Bohman–Frieze–Mubayi–Pikhurko's codegree density conjecture for F3,2F_{3,2}

Let F3,2F_{3,2} be the 33-graph in the paper whose-free condition is equivalent to having independent joint neighbourhoods: for distinct vertices x,yx,y, define

Γ(x,y)={zV(G):{x,y,z}E(G)}.\Gamma(x,y)=\{z\in V(G):\{x,y,z\}\in E(G)\}.

A 33-graph has independent neighbourhoods when every such joint neighbourhood is edge-free. Let DA,BD_{A,B} be the one-way bipartite 33-graph associated with a bipartition V=ABV=A\sqcup B, whose edges are all triples containing two vertices from AA and one from BB. Let TA,B,C=DA,BDB,CDC,AT_{A,B,C}=D_{A,B}\cup D_{B,C}\cup D_{C,A} for a tripartition V=ABCV=A\sqcup B\sqcup C.

Bohman–Frieze–Mubayi–Pikhurko's conjecture. The balanced construction TA,B,CT_{A,B,C} is asymptotically optimal for the codegree problem for F3,2F_{3,2}; equivalently,

γ(F3,2)=13.\gamma(F_{3,2})=\frac{1}{3}.

The construction has independent neighbourhoods and codegree approximately n/3n/3 when the three parts are as equal as possible, giving the lower bound. The conjecture asserts that this lower bound is tight for the codegree density.

Sources & referencesView supporting material

Primary source

Victor Falgas-Ravry, Edward Marchant, Oleg Pikhurko and Emil Vaughan, “The codegree threshold for 3-graphs with independent neighbourhoods”, arXiv:1307.0075 (2015).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.