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

DOI10.1017/S0963548320000115zbMATH Open1462.05323arXiv1810.11739OpenAlexW3045198963WikidataQ123101908 ScholiaQ123101908MaRDI QIDQ4987259FDOQ4987259

Authors: Patrick Bennett, Andrzej Dudek, Shira Zerbib 

Publication date: 30 April 2021

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

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.

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

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

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)

Cites Work

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