The degeneracy of a graph is a measure of sparseness that appears in many contexts throughout graph theory. In extremal graph theory, it is known that graphs of bounded degeneracy have Ramsey number which is linear in their number of vertices (Lee, 2017). Also, the degeneracy gives good bounds on the Turán exponent of bipartite graphs (Alon--Krivelevich--Sudokav, 2003). Extending these results to hypergraphs presents a challenge, as it is known that the naïve generalization of these results -- using the standard notion of hypergraph degeneracy -- are not true (Kostochka--Rödl 2006). We define a new measure of sparseness for hypergraphs called skeletal degeneracy and show that it gives information on both the Ramsey- and Turán-type properties of hypergraphs.
Based on joint work with Jacob Fox, Maya Sankar, Michael Simkin, and Yunkun Zhou
For positive integers $r > \ell \geq 1$, an $\ell$-cycle in an $r$-uniform hypergraph is a cycle where each edge consists of $r$ vertices and each pair of consecutive edges intersect in $\ell$ vertices. For $\ell \geq 2$, we determine the exact threshold for the appearance of Hamilton $\ell$-cycles in an Erd\H{o}s--R\'enyi random hypergraph, confirming a conjecture of Narayanan and Schacht. The main difficulty is that the second moment is not tight for these structures. I’ll discuss how a variant of small subgraph conditioning and a subsampling procedure overcome this difficulty.
We present a random construction proving that the extreme off-diagonal Ramsey numbers satisfy $R(3,k)\ge \left(\frac12+o(1)\right)\frac{k^2}{\log{k}}$ (conjectured to be asymptotically tight), improving the previously best bound $R(3,k)\ge \left(\frac13+o(1)\right)\frac{k^2}{\log{k}}$. In contrast to all previous constructions achieving the correct order of magnitude, we do not use a nibble argument.
Beyond the paper, we will explore a bit further how the approach can be used for other problems.
Let $LC_n$ be the length of the longest common subsequences of two independent random words whose letters are taken
in a finite alphabet and when the alphabet is totally ordered, let $LCI_n$ be the length of the longest common and increasing subsequences of the words. Results on the asymptotic means, variances and limiting laws of these well known random objects will be described and compared.
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.
A geometric graph consists of a set of points in the plane together with line
segments between some pairs of points. A convex geometric graph is a geometric graph whose
points are in convex position. We present some old and new extremal results and applications,
and their extension to geometric hypergraphs, together with a variety of open problems.
Partly joint work with Zoltan Furedi, Tao Jiang, Sasha Kostochka and Dhruv Mubayi
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.
Given a feasible degree sequence D, we consider the uniform distribution over all graphs with degree sequence D. In 1995, Molloy and Reed gave a criterion for determining the existence of a giant (i.e. linear in n) component for degree sequences satisfying certain technical conditions; in 2018, Joos, Perarnau, Rautenbach, and Reed gave a refined result that applies to essentially all feasible D. In this talk, we work in the "supercritical" regime and uncover the precise structure of the giant component when it exists, obtaining bounds on the diameter and mixing time of the random walk on the giant which are tight up to polylogarithmic factors. Our techniques involve a variation of core-kernel reduction and analysis of the switch Markov chain. Joint work with Louigi Addario-Berry and Bruce Reed.
