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

About 6 years old · traced to

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.

References

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.