Large triangle packings and Tuza's conjecture in sparse random graphs

DOI10.1017/S0963548320000115MaRDI QIDQ4987259zbMATH OpenOpenAlexWikidataFDO

Authors Patrick Bennett, Andrzej Dudek, Shira Zerbib

Publication date 30 April 2021

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

greedy algorithmlarge triangle packings in random graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Distance in graphs (05C12) Density (toughness, etc.) (05C42) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: The triangle packing number $u(G)$ of a graph $G$ is the maximum size of a set of edge-disjoint triangles in $G$. Tuza conjectured that in any graph $G$ there exists a set of at most $2u(G)$ edges intersecting every triangle in $G$. We show that Tuza's conjecture holds in the random graph $G=G(n,m)$, when $mle0.2403n^{3/2}$ or $mge2.1243n^{3/2}$. This is done by analyzing a greedy algorithm for finding large triangle packings in random graphs.

Recommendations

• Closing the random graph gap in Tuza's conjecture through the online triangle packing process
• Triangle packing and covering in dense random graphs
• Tuza's conjecture for random graphs
• On a conjecture of Tuza about packing and covering of triangles
• Dense graphs with a large triangle cover have a large triangle packing

Cites work

• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 1405894 (Why is no real title available?)
• A generalization of Tuza's conjecture
• Dense graphs with a large triangle cover have a large triangle packing
• Dynamic concentration of the triangle-free process
• Handbook of large-scale random networks
• Integer and fractional packings in dense graphs
• Near perfect coverings in graphs and hypergraphs
• On a conjecture of Tuza about packing and covering of triangles
• On a hypergraph matching problem
• On some extremal problems in graph theory
• On tail probabilities for martingales
• On the method of typical bounded differences
• On the size of a random maximal graph
• Packing and covering triangles in graphs
• Random triangle removal
• The reverse \(H\)-free process for strictly 2-balanced graphs
• The triangle-free process
• The triangle-free process and the Ramsey number \(R(3,k)\)
• To Prove and Conjecture: Paul Erdos and His Mathematics
• Tuza's conjecture is asymptotically tight for dense graphs

Cited in

(8)

• A note on the random greedy triangle-packing algorithm
• Triangle packing and covering in dense random graphs
• Tuza's conjecture is asymptotically tight for dense graphs
• Tuza's conjecture for random graphs
• Dense graphs with a large triangle cover have a large triangle packing
• The sum-free process
• Corrádi and Hajnal's theorem for sparse random graphs
• Closing the random graph gap in Tuza's conjecture through the online triangle packing process

This page was built for publication: Large triangle packings and Tuza's conjecture in sparse random graphs

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