Info on office hours on Mon. Dec. 11 and later this break, see my index page.
Textbook: R. A. Brualdi, Introductory Combinatorics (4th edition) Pearson/Prentice-Hall, ISBN 0-13-100-119-1.
Updated last Dec. 8, 2006
For the 3rd midterm (Wed. night at 9 pm):
Review what we have covered since the 2nd midterm.
This includes directed graphs (including acyclic
digraphs and tournaments), chromatic number and
bounds relating it to other parameters, and also
chromatic polynomials - especially the recursion
and basic properties. Make sure you can work out
simple examples.
Also the following topic which I introduced in
today's class. I'll review it in Wed. class but
you should read through the material below and
try the problems below.
The Prufer Correspondence:
Start with a tree T on n labeled vertices;
produce a sequence P(T) of n-2 numbers, each
between 1 and n. Since the correspondence
is 1-1 and onto, the number of trees on n
labeled vertices is n^(n-2).
The method is as follows: Take the endpoint
of lowest index - i.e., find i in {1,...,n}
such that v_i is an endpoint of T and no v_j
with j < i is an endpoint of T. In the
example shown below, v_1 is chosen. The first
term of P(T) is the unique index belonging
to the neighbor of v_1 - which is 6. Now
delete v_1, as shown, and repeat the process
using the new tree T-v_1, which has lowest
index 3 among its endpoints, so the second
term in P(T) is 4, etc. Note that removing
an endpoint means also removing one edge.
Stop when you reach K_2.
If T has only one or two vertices (n = 1 or 2),
then P(T) is empty - which is consistent
with the fact that there are unique trees on
1 labeled vertex and on 2 labeled vertices.
T (a tree with 7 labeled vertices)
0 v_3
|
|
| v_4 v_7
O-------0
|
|
| v_6 v_2 v_5
0-------0--------0
|
|
| v_1
0
0 v_3
|
|
| v_4 v_7
O-------0 6
|
|
| v_6 v_2 v_5
0-------0--------0
v_4 v_7
O-------0 6 4
|
|
| v_6 v_2 v_5
0-------0--------0
v_4 v_7
O-------0 6 4 2
|
|
| v_6 v_2
0-------0
v_4 v_7
O-------0 6 4 2 6
|
|
| v_6
0
The Prufer sequence for T:
v_4 v_7
O-------0 P(T) = 6 4 2 6 4
Note that the algorithm ends with a copy of K_2.
For another example, if T = K_1,n-1 is a star
with n-1 endpoints and the central vertex has
label v_i, then P(T) = (i,i,...,i). If T is
a path, labeled V_1, v_2, ... ,v_n, then P(T)
is (2,3,...,n-1).
Test your understanding with the following two
problems:
(1) Find all 16 trees on 4 labeled vertices;
write down the corresponding Prufer sequences.
(2) Suppose that T is a tree on n labeled
vertices and that n is at least 2. Then
one of the endpoints of T is labeled v_1
if and only if 1 does not appear in P(T).
(3) Let S be a sequence of n-2 terms from the
set {1, ... ,n}. Show that there is a unique
labeled tree on n vertices with P(T) = S.
There weren't any questions on the problems below in today's class (Monday) but I suspect that some some of you haven't tried them yet. We will review your questions on the problems above and below on Wed.
Here are some Practice problems for midterm 11/29 .
1. Define digraph, acyclic digraph, and tournament. In fact,
for every term used below, make sure you can define it.
Statements should be proved or refuted by an example.
If there is simple restatement that makes a false statement
true, then give it.
2. Every acyclic digraph has a vertex of in-degree 0.
3. If D is a tournament with n vertices, then D must
have more than one vertex of out-degree = n-1.
If G and H are graphs, we define G*H to be the graph
V(G*H) = V(G) + V(H) (where "+" means disjoint union)
E(G*H) = E(G) + E(H) + {[v,w]: v in V(G), w in V(H)}
4. Show that chi(G*H) = chi(G) + chi(H), where chi means
chromatic number.
5. Of the graphs K_n, K_(p,q), C_n, which can be written
in the form G*H and give a corresponding choice of G,H.
6. For any graph G, if delta-hat(G) is at most 2,
give an upper bound on chi(G).
7. If omega(G) is at least 4, where omega denotes clique
number, give a lower bound on chi(G).
8. Find G with no K_3-subgraph but with chi(G) = 4.
(This can be done with an 11-vertex graph G but this is
a tough problem!)
9. Show that for any graph G, chi(LG) is at least Delta(G).
Let G be a graph and let P(G,t) denote the number of ways
the vertices of G can be colored from a set of t colors.
As we have shown, P(G,t) is a polynomial of the form
P(G,t) = c_0 + c_1 * t + c_2 * t^2 + ... + c_n * t^n
10. What are the values of c_0 and c_n?
11. What is the significance of n and c_(n-1) for G?
12. State and prove the basic recurrence relation among
chromatic polynomials.
For homework, due Monday, I assigned several problems from the hand-out given to you in class. But the hand-out does define digraph _differently_ from what we said since it requires that arcs consist of ordered pairs of _distinct_ vertices. So the hand-out excludes loops. Note that our definition of finite-state machine (FSM) given in class does allow loops.
This is really just a technicality but it will change the number of digraphs of some given type. The first assigned problem asks you to find all nonisomorphic unlabeled digraphs that have four vertices and four arcs. So when you do this, you can leave out the digraphs that contain loops. The total number is 18 by my count.
For Wed.(11/1), draw all four of the connected FSMs with 3 states;
i.e., find all digraphs with 3 vertices in which each vertex
has a unique arc out (and the underlying undirected graph is
connected). We are considering two digraphs to be the same
if one is isomorphic to the other - i.e., if there is a 1-1
correspondence between their vertices f:V --> V' which
induces a 1-1 correspondence between the arcs by sending
a = (v,w) to a' = (v',w') with v' = f(v), w' = f(w)
There is only one FSM with _one_ vertex - a directed loop.
There are two FSMs with _two_ vertices -
(i) a loop with one arc going into the vertex with the loop
V = {v,w}, A = ((v,v),(w,v)}
(interchanging v and w gives a different digraph which is
isomorphic to the original one)
and (ii) two arcs going opposite ways between two vertices
V = {v,w}, A = {(v,w),(w,v)}
The problem is asking you to enumerate all of the 3-vertex
FSMs which are connected. (One would have many more if it
is allowed to have non-connected digraphs. For instance,
for 2 vertices, one would also have two disjoint loops.)
Also, draw example digraphs obtained by orienting Q_3 so
that (i) D is weakly connected, (ii) D is acyclic, (iii)
D is strongly connected, (iv) D contains some pair of
vertices which are not joined by any directed path.
(According to the notes I gave out: a digraph is strongly
connected if every pair of vertices can be joined by a
directed path (in both directions). It is weakly connected
if each pair of vertices can be joined by a directed path
in at least one direction.)
Hot off the press! Review page for the midterm next week. This is a partial list of topics but a few more are yet to appear. Be sure to look it over and bring your questions to class tomorrow. Also, expect a quiz on matchings.
Ok, here is the answer to the quiz (direct from Dallas)
Starting with the set S = {a,b,c,d,e,f}, form the family
F_1 = {T_1,T_2,T_3}, where the T_i are 3-element subsets of S
T_1 = {a,b,c}, T_2 = {c,d,e}, T_3 = {a,d,f},
The family F_1 packs the pairs of S into triples - that is
For every pair {x,y} a 2-element subset of S,
there is at most one triple in F_1 containing the pair as a subset.
There is no larger family of triples.
FALSE! As many of you noticed, you could also take, e.g.,
T_4 = {b,e,f}.
However, a smaller family of triples also packs pairs into triples
and cannot be enlarged to such a family:
Let F_2 be the family F_2 = {T'_1, T'_2}, where
T'_1 = {a,b,c}, T'_2 = {d,e,f}.
Then clearly no new triple can be added since by the PHP it would
have to overlap with either T'_1 or T'_2 in a pair of elements.
So a _maximum_ family has 4 elements
while F_2 is a _maximal_ family with 2 elements.
For next week, we will cover Chap. 9, pp. 322--345. I'll have a bit more to say about the paper I gave you, but our focus will be on Chapter 9. For Monday, do #2 on p. 358 and be ready to put it on the board.
For Wed. 10/18, write down the definition analogous to Steiner triple systems (STS) but using sets of size 4, rather than sets of size 3. An STS is a set S and a family of 3-element subsets T_1, ... ,T_k contained in S such that every 2-element subset of S belongs to one and only one of the T_k. Now find the equations that relate and describe n and k, where n is the number of elements in S. For an STS, we found that C(n,2) = 3k and that 2 divides n-1.
Let Q_1, ... ,Q_k be 4-element subsets of S such that every pair in S belongs to one and only one 4-set in the family. If S has n elements, then C(n,2) = C(4,2)*k so n(n-1) = 12k (i.e., n(n-1) is congruent to 0 mod 12) and 3 divides n-1. The same reasoning works for t-element subsets of S, yielding the nec. conditions
n(n-1) = 2*C(t,2)*k - i.e., n(n-1) = 0 (mod t(t-1)) and t-1 divides n-1
In the paper I handed out today, you will see that we consider something a bit more general than the exact systems (eg STS). We take a family m of p-element subsets of the vertices of a drawing D of K_n with the property that no two of the p-element subsets have a pair in common and the family is as large as possible with this property (I wrote "maximal" in the paper but we really want "maximum". The result of Erdos and Hanani (5) is that for any fixed p at least 2, m-bar(n,p) (the number of elements in m) is asymptotically just the same as C(n,2)/C(p,2). That is, lim (n --> oo) of the quotient is 1.
Question: What happened to the last four terms in the calculation below (5) - just before = (1/64)q(p)?
Previously, I asked you to find the set of all distinct trees on 5 labeled points.
For 4 such points, there are 12 different
labeled trees which are paths
(E.g., 1-2-3-4 and 4-3-2-1 are the same but
1-2-3-4 and 1-3-2-4 are not the same)
and there are four more trees with a single
vertex of degree 3. In the first 12, the
chance that a random vertex is an endpoint
is (1/2) while in the next 4, the chance is
3/4. Hence, over all, the probability that
a random vertex of a random tree on 4 labeled
points is an endpoint is
(3/4)(1/2) + (1/4)(3/4) = 9/16.
When you have found all the distinct trees on
5 labeled points, also calculate the probability
that a randomly selected vertex in a randomly
chosen tree is an endpoint.
I asked you to find the number of distinct copies of Q_1 in Q_d. This is the same as asking for the number of edges. Since each vertex has degree d and since there are 2^d vertices, by the first theorem of graph theory, |E| = d*2^(d-1). (Check: For Q_3, |E| = 12 = 3*(2^2).) Recall that the first theorem of graph theory says that the sum of all the vertex degrees is twice the number of edges. To find copies of Q_2 in Q_d, you need to choose two of the d coordinates. Once the choice is made, there are 2^(d-2) different Q_2-subgraphs depending on the values of the d-2 fixed coordinates. For instance, for Q_3, there are 6 faces since (3 choose 2)*2 = 6. So the number of Q_2 subgraphs in Q_d is f(2,d) = (d choose 2)*2^(d-2). Can you prove this by induction? For d=2, the basis case, the assertion holds: (2 choose 2)*2^(2-2) = 1. Suppose it holds for Q_d and consider Q_(d+1). Check that f(2,d+1) = 2f(2,d) + d*2^(d-1). Since each Q_2 in Q_(d+1) is either a Q_d in the first copy of Q_d, a Q_2 in the second copy of Q_d, or a Q_2 determined by one of the edges of Q_d. How about the number of Q_r subgraphs in Q_d, for 0 \leq r \leq d? The problem about showing that G-bar (the complement of G) is connected whenever G is not connected may be easier if you prove something seemingly harder - if G is not connected, then G-bar has diameter 1 or 2 (the diameter is the shortest distance - i.e., number of edges in a shortest path - between the worst-case pair of vertices in the graph). That is, you can show that every pair of vertices in the complement of a disconnected graph are either directly adjacent or there is a vertex adjacent to each of them. It is an interesting fact about mathematics that sometimes it is easier to do something harder ;-)
Don't worry about the probability theory remarks; they won't be included. I asked you to find the next number in the sequence 1,1,2,5 of Catalan numbers. Of course, you could just look it up but I would rather that you use the recursion I showed you in class or else just count all the different triangulations of a hexagon. Answer is 14 = 1*5 + 2*2 + 5*1 . Can you find 14 different triangulations of a hexagon? "Different" here means that if you label the corners 1,2,3,4,5,6, then the triangulation with central triangle 135 is counted separately from the triangulation with central triangle 246 - even though they are isomorphic graphs.
Some reading for next week: Chap. 3 selected parts indicated below. We've covered most of this in class but there are some examples here you should review to see if the ideas are clear.
Example at bottom of p. 47. Example on p. 51: Read the last 6 lines of the para below the example. The next paragraph shows that the ease of counting may be changed depending on what order you count in. Then on p. 52, for the example, just look at the second solution. Jump to the bottom of p. 53 which is better expressed on the middle of the next page. Now jump to p. 60, and read all of section 3.3.
Here are some problems to try for Chap. 3: 1,4b,7abc,16,23,46a,54 (the answer given in the book is 3^n but why is that correct?). We'll discuss them, beginning on Monday. Some may become homework problems.
For Friday 9/15, I asked you to take a particular graph G (drawn on the board so ask someone who was there to see it) and to count the total number of cliques and also the size of the largest clique (called the clique-number) omega(G). Recall that a clique is a set of vertices which induces a complete subgraph and which is maximal with respect to that property. I also asked you to show that for large k and for n large with respect to k, if p is between 0 and 1, then
(1 - p^C(k,2))^C(n,k)
is approximately equal to
exp(- [p^C(k,2)]*C(n,k))
using the fact that
e^(-1) = lim(n --> oo) (1 - (1/n))^n
This second "try it" problem is just a bit of algebra.
For Wed. 9/13, the problem was to show that 2^n = sum of C(n,k) as k runs from 0 to n inclusive, and 0 = sum of C(n,k)*(-1)^k. In class, we used the binormial theorem and we also discussed combinatorial arguments.
For Monday 9/11, consider the graph G = (V,E), where
V = V_1 U V_2, V_1 and V_2 disjoint and non-empty
E = {[v,w] : v in V_1, w in V_2}
Problem #1:
If V_1 has m elements and V_2 has n elements, how
many vertices and edges does the graph have?
This graph is called the "complete bipartite graph"
and is denoted K_m,n. In class, I drew K_3,3 (the
"3 houses and 3 utilities graph" in which each house
is adjacent to each utility) and we noted that this
graph has 6 vertices and 9 edges.
BTW, "U" means "union" and the symbol "_" means subscript.
Problem #2: How many distinct copies of the graph K_2,2 can you find in the graph K_3,3? Problem #3: We defined a tree as a graph which is connected but contains no cycles. It was shown in class that every nontrivial tree contains at least 2 endpoints (i.e., vertices of degree 0). You may want to use this as a lemma in the following problem. Show that every tree is bipartite.
As defined in class, "bipartite" means that one can label the vertices with 2 colors so that no two adjacent vertices have the same color.
Again these problems aren't for collection but you may be asked about them in class.
For Fri., try problems #5 and 16 of Chap. 2. You don't need to write them up for collection but be ready to work one at the board if I call on you.
In class, I assigned two problems for collection on Wed. 9/6: (1) is below - the Hadamard problem. (2) Show that for any two distinct vertices v,w in the cube Q_d, defined in class today and in the book on p. 101, there is a "subcube" in which v and w are at opposite corners. All I expect here is that you indicate the key idea - not the technical details. For example, the 3-cube Q_3 has, in addition to itself, six subcubes of type Q_2 and 12 subcubes of type Q_1. A subcube of Q_3 is defined by choosing a subset of the set {1,2,3} of coordinates and then fixing the values of the other coordinates. So since there are three 2-element subsets of {1,2,3} and two possible values (0 and 1) for the remaining coordinate, there are 3 x 2 = 6 of these 2-dimensional subcubes.
Also for Sept. 6, please read the following portions of Chap. 1: section 1.1 (up to p. 5 parag "More generally"), section 1.3 (up to p. 11, parag. "Three-dimensional analogs"), sections 1.4, 1.5, 1.6, and try the following problems for Ch. 1: #1,2,4a,23,24,25,28. I won't ask you to write them up this time but do be ready in case I ask you about one of them. Of course, not everybody will get every problem, but you ought to at least try them. In addition to collecting the two problems above as homework, I'll ask some of you to put some of these problems from Chap. 1 on the board.
I mentioned a website in class. It's the on-line encyclopedia of integer sequences . Try it with 0,1,3,6; now try 1,1,1,1,2,3,7!
Recall that a square matrix A (with entries of +1 and -1) is Hadamard provided the dot product of any two rows is zero. We've already seen that if A is Hadamard and n x n, then n must be even. Proof: The dot product of two distinct rows is a sum of n terms with a of them equal to +1 and b of them equal to -1. If the dot product is zero, then a - b = 0, i.e., a = b. Hence, 2a = a + b = n so n is even.
For Wed. Sept. 6, try to prove that if A is an n x n Hadamard matrix and n is bigger than 2, then n is divisible by 4. Here is a hint:
Without loss of generality (WLOG) the first row is all 1s. Indeed, if A is Hadamard, then so is A' where A' is obtained from A by multiplying any column (or row) by -1. (Why?) So if you multiply each column with a -1 in the first row by -1, you change A into another Hadamard matrix with first row all +1. Now there are four types of column: 1 1 1 1 1 1 - - 1 - 1 - . . . . . . . . . . . . and suppose A has a,b,c,d, columns, resp., of each type. Since the first two rows of A have dot product zero, a+b-c-d = 0. The same argument for rows 1 and 3 and rows 2 and 3, resp., gives a total of three equations, and one more equation follows from the fact that the total number of columns is n. However, with four equations in four unknowns, one can solve for a in terms of n, getting a = n/4. But a is an integer so n is divisible by 4.
Back to the index page To contact me, you can use voice mail (202-687-2703), e-mail kainen at georgetown.edu