solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看7461次
A Note on Large H-Intersecting Families. (arXiv:1609.01884v2 [math.CO] UPDATED)
来源于:arXiv
A family $F$ of graphs on a fixed set of $n$ vertices is called
triangle-intersecting if for any $G_1,G_2 \in F$, the intersection $G_1 \cap
G_2$ contains a triangle. More generally, for a fixed graph $H$, a family $F$
is $H$-intersecting if the intersection of any two graphs in $F$ contains a
sub-graph isomorphic to $H$.
In [D. Ellis, Y. Filmus, and E. Friedgut, Triangle-intersecting families of
graphs, J. Eur. Math. Soc. 14 (2012), pp. 841--885], Ellis, Filmus and Friedgut
proved a 36-year old conjecture of Simonovits and S\'{o}s stating that the
maximal size of a triangle-intersecting family is $(1/8)2^{n(n-1)/2}$.
Furthermore, they proved a $p$-biased generalization, stating that for any $p
\leq 1/2$, we have $\mu_{p}(F)\le p^{3}$, where $\mu_{p}(F)$ is the probability
that the random graph $G(n,p)$ belongs to $F$.
In the same paper, Ellis et al. conjectured that the assertion of their
biased theorem holds also for $1/2 < p \le 3/4$, and more generally, that for
any non-$t$-colo 查看全文>>