TY - GEN

T1 - Towards the ErdÅ's-Gallai Cycle Decomposition Conjecture

AU - Bucić, Matija

AU - Montgomery, Richard

N1 - Funding Information:
∗The first author gratefully acknowledges the support of the Oswald Veblen Fund and is in part supported by an NSF Grant CCF-1900460. The second author is supported by the European Research Council (ERC) under the European Union Horizon 2020 research and innovation programme (grant agreement No. 947978) and the Leverhulme trust as well as in part supported by the Centre for Discrete Mathematics and its Applications (DIMAP), University of Warwick.
Publisher Copyright:
© 2023 ACM.

PY - 2023/6/2

Y1 - 2023/6/2

N2 - In the 1960's, ErdÅ's and Gallai conjectured that the edges of any n-vertex graph can be decomposed into O(n) cycles and edges. We improve upon the previous best bound of O(n loglogn) cycles and edges due to Conlon, Fox and Sudakov, by showing an n-vertex graph can always be decomposed into O(n log† n) cycles and edges, where log†n is the iterated logarithm function. Our arguments make use and further develop the theory of robust sublinear expander graphs.

AB - In the 1960's, ErdÅ's and Gallai conjectured that the edges of any n-vertex graph can be decomposed into O(n) cycles and edges. We improve upon the previous best bound of O(n loglogn) cycles and edges due to Conlon, Fox and Sudakov, by showing an n-vertex graph can always be decomposed into O(n log† n) cycles and edges, where log†n is the iterated logarithm function. Our arguments make use and further develop the theory of robust sublinear expander graphs.

KW - Decomposition into expanders

KW - Erdos-Gallai Conjecture

KW - Graph decomposition

KW - Robust sublinear expanders

UR - http://www.scopus.com/inward/record.url?scp=85163111434&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85163111434&partnerID=8YFLogxK

U2 - 10.1145/3564246.3585218

DO - 10.1145/3564246.3585218

M3 - Conference contribution

AN - SCOPUS:85163111434

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 839

EP - 852

BT - STOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing

A2 - Saha, Barna

A2 - Servedio, Rocco A.

PB - Association for Computing Machinery

T2 - 55th Annual ACM Symposium on Theory of Computing, STOC 2023

Y2 - 20 June 2023 through 23 June 2023

ER -