Georgia Institute of Technology College of Sciences

Let H be a fixed graph with h vertices. The graph removal lemma states that every graph on n vertices with o(n^h) copies of H can be made H-free by removing o(n^2) edges. We give a new proof which avoids Szemeredi’s regularity lemma and gives a better bound. This approach also works to give improved bounds for the directed and multicolored analogues of the graph removal lemma. This answers questions of Alon and Gowers.

In 1993 Jackson and Wormald conjectured that if G is a 3-connected n-vertex graph with maximum degree d \ge 4 then G has a cycle of length \Omega(n^{\log_{d-1} 2}). In this talk, I will report progresses on this conjecture and related problems.

Given a finite poset $P$, we consider the largest size ${\rm La}(n,P)$ of a family of subsets of $[n]:=\{1,\ldots,n\}$ that contains no  subposet $HP.  Sperner's Theorem (1928) gives that${\rm La}(n,P_2)= {n\choose{\lfloor n/2\rfloor}}$,  where$P_2$is the two-element chain.    This problem has been studied intensively in recent years, and it is conjectured that$\pi(P):=  \lim_{n\rightarrow\infty} {\rm La}(n,P)/{n\choose{\lfloor n/2\rfloor}}$exists for general posets$P$, and, moreover, it is an integer. For$k\ge2$let$D_k$denote the$k$-diamond poset$\{A< B_1,\ldots,B_k < C\}$. We study the average number of times a random full chain meets a$P$-free family, called the Lubell function, and use it for$P=D_k$to determine$\pi(D_k)$for infinitely many values$k$.  A stubborn open problem is to show that$\pi(D_2)=2$; here we prove$\pi(D_2)<2.273$ (if it exists).    This is joint work with Wei-Tian Li and Linyuan Lu of University of South Carolina.

In the paper "On the Size of Maximal Chains and the Number of Pariwise Disjoint Maximal Antichains" Duffus and Sands proved the following:If P is a poset whose maximal chain lengths lie in the interval [n,n+(n-2)/(k-2)] for some n>=k>=3 then there exist k disjoint maximal antichains in P. Furthermore this interval is tight. At the end of the paper they conjecture whether the dual statement is true (swap the words chain and antichain in the theorem). In this talk I will prove the dual and if time allows I will show a stronger version of both theorems.