On $P_4$-intersecting families of graphs
arXiv.org
On $P_4$-intersecting families of graphs
Given a graph $F$, a family $\mathcal F$ of graphs on $[n]$ is \emph{$F$-intersecting} if $G\cap H$ contains a copy of $F$ for every $G,H\in\mathcal F$. We prove that there exists an absolute constant $\varepsilon>0$ such that every $P_4$-intersecting family $\mathcal F$ satisfies $|\mathcal F|\le\left(\frac12-\varepsilon\right)2^{\binom n2}$, which resolves a conjecture of Alon. Combined with Alon's reduction, this proves that a graph $F$ admits $F$-intersecting families of asymptotic density $1/2$ if and only if $F$ is a star forest.
0 comments
No comments yet.