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 -