Hostname: page-component-78c5997874-v9fdk Total loading time: 0 Render date: 2024-11-17T00:20:02.460Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Part of: Designs and configurations Extremal combinatorics Graph theory

Published online by Cambridge University Press:  22 July 2020

Patrick Bennett ,
Andrzej Dudek  and
Shira Zerbib
Patrick Bennett
Affiliation:
Department of Mathematics, Western Michigan University, Kalamazoo, MI49008, USA
Andrzej Dudek*
Affiliation:
Department of Mathematics, Western Michigan University, Kalamazoo, MI49008, USA
Shira Zerbib
Affiliation:
Department of Mathematics, Iowa State University, Ames, IA50011, USA
*
*Corresponding author. Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The triangle packing number v(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 2v(G) edges intersecting every triangle in G. We show that Tuza’s conjecture holds in the random graph G = G(n, m), when m ⩽ 0.2403n3/2 or m ⩾ 2.1243n3/2. This is done by analysing a greedy algorithm for finding large triangle packings in random graphs.

MSC classification

Primary: 05B40: Packing and covering
Secondary: 05C80: Random graphs 05D40: Probabilistic methods
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 29 , Issue 5 , September 2020 , pp. 757 - 779
Check for updates
Copyright
© The Author(s), 2020. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

†

Supported in part by Simons Foundation Grant #426894.

‡

Supported in part by Simons Foundation Grant #522400.

References

Aharoni, R. and Zerbib, S.A generalization of Tuza’s conjecture. J. Graph Theory. doi:10.1002/jgt.22533.Google Scholar
Alon, N. and Yuster, R. (2005) On a hypergraph matching problem. Graphs Combin. 21 377–384.CrossRefGoogle Scholar
Baron, J. and Kahn, J. (2016) Tuza’s conjecture is asymptotically tight for dense graphs. Combin. Probab. Comput. 25 645–667.CrossRefGoogle Scholar
Basit, A. and Galvin, D. Personal communication.Google Scholar
Bohman, T. (2009) The triangle-free process. Adv. Math. 221 1653–1677.CrossRefGoogle Scholar
Bohman, T., Frieze, A. and Lubetzky, E. (2015) Random triangle removal. Adv. Math. 280 379–438.CrossRefGoogle Scholar
Bohman, T. and Keevash, P. (2013) Dynamic concentration of the triangle-free process. In Seventh European Conference on Combinatorics, Graph Theory and Applications, Vol. 16 of CRM Series, pp. 489–495, Edizioni della Normale.CrossRefGoogle Scholar
Bollobás, B. (1998) To prove and conjecture: Paul Erdös and his mathematics. Amer. Math. Monthly 105 209–237.Google Scholar
Bollobás, B. (2000) The Life and Work of Paul Erdös, Wolf Prize in Mathematics Vol. 1 (Chern, S. S. and Hirzebrunch, F., eds), pp. 292–315, World Scientific.CrossRefGoogle Scholar
Bollobás, B. and Riordan, O. (2009) Random graphs and branching processes. In Handbook of Large-Scale Random Networks, Vol. 18 of Bolyai Society Mathematical Studies, pp. 15–115, Springer.Google Scholar
Erdös, P. (1965) On some extremal problems in graph theory. Israel J. Math. 3 113–116.CrossRefGoogle Scholar
Erdös, P., Suen, S. and Winkler, P. (1995) On the size of a random maximal graph. Random Struct. Algorithms 6 309–318.CrossRefGoogle Scholar
Fiz Pontiveros, G., Griffiths, S. and Morris, R. (2020) The triangle-free process and R(3,k). Mem. Amer. Math. Soc. 263 1274.Google Scholar
Frankl, P. and Rödl, V. (1985) Near perfect coverings in graphs and hypergraphs. European J. Combin. 6 317–326.CrossRefGoogle Scholar
Freedman, D. A. (1975) On tail probabilities for martingales. Ann. Probab. 3 100–118.CrossRefGoogle Scholar
Haxell, P. (1999) Packing and covering triangles in graphs. Discrete Math. 195 251–254.CrossRefGoogle Scholar
Haxell, P. and Rödl, V. (2001) Integer and fractional packings in dense graphs. Combinatorica 21 13–38.CrossRefGoogle Scholar
Janson, S., Łuczak, T. and Ruciński, A. (2009) Random Graphs, Wiley-Interscience.Google Scholar
Krivelevich, M. (1995) On a conjecture of Tuza about packing and covering of triangles. Discrete Math. 142 281–286.CrossRefGoogle Scholar
Makai, T. (2015) The reverse H-free process for strictly 2-balanced graphs. J. Graph Theory 79 125–144.CrossRefGoogle Scholar
Tuza, Z. (1984) A conjecture. In Finite and Infinite Sets (Eger, Hungary 1981) (A. Hajnal et al., eds), Vol. 37 of Proc. Colloq. Math. Soc. J. Bolyai, p. 888, North-Holland.Google Scholar
Warnke, L. (2016) On the method of typical bounded differences. Combin. Probab. Comput. 25 269–299.CrossRefGoogle Scholar
Wormald, N. (1999) The differential equation method for random graph processes and greedy algorithms. In Lectures on Approximation and Randomized Algorithms (M. Karoński and H. J. Prömel, eds), pp. 73–155, PWN.Google Scholar
Yuster, R. (2012) Dense graphs with a large triangle cover have a large triangle packing. Combin. Probab. Comput. 21 952–962.CrossRefGoogle Scholar