Problems in Extremal and Probabilistic Combinatorics

We study the following four problems in extremal and probabilistic combinatorics: 1. A sunflower is a collection of distinct sets such that the intersection of any two of them is the same as the common intersection $C$ of all of them, and $|C|$ is smaller than each of the sets. We consider the problems of determining the maximum sum and product of $k$ families of subsets of $[n]$ that contain no sunflower of size $k$ with one set from each family. For the sum, we prove that the maximum is $$(k-1)2^n+1+\sum_{s=0}^{k-2}\binom{n}{s}$$ for all $n \ge k \ge 3$, and for the $k=3$ case of the product, we prove that the maximum is $$\left(\frac{1}{8}+o(1)\right)2^{3n}.$$ We conjecture that for all fixed $k\ge 3$, the maximum product is $(1/8+o(1))2^{kn}$. 2. For $k \ge 4$, a loose $k$-cycle $C_k$ is a hypergraph with distinct edges $e_1, e_2, \ldots, e_k$ such that consecutive edges (modulo $k$) intersect in exactly one vertex and all other pairs of edges are disjoint. Our main result is that for every even integer $k \ge 4$, there exists $c>0$ such that the number of triple systems with vertex set $[n]$ containing no $C_{k}$ is at most $2^{cn^2}$. An easy construction shows that the exponent is sharp in order of magnitude. Our proof method is different than that used for most recent results of a similar flavor about enumerating discrete structures, since it does not use hypergraph containers. One novel ingredient is the use of some (new) quantitative estimates for an asymmetric version of the bipartite canonical Ramsey theorem. 3. For $p \in [0,1]$ and an integer $n$, let $Q(n,p)$ be the random set system, obtained by picking each subset of $[n]$ independently with probability $p$. We prove that for many configurations $\F$ that arise naturally in extremal set theory there is a threshold probability $p_0$ such that if $p \ll p_0$ then asymptotically almost surely $Q(n,p)$ contains no member of $\F$ while if $p \gg p_0$ then asymptotically almost surely $Q(n,p)$ contains many members of $\F$. Our general results imply that $p_0=(t+1)^{-n/t}$ is the threshold for the appearance of a matching of size $t$ and is also a threshold for the appearance a chain of size of size $t$. This generalizes results of R\'enyi from 1961 who answered a question of Erd\H os by solving these two problems for $t=2$. R\'enyi observed that his approach did not work for larger $t$ for either a matching or chain. We overcome this problem by using the second moment method on a more restricted class of configurations than the entire family $\F$. Our general result also determines the threshold for the appearance of a sunflower of size $t$ and several other configurations. 4. A family $\A\subset 2^{[n]}$ is intersecting if $A\cap B
eq \emptyset$ for all $A, B\in \A$. We prove that if $p=2^{-\Theta(\sqrt{n}\log n)}$, the maximum intersecting family in the random set system $Q(n, p)$ is $(1+o(1))p 2^{n-1}$. This is a continuation of the work by Balogh, Bohman and Mubayi who proved the random version of the Erd\H{o}s--Ko--Rado theorem in 2009. The proof takes advantage of the hypergraph container method developed independently by Saxton and Thomason, and by Balogh--Morris--Samotij.