Georgia Institute of Technology College of Sciences

The permutation removal lemma was first proved by Klimosová and Král’, and later reproved by Fox and Wei in the context of permutation property testing. In this talk, we study a local version of the permutation removal problem. We show that for any permutation σ not equal to 12, 21, 132, 231, 213, or 312, there exists ε(σ) > 0 such that for any sufficiently large integer N, there is a permutation π of length N that is ε-far from being σ-free with respect to the ρ∞ distance, yet contains only a single copy of σ. Here, the ρ∞ distance is defined as an L∞-variant of the Earth Mover’s Distance between two permutations. We will also discuss our result on the local induced graph removal problem. This is joint work with Fan Wei.

I’ll describe some recent work (joint with Jeff Kahn and Jinyoung Park) on the "Second" Kahn--Kalai Conjecture (KKC2), the original conjecture on graph containment in $G_{n,p}$ that motivated what is now the Park--Pham Theorem (PPT). KKC2 says that $p_c(H)$, the threshold for containing a graph $H$ in $G_{n,p}$, satisfies $p_c(H) < O(p_E(H) log n)$, where $p_E(H)$ is the smallest p such that the expected number of copies of any subgraph of $H$ is at least one. Thus, according to KKC2, the simplest expectation considerations predict $p_c(H)$ up to a log factor. This serves as a refinement of PPT in the restricted case of graph containment in $G_{n,p}$. Our main result is that $p_c(H) < O(p_E(H) log^3(n))$. This last statement follows (via PPT) from our results on a completely deterministic graph theory problem about maximizing subgraph counts under sparsity constraints. 

The regularity method for graphs has been well studied for dense graphs, i.e., graphs on $n$ vertices with $\Omega(n^2)$ edges. However, applying it to sparse graphs, i.e., those with $o(n^2)$ edges seems to be a harder problem. In the mid 2010s, the regularity method was extended to dense subgraphs of random graphs thus resolving the KŁR conjecture. Later, in another direction, Conlon, Fox, Sudakov and Zhao proved a removal lemma for $C_5$ in graphs that do not contain any $C_4$ (such graphs on $n$ vertices can contain at most $n^{3/2}$ edges). In this talk, we will consider a similar problem for sparse $3$-uniform hypergraphs. In particular, we consider an application of the regularity method to $3$-uniform hypergraphs whose vertices do not contain $C_4$ in their links and satisfy an additional boundedness condition. This is joint work with Vojtěch Rödl and Mathias Schacht.