Partial Orders, Fall 2018

**Instructor:** Jozsef Balogh

**Office:** 233B Illini Hall

**E-mail:** jobal@math.uiuc.edu

**Time and place:** 9:00- 9:50 pm MWF, 145 Altgeld Hall

**Office Hour:** by appointment.

PREREQUISITES:

Math 580 or consent of instructor, obtainable by familiarity
with elementary combinatorics.

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

MAKE UP CLASSES:

;

COURSE REQUIREMENTS:

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.

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.

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.

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.

TEXT:

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