Georgia Institute of Technology College of Sciences

\ell-sequences are periodic binary sequences {a_i} that arise from Feedback with Carry Shift Registers and in many other ways. A decimation of {a_i} is a sequence of the form {a_{di}}. Goresky and Klapper conjectured that for any prime p>13 and any \ell-sequence based on p, every pair of allowable decimations of {a_i} is cyclically distinct. If true this would yield large families of binary sequences with ideal arithmetic cross correlations. The conjecture is essentially equivalent to the statement that if p>13 then the mapping x \to Ax^d on \mathbb Z/(p) with (d,p-1)=1, p \nmid A, permutes the even residues only if it is the identity mapping. We will report on the progress towards resolving this conjecture, focussing on our joint work with Bourgain, Paulhus and Pinner.

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.