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

About 13 years old · traced to

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)={z∈V(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=A⊔BV=A\sqcup B, whose edges are all triples containing two vertices from AA and one from BB. Let TA,B,C=DA,B∪DB,C∪DC,AT_{A,B,C}=D_{A,B}\cup D_{B,C}\cup D_{C,A} for a tripartition V=A⊔B⊔CV=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.

References

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.