Math 583
Partial Orders, Fall 2018

Instructor:   Jozsef   Balogh
Office: 233B Illini Hall
Time and place: 9:00- 9:50 pm MWF, 145 Altgeld Hall
Office Hour: by appointment.
Math 580 or consent of instructor, obtainable by familiarity with elementary combinatorics.

CANCELLED CLASSES: September 27 (F), Oct 1 (M) ;


There will be 5 homework assignments. Homework allows you to choose five out of six problems to write up. Problems are worth 5 points each, so the maximum score/homework is 25 points. A is from 80%, grade drops by 5% (so 75% is A-). Make up possibilities include giving lecture.

  • Homework 1: Do 4 out of 6: 1. Problem 0.2;    2. Problem 0.5(a);    3. Problem 0.5(b);    4. Problem 11.1.3;   5. Problem 11.2.8;    6. Problem 11.2.9;    DUE:  September 17 Monday.  

  • Homework 2: Do 4 out of 6: 1. 11.2.13;   2. 11.2.15;    3. 11.2.16;    4. 11.2.21;    5. 11.3.4;    6. 11.3.5    DUE:  September 24 Monday.  

  • Homework 3: Do 5 out of 7: 1. 11.3.13 (a,b);    2. 11.3.14;    3. 11.4.11;    4. 11.4.20;    5. Proof of Lemma 11.4.9 and 11.4.29;    6. 12.1.4;  
    7. Prove that the dimension of the poset $P$ below decreases by two if we delete the elements $k$ and $j$ of the unforced pair $(k,j)$. (Hint: To give a lower bound on the dimension of $P$, it is enough to use only alternating cycles of length at most two.)    DUE:  October 3 Wednesday.  

  • Homework 4: 1. Let $V_1,V_2,V_3,V_4$. each of size $n$, being $\epsilon$-regular and density $1/3$. Formulate and prove the counting lemma for the induced four-cycles, giving both lower and upper bounds. (needs an actual proof).
    2. Prove that when SZRL is applied to the half-graph (threshold graph, with class sizes $n,n$), then there is always at least k/10 non-regular pairs, where $k$ is the number of classes of the partition.
    3. Let $(V_1,V_2)$ be a bipartite graph with $m< \epsilon^3 |V_1||V_2|$. Prove that the graph is $\epsilon$-regular.
    4. For every $0< \epsilon, d < 1$ every bipartite graph $B$ with classes $V_1,V_2$ with sizes n and density $d$ contains an $\epsilon$-regular subgraph $B'$ with classes $U_1,U_2$ , with density at least $(\epsilon/3)d$ (?) and size of $U_1,U_2$ at least $(n/2)*d^{50/\epsilon^2}$.
    5. Recall that we work with $3$-regular hypergraphs. Give good bounds on:\\ (i) f(n,7,4), (ii) f(n,5,4), (iii) f(n,5,3), (iv) f(n,6,4) .
    6. Recall that we work with $3$-regular hypergraphs. Give good bounds on:\\ (i) f(n,6,6), (ii) f(n,6,8), (iii) f(n,6,9), (iv) f(n,6,10).
       DUE:  December 14 Friday.  

  • Homework 5: 1. Let $V_1,V_2,V_3$ be the classes of a $3$-partite graph, each of sizes at least $n$. Each pair is $\epsilon$-regular, and the minimum degree of the graph is $n/10$. Prove or disprove that it contains a Hamilton cycle.
    2. Let $f(G,K_4,2)$ be number $3$-edge coloring of graph $G$ without a monochromatic $K_4$. Give a good upper bound on the number of such colorings.
    3. Let $c>0$ be a very small constant. Let $G$ be a $K_7$-free graph with the property that every $cn$ vertices spans a $K_4$. Give an upper bound on the number of edges of $G$.
    4. Prove that for every c>0, if n is sufficiently big, and an n-vertex K_4-free graph has more than n^2(1/3-c) edges then it is almost 3-partite.
    5. Prove that almost all n-vertex $K_4$-free graph is almost $3$-partite. Almost $3$-partite means that for every $a>0$, for n large enough there is a $3$-partition that the number of non-cross-edges is at most $an^2$. [hint: exercise 4 helps.]
    6. Try to explain, why the weak-regularity lemma requires only "few" classes. Be somewhat "rigourous". Literature could be used.
       DUE:  December 21 Friday.  

    D.~B.~West: The Art of Combinatorics, Volume III: Order and Optimization.