Georgia Institute of Technology College of Sciences

Given an $r$-uniform hypergraph $H$, the random Turán number $\mathrm{ex}(G^r_{n,p},H)$ is the maximum number of edges in an $H$-free subgraph of $G^r_{n,p}$, where $G^r_{n,p}$ is the Erdős-Rényi random hypergraph with parameter $p$. In the case when $H$ is not r-partite, the problem has been essentially solved independently by Conlon-Gowers and Schacht. In the case when $H$ is $r$-partite, the degenerate case, only some sporadic results are known.

The Sidorenko conjecture is a notorious problem in extremal combinatorics. It is known that its hypergraph analog is not true. Recently, Conlon, Lee, and Sidorenko discovered a relation between the Sidorenko conjecture and the Turán problem. 

 In this talk, we introduce some recent results on the degenerate random Turan problem and its relation to the hypergraph analog of the Sidorenko conjecture.

In this talk, the speaker will present three applications of information theory in applied spaces. No background on information theory, hypergraphs, or RF signals analysis will be assumed. Bill Kay is a pure mathematician in combinatorics by training who now lives in an applied space at Pacific Northwest National Laboratory.

Let $d\geq 2$, and $n\geq 2d+2$. Frankl and Pach initiated the study of the maximum size of a $(d+1)$-uniform set system in $[n]$ with VC-dimension at most $d$. The best-known upper bound is essentially $\binom{n}{d}$, and the best-known lower bound is $\binom{n-1}{d} + \binom{n-4}{d-2}$. In this talk, I will discuss some recent improvements on the upper bound and some interesting connections between this problem and the celebrated Erdős--Ko--Rado theorem. In particular, I will discuss our conjecture, which can be viewed as a generalization of the EKR as well as an "uniform version" of the disproved Erdős--Frankl--Pach conjecture, and highlight some of our partial progress. Joint work with Ting-Wei Chao, Zixiang Xu, and Shengtong Zhang.

A basic result of probabilistic combinatorics, originally due to Erdős and Rényi, is the determination of the threshold at which the random graph $G_{n,p}$ contains a triangle with high probability. But one can also ask more refined versions of this question, where we ask not just for one triangle but for many triangles which interact in complicated ways. For example, what is the threshold at which we can no longer partition $G_{n,p}$ into two triangle-free subgraphs?


In this talk, I will discuss the proof of the Kohayakawa–Kreuter conjecture, which gives a general answer to all such questions. Rather surprisingly, a key step of the proof is a purely deterministic graph decomposition statement, closely related to classical results such as Nash-Williams' tree decomposition theorem, whose proof uses techniques from combinatorial optimization and structural graph theory.

Based on joint works with Micha Christoph, Eden Kuperwasser, Anders Martinsson, Wojciech Samotij, and Raphael Steiner.