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 -