The 3/2 conjecture for triangle covering and packing in random graphs
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.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.