6 solved out of 9 shown

$1000

Let $f(n,k)$ be minimal such that every $\mathcal{F}$ family of $n$-uniform sets with $\lvert F\rvert \geq f(n,k)$ contains a $k$-sunflower. Is it true that
\[f(n,k) < c_k^n\]
for some constant $c_k>0$?

Erdős and Rado [ErRa60] originally proved $f(n,k)\leq (k-1)^nn!$. Kostochka [Ko97] improved this slightly, but the bound stood at $n^{(1+o(1))n}$ for a long time until Alweiss, Lovett, Wu, and Zhang [ALWZ20] proved
\[f(n,k) < (Ck\log n\log\log n)^n\]
for some constant $C>1$. This was refined slightly, independently by Rao [Ra20], Frankston, Kahn, Narayanan and Park [FKNP19], and Bell, Chueluecha and Warnke [BCW21], leading to the current record of
\[f(n,k) < (Ck\log n)^n\]
for some constant $C>1$. The usual focus is on the regime where $k=O(1)$ is fixed (say $k=3$) and $n$ is large, although for the opposite regime Kostochka, Rödl, and Talysheva [KoRoTa99] have shown
\[f(n,k)=(1+O_n(k^{-1/2^n}))k^n.\]

Is it true that for every $C>0$ if $n$ is large enough and $\mathcal{F}$ is an intersecting family of sets of size $n$ with $\lvert \mathcal{F}\rvert \leq Cn$ then there exists a set $S$ with $\lvert S\rvert \leq n-1$ which intersects every $A\in\mathcal{F}$?

Conjectured by Erdős and Lovász [ErLo75], who proved that this holds if $\mathcal{F}\leq \frac{8}{3}n-4$. Disproved by Kahn [Ka94] who constructed an infinite sequence of $\mathcal{F}$, each a family of sets of size $n\to\infty$, such that any set $S$ of size $n-1$ is disjoint from at least one set in $\mathcal{F}$. The Erdős and Lovász constant of $8/3$ has not been improved.

$500

Suppose that we have a family $\mathcal{F}$ of subsets of $[4n]$ such that $\lvert A\rvert=2n$ for all $A\in\mathcal{F}$ and for every $A,B\in \mathcal{F}$ we have $\lvert A\cap B\rvert \geq 2$. Then
\[\lvert \mathcal{F}\rvert \leq \frac{1}{2}\left(\binom{4n}{2n}-\binom{2n}{n}^2\right).\]

Conjectured by Erdős, Ko, and Rado [ErKoRa61]. This inequality would be best possible, as shown by taking $\mathcal{F}$ to be the collection of all subsets of $[4n]$ of size $2n$ containing at least $n+1$ elements from $[2n]$.

Proved by Ahlswede and Khachatrian [AhKh97], who more generally showed the following. Let $2\leq t\leq k\leq m$ and let $r\geq 0$ be such that \[\frac{1}{r+1}\leq \frac{m-2k+2t-2}{(t-1)(k-t+1)}< \frac{1}{r}.\] The largest possible family of subsets of $[m]$ of size $k$, such that the pairwise intersections have size at least $t$, is the family of all subsets of $[m]$ of size $k$ which contain at least $t+r$ elements from $\{1,\ldots,t+2r\}$.

$500

Let $\alpha>0$ and $n,t\geq 1$ be integers. Let $F^{(t)}(n,\alpha)$ be the largest $k$ such that the following holds.

Let $\lvert S\rvert=n$ and 2-colour all $t$-subsets of $S$. For every $X\subseteq S$ of size at least $k$ there are at least $\alpha \binom{\lvert X\rvert}{t}$ many $t$-subsets of $X$ of each colour.

For fixed $n,t$ as we change $\alpha$ from $0$ to $1/2$ does $F^{(t)}(n,\alpha)$ increase continuously or are there jumps? Only one jump?

For $\alpha=0$ this is the usual Ramsey function. A conjecture of Erdős, Rado, and Hajnal implies that
\[ F^{(t)}(n,0)\asymp \log_{t-1} n\]
and results of Erdős and Spencer imply that
\[F^{(t)}(n,\alpha) \asymp_\alpha (\log n)^{\frac{1}{t-1}}\]
for $\alpha$ close to $1/2$.

Let $\alpha>0$ and $n\geq 1$. Let $F(n,\alpha)$ be the largest $k$ such that in any 2-colouring of the edges of $K_n$ any subgraph $H$ on at least $k$ vertices contains more than $\alpha\binom{\lvert H\rvert}{2}$ many edges of each colour.

Prove that for every fixed $0\leq \alpha \leq 1/2$, as $n\to\infty$, \[F(n,\alpha)\sim c_\alpha \log n\] for some constant $c_\alpha$.

It is easy to show with the probabilistic method that there exist $c_1(\alpha),c_2(\alpha)$ such that
\[c_1(\alpha)\log n < F(n,\alpha) < c_2(\alpha)\log n.\]

For any $g\geq 2$, if $n$ is sufficiently large and $\equiv 1,3\pmod{6}$ then there exists a 3-uniform hypergraph on $n$ vertices such that

- every pair of vertices is contained in exactly one edge (i.e. the graph is a Steiner triple system) and
- for any $2\leq j\leq g$ any collection of $j$ edges contains at least $j+3$ vertices.

Proved by Kwan, Sah, Sawhney, and Simkin [KSSS22b].

How large can a union-free collection $\mathcal{F}$ of subsets of $[n]$ be? By union-free we mean there are no solutions to $A\cup B=C$ with distinct $A,B,C\in \mathcal{F}$. Must $\lvert \mathcal{F}\rvert =o(2^n)$? Perhaps even
\[\lvert \mathcal{F}\rvert <(1+o(1))\binom{n}{\lfloor n/2\rfloor}?\]

The estimate $\lvert \mathcal{F}\rvert=o(2^n)$ implies that if $A\subset \mathbb{N}$ is a set of positive density then there are infinitely many distinct $a,b,c\in A$ such that $[a,b]=c$ (i.e. [487]).

Solved by Kleitman [Kl71], who proved \[\lvert \mathcal{F}\rvert <(1+o(1))\binom{n}{\lfloor n/2\rfloor}.\]

How many antichains in $[n]$ are there? That is, how many families of subsets of $[n]$ are there such that, if $\mathcal{F}$ is such a family and $A,B\in \mathcal{F}$, then $A\not\subseteq B$?

Sperner's theorem states that $\lvert \mathcal{F}\rvert \leq \binom{n}{\lfloor n/2\rfloor}$. This is also known as Dedekind's problem.

Resolved by Kleitman [Kl69], who proved that the number of such families is \[2^{(1+o(1))\binom{n}{\lfloor n/2\rfloor}}.\]