Search

Confirming a conjecture of Vera T. S\'os in a very strong sense, we give a complete solution to Tur\'an's hypergraph problem for the Fano plane. That is we prove for $n\ge 8$ that among all $3$-uniform hypergraphs on $n$ vertices not containing the Fano plane there is indeed exactly one whose number of edges is maximal, namely the balanced, complete, bipartite hypergraph. Moreover, for $n=7$ there is exactly one other extremal configuration with the same number of edges: the hypergraph arising from a clique of order $7$ by removing all five edges containing a fixed pair of vertices. For sufficiently large values $n$ this was proved earlier by F\"uredi and Simonovits, and by Keevash and Sudakov, who utilised the stability method., Comment: revised according to referee reports

For 00, there exists a real constantC=C(l, η), such that almost every random graphG n, p withp=p(n)≥Cn −1+1/2l satisfiesG n,p→1/2+η C 2l+1. In particular, for any fixedl≥1 and η>0, this result implies the existence of very sparse graphsG withG →1/2+η C 2l+1.

0. Notation n=n(G)=number of vertices of the graph G e=e(G)=number of edges of G h=h(G)=number of triangles in G deg (P)=valency (degree) of the vertex P deg,(P)= triangle-valency of P=number of triangles in G adjacent to P t=t(G)=n f deg(P) = 2eln = average valency in G (we will tacitly assume t' 1) T= T(G) =maximum valency in G a=a(G)=maximum size of independent set of vertices (independence or stability number) Kp=shorthana' -for p-clique log x=max {1, In x} to,cl,c2,... are absolute constants when speaking of union, difference or partition of graphs, we work with the vertex-sets