Tuza's conjecture for random graphs

DOI10.1002/RSA.21057MaRDI QIDQ6076736zbMATH OpenOpenAlexWikidataFDO

Authors J. Kahn, Jinyoung Park

Publication date 17 October 2023

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2007.04351

zbMATH Keywords

branching processcouplingrandom graphrandom greedy matchingTuza's conjecture

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random graphs (graph-theoretic aspects) (05C80)

Abstract: A celebrated conjecture of Zs. Tuza says that in any (finite) graph, the minimum size of a cover of triangles by edges is at most twice the maximum size of a set of edge-disjoint triangles. Resolving a recent question of Bennett, Dudek, and Zerbib, we show that this is true for random graphs; more precisely: [ mbox{for any $p=p(n)$, $$G_{n,p}$$ (as $nightarrowinfty$).} ]

Recommendations

• Triangle packing and covering in dense random graphs
• Closing the random graph gap in Tuza's conjecture through the online triangle packing process
• Large triangle packings and Tuza's conjecture in sparse random graphs
• On a conjecture of Tuza about packing and covering of triangles
• Tuza's conjecture is asymptotically tight for dense graphs

Cites work

• A linear programming perspective on the Frankl?R�dl?Pippenger theorem
• A stability theorem on fractional covering of triangles by edges
• Asymptotic packing via a branching process
• scientific article; zbMATH DE number 3891262 (Why is no real title available?)
• scientific article; zbMATH DE number 4170917 (Why is no real title available?)
• scientific article; zbMATH DE number 1131873 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Large triangle packings and Tuza's conjecture in sparse random graphs
• Large triangle-free subgraphs in graphs without \(K_ 4\)
• Matchings and covers in hypergraphs
• Near perfect coverings in graphs and hypergraphs
• Packing and covering triangles in graphs
• Probability on trees and networks
• The probabilistic method
• Upper bounds for the distance in total variation between the binomial or negative binomial and the Poisson distribution

Cited in

(12)

• Triangles in random graphs
• Triangle packing and covering in dense random graphs
• Goldberg's conjecture is true for random multigraphs
• Tuza's conjecture for graphs with maximum average degree less than 7
• Turán's graph theorem, measures and probability theory
• On a Conjecture of Godsil Concerning Controllable Random Graphs
• Large triangle packings and Tuza's conjecture in sparse random graphs
• A generalization of Tuza's conjecture
• A generalized Turán problem in random graphs
• Closing the random graph gap in Tuza's conjecture through the online triangle packing process
• Generalized Tuza's conjecture for random hypergraphs
• Approximate hypergraph vertex cover and generalized Tuza's conjecture

This page was built for publication: Tuza's conjecture for random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6076736)