Classes: Friday 12:00–2:30pm, room 301.

Office hour by appointment.

All class after February 21 moved from Tuesday to Friday, 12–2:30pm.

Last class March 31, 12 noon

Final on Monday, April 10, 9–11:30am

Recommended books:

Grading:

Assignment problems are intended for you to solve alone. If you get stuck, ask me (it's "free" - no deductions for hints I may give). Some of the problems are "standard" and could be looked up in a library or on the internet. Please don't do so. If you did find the solution in a book or online, or you discussed it with somebody else acknowledge this fact.

Topics covered:

Eulerian graphs.

Simple bounds on the chromatic number: ω(G) ≤ χ(G) ≤ Δ(G)+1. Brooks' theorem characterizing G with χ(G) = Δ(G)+1.

Planar graphs, Euler's polyhedron formula and the maximal number of edges in a plnar graph. Five-color theorem. (Four color theorem without proof.)

Mycielski's construction of high chromatic triangle-free graphs.

1st assignment (submit on or before Sunday, January 15):

1. State and prove a necessary and sufficient condition for the existence of Eulerian walk in directed graphs. (An Eulerian walk traverses every directed edge exactly once in the correct direction and returns to the point where it started.)

2. Prove that there exists a sequence of digits 0-9 such that all 100000 patterns of 5 digits shows up in it exactly once as a subsequence of 5 consecutive digits.

3. Prove that all graphs G have at least χ(G) vertices of degree at least χ(G)-1.

Shift graphs and their chromatic number.

2nd assignment (submit in email on or before Sunday, January 29, extended to Tuesday, February 7):

1. Prove that the crossing number lemma is tight for all possible n and e (apart from the constant factor).

2. Prove that the Szemerédi-Trotter theorem is tight for all possible number of points and lines (apart from the constant factor). Hint: use an appropriate axb grid for the set of points.

3. Prove that all C

4. Here is a modified shift graph S'

5. Prove that among n points in the plane there are O(n

Connection between the finite and the infinite statements: the compactness principle (proved – through König's lemma – only for a countable number of variables).

Upper bounds on the graph and hypergraph Ramsey numbers. Lower bound for R(k,k) using the probabilistic method.

The two versions of the probabilistic method (a) take a random graph and prove that with positive probability it has the desired properties and (b) take a random graph and modify it slightly so that it has the desired properties.

3rd assignment (submit in email on or before Tuesday, February 7):

1. Prove the following statement (Paris-Harrington theorem): For all positive integers r and k there exists n>k such that for all 2-colorings of the r-subsets of the set H={k,k+1,k+2,...,n} there exists a monochromatic subset S of H with |S|≥min(S).

2. Prove the following statement (Erdős-Szekeres theorem): For every integer k≥3 there exists n such that among any set of n points in the plane with no three on a line one can find the vertices of a convex k-gon.

3. (a) Prove that the following statement is false: For every positive integer k there exists n such that for any coloring of the edges of K

(b) Make the statement true by allowing just one more type of k-cliques and prove this statement.

4. Apply the (simplest form of) the probabilistic method to prove a lower bound on the Ramsey number R

5. (a) Compute or estimate the size of k-chromatic Mycielski and shift graphs.

(b) Prove quadratic lower bound on the size of any triangle-free k-chromatic graph.

4th asignmet (submit in email on or before Sunday February 12):

1. Find the threshold function for 4-cliques to appear in the random graphs.

2. Prove the existence of graphs with cromatic number k and no triangle or C

3. Find a connected graph H and probabilities p

5th assignment (submit in email on or before on or before Sunday Februar 26, extended to Wednesday, March 1):

0. (not really a mathematical problem) Draw the graph KG(5,2).

1. We saw that the Kneser graphs are edge-transitive. (a) Find which Kneser graphs are 2-edge-path transitive, i.e., when every path of length 2 can be brought to every other path of length 2 by a automorphism of the graph. (b) Show that these graphs are also 3-edge-path transitive.

2. Deleted.

3. We proved that the Borsuk graph B

4. The inclusion-exclusion formula gives the size of the union of finite sets from the sizes of intersections of subsets. Prove that if you truncate the formula by considering only the sizes of the intersections of at most k sets, you get a lower or upper bound on the size of the union depending on k.

6th assignment (submit in email on of before Wednesday, March 8):

1. Find all maximal size Sperner systems on a fixed base set of odd size. We did this in class for even size.

2. Find all maximal size pairwise intersecting families of k-subsets of an n-set. Hint: use these steps. (i) Find the values of the the parameters k and n, where there are very many extremal families. If there are not many: (ii) Characterise families with equality in the Katona lemma on intervals of cyclic orderings. (iii) Compare two cyclic orderings that differ only by a transposition of a pair of neighbors.

3. Find many maximal size VC-dimension-d families of subsets of an n-set. The more, the better, try to reach at least 3

4. Find any maximal family of VC-dimension d that is not maximal size. You choose n and d and a family of subsets of an n-set of VC-dimension d such that if you add a set to the family the dimension increases but the size of the family does not reach the bound in the Sauer-Shelah theorem.

5. (a) We found the VC-dimension of the family of open half-planes in the plane to be three. Find the order of magnitude of the growth function of this family. (b) Find the VC-dimension of the family of open circular disks in the plane. Can you say something about the growth function here? (Recall that the growth function f for a family F is defined as f(n) being the maximum cardinality of the set {X∩S|X∈F} for all n-sets S.)

The definition of the Ackermann function as A

Erdős-Szekeres cap-cup theorem and the construction showing that it is tight.

7th assignment (submit in email on of before Wednesday, March 15):

1. We saw VdW(k,r)≤k

2. We used a doubly exponential function of z for the number of colors in the term defining w in Lemma 1. Modify the argument to get a simply exponential function in the same place.

3. The Van der Waerden theorem can be equivalently stated as follows: If we color all the natural numbers with finitely many colors there will always be monochromatic arithmetic progressions of arbitrary size. Recall that in the case of Ramsey theorem, we could guarantee not only arbitrary size monochromatic cliques but also

4. extended—try at least for HJ(3,r) Try to approximate the bound this specific inductive proof gives to HJ(k,2). In this problem you don't have to be precize, but try to reasonably guess how big the obtained bound gets using the values of the Ackermann function as your metric.

5. Find good setting for the numbers m and t in the Behrend's construction that and find the size of the 3-term AP-free set as a funtion of n. It should be n

8th assignment (submit in email on or before March 22):

1. Prove that if G is chordal if and only if it has a perfect elimination order (i.e., a linear order on the vertices where the "forward neighbors" of any vertex form a clique). One direction should be easy from what we had in class, for the other direction prove that if G is chordal and K is a clique in G not containing all vertices, then G has a vertex outside K whose neighborhood is a clique.

2. The statements (a-c) hold for the same graphs G. Prove that if they (all) hold, then G is perfect. Prove as much of the equivalence of the three statements as you can. (The graphs satisfying these statements are called cographs).

(a) P

(b) In all induced subgraphs H of G all (containment) maximal independent sets of H meet all (containment) maximal cliques of H.

(c) G can be constructed starting from K

9th assignment (submit in email on or before March 29):

1: We saw how to construct n-choose-2 points in n-space determining only 2 distances. Find an even larger set closing a substatial part of the gap toward the upper bound.

2. How about the maximal size of a point set in d-space determining three distinct distances? Derive both lower and upper bounds using similar techniques to the ones seen in class.

3. Find lower and upper bounds on the maximal size of a set system over an n element base set such that (a) the size of pairwise intersections are divisible by 6, but the size of no set is divisible by 6. Or (b) each set size and each pairwise intersection size is divisible by 6. (Find "reasonable" bounds, do not shoot for the exact maximum.)

Three forms of LLL. In each form A

In the first form of LLL we assume (Δ(G)+1)max(Pr[A

In the second form we assume Pr[A_i]+∑

In the third form we assume there exist real numbers 0< x

The second conditon clearly implies the first, the third condition implies the second with the choice x

The main step of the proof is showing that Pr[A

10th (and last) assignment (submit in email on or before April 5):

1. Can you modify the statement and the proof of the Erdős-Sefridge theorem so that it applies to games where Maker takes 2 vertices of the hypergraph at every turn but Breaker still takes just one? Modify the weight function in such a way that you can still give Breaker a winning strategy in any game with a bounded number of winning sets, all of size k. Your bound will be smaller than in the original theorem, but should nevertheless be exponential in k.

2. Let k and n be positive integers. Prove that VdW(k,c) > c

3. A simpler definition of the dependency graph would be connecting two bad events if they are not independent. Prove that the LLL with this definition of the dependency graph does not hold by finding three pairwise independent bad events (in the probability space of your choice), each of probability 1/2 such that one cannot avoid all three. Harder version: find many pairwise independent events of probability 1/k (k arbitrary) that cannot all be avoided. Hint: Recall that the events that two sets are monochromatic in a uniform random coloring are independent unless the sets have more than one elements in common.

Have questions? Need consultation? Write.