The 3/2 conjecture for triangle covering and packing in random graphs
Let be a random graph with vertices and edges, and let and denote its triangle covering and triangle packing numbers, respectively. For a fixed constant , consider all values of .
The 3/2 random-graph conjecture. For all and , with high probability,
for the full range of .
The conjecture is motivated by estimates suggesting that the ratio grows from about when triangles first emerge to about 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
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.