TY - GEN

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

AU - Bucić, Matija

AU - Montgomery, Richard

N1 - 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 -