The 3/2 conjecture for triangle covering and packing in random graphs

Let G=G(n,m)G=G(n,m) be a random graph with nn vertices and mm edges, and let τ(G)\tau(G) and ν(G)\nu(G) denote its triangle covering and triangle packing numbers, respectively. For a fixed constant C>3/2C>3/2, consider all values of mm.

The 3/2 random-graph conjecture. For all C>3/2C>3/2 and G=G(n,m)G=G(n,m), with high probability,

τ(G)Cν(G)\tau(G)\leq C\cdot\nu(G)

for the full range of mm.

The conjecture is motivated by estimates suggesting that the ratio τ(G)/ν(G)\tau(G)/\nu(G) grows from about 11 when triangles first emerge to about 3/23/2 in denser random graphs. The source gives this as a possible direction for future study and provides no resolution.

Sources & referencesView supporting material

Primary source

Patrick Bennett, Ryan Cushman and Andrzej Dudek, “Closing the Random Graph Gap in Tuza's Conjecture Through the Online Triangle Packing Process”, arXiv:2007.04478 (2020).

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.