On MaxCut and the Lovász theta function
HTML articles powered by AMS MathViewer
- by Igor Balla, Oliver Janzer and Benny Sudakov;
- Proc. Amer. Math. Soc. 152 (2024), 1871-1879
- DOI: https://doi.org/10.1090/proc/16675
- Published electronically: March 7, 2024
- HTML | PDF | Request permission
Abstract:
In this short note we prove a lower bound for the MaxCut of a graph in terms of the Lovász theta function of its complement. We combine this with known bounds on the Lovász theta function of complements of $H$-free graphs to recover many known results on the MaxCut of $H$-free graphs. In particular, we give a new, very short proof of a conjecture of Alon, Krivelevich and Sudakov about the MaxCut of graphs with no cycles of length $r$.References
- Noga Alon, Explicit Ramsey graphs and orthonormal labelings, Electron. J. Combin. 1 (1994), Research Paper 12, approx. 8. MR 1302331, DOI 10.37236/1192
- Noga Alon, Bipartite subgraphs, Combinatorica 16 (1996), no. 3, 301–311. MR 1417340, DOI 10.1007/BF01261315
- Noga Alon, Béla Bollobás, Michael Krivelevich, and Benny Sudakov, Maximum cuts and judicious partitions in graphs without short cycles, J. Combin. Theory Ser. B 88 (2003), no. 2, 329–346. MR 1983363, DOI 10.1016/S0095-8956(03)00036-4
- Noga Alon and Nabil Kahale, Approximating the independence number via the $\theta$-function, Math. Programming 80 (1998), no. 3, Ser. A, 253–264. MR 1603356, DOI 10.1007/BF01581168
- Noga Alon, Michael Krivelevich, and Benny Sudakov, MaxCut in $H$-free graphs, Combin. Probab. Comput. 14 (2005), no. 5-6, 629–647. MR 2174649, DOI 10.1017/S0963548305007017
- Noga Alon, Konstantin Makarychev, Yury Makarychev, and Assaf Naor, Quadratic forms on graphs, Invent. Math. 163 (2006), no. 3, 499–522. MR 2207233, DOI 10.1007/s00222-005-0465-9
- Noga Alon and Mario Szegedy, Large sets of nearly orthogonal vectors, Graphs Combin. 15 (1999), no. 1, 1–4. MR 1684496, DOI 10.1007/PL00021187
- I. Balla. Orthonormal representations, vector chromatic number, and extension complexity. arXiv:2310:17482, 2023.
- Igor Balla, Shoham Letzter, and Benny Sudakov, Orthonormal representations of $H$-free graphs, Discrete Comput. Geom. 64 (2020), no. 3, 654–670. MR 4156242, DOI 10.1007/s00454-020-00185-0
- Charles Carlson, Alexandra Kolla, Ray Li, Nitya Mani, Benny Sudakov, and Luca Trevisan, Lower bounds for max-cut in $H$-free graphs via semidefinite programming, SIAM J. Discrete Math. 35 (2021), no. 3, 1557–1568. MR 4283107, DOI 10.1137/20M1333985
- M. Charikar and A. Wirth, Maximizing quadratic programs: extending Grothendieck’s inequality, 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 54–60. IEEE, 2004.
- C. Delorme and S. Poljak, Laplacian eigenvalues and the maximum cut problem, Math. Programming 62 (1993), no. 3, Ser. A, 557–574. MR 1251892, DOI 10.1007/BF01585184
- Reinhard Diestel, Graph theory, 4th ed., Graduate Texts in Mathematics, vol. 173, Springer, Heidelberg, 2010. MR 2744811, DOI 10.1007/978-3-642-14279-6
- C. S. Edwards, Some extremal properties of bipartite subgraphs, Canadian J. Math. 25 (1973), 475–485. MR 337686, DOI 10.4153/CJM-1973-048-x
- C. S. Edwards, An improved lower bound for the number of edges in a largest bipartite subgraph, Recent advances in graph theory (Proc. Second Czechoslovak Sympos., Prague, 1974) Academia, Prague, 1975, pp. 167–181. MR 398888
- Paul Erdős, Problems and results in graph theory and combinatorial analysis, Graph theory and related topics (Proc. Conf., Univ. Waterloo, Waterloo, Ont., 1977) Academic Press, New York-London, 1979, pp. 153–163. MR 538043
- Jacob Fox, Zoe Himwich, and Nitya Mani, Making an $H$-free graph $k$-colorable, J. Graph Theory 102 (2023), no. 2, 234–261. MR 4529832, DOI 10.1002/jgt.22868
- S. Glock, O. Janzer, and B. Sudakov, New results for MaxCut in $H$-free graphs, J. Lond. Math. Soc. (2) 108 (2023), no. 2, 441–481.
- Michel X. Goemans and David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. Assoc. Comput. Mach. 42 (1995), no. 6, 1115–1145. MR 1412228, DOI 10.1145/227683.227684
- David Karger, Rajeev Motwani, and Madhu Sudan, Approximate graph coloring by semidefinite programming, J. ACM 45 (1998), no. 2, 246–265. MR 1623197, DOI 10.1145/274787.274791
- Donald E. Knuth, The sandwich theorem, Electron. J. Combin. 1 (1994), Article 1, approx. 48. MR 1269161, DOI 10.37236/1193
- László Lovász, On the Shannon capacity of a graph, IEEE Trans. Inform. Theory 25 (1979), no. 1, 1–7. MR 514926, DOI 10.1109/TIT.1979.1055985
- Alexandre Megretski, Relaxations of quadratic programs in operator theory and system analysis, Systems, approximation, singular integral operators, and related topics (Bordeaux, 2000) Oper. Theory Adv. Appl., vol. 129, Birkhäuser, Basel, 2001, pp. 365–392. MR 1882703
- Alexander Schrijver, A comparison of the Delsarte and Lovász bounds, IEEE Trans. Inform. Theory 25 (1979), no. 4, 425–429. MR 536232, DOI 10.1109/TIT.1979.1056072
- James B. Shearer, A note on bipartite subgraphs of triangle-free graphs, Random Structures Algorithms 3 (1992), no. 2, 223–226. MR 1151364, DOI 10.1002/rsa.3240030211
- M. Szegedy, A note on the $\theta$ number of Lovász and the generalized Delsarte bound, Proceedings 35th Annual Symposium on Foundations of Computer Science, pp. 36–39. IEEE, 1994.
- Qinghou Zeng and Jianfeng Hou, Maximum cuts of graphs with forbidden cycles, Ars Math. Contemp. 15 (2018), no. 1, 147–160. MR 3862083, DOI 10.26493/1855-3974.1218.5ed
Bibliographic Information
- Igor Balla
- Affiliation: Einstein Institute of Mathematics, Hebrew University of Jerusalem, Israel
- MR Author ID: 1005527
- Email: iballa1990@gmail.com
- Oliver Janzer
- Affiliation: Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, United Kingdom
- MR Author ID: 1331649
- Email: oj224@cam.ac.uk
- Benny Sudakov
- Affiliation: Department of Mathematics, ETH Zürich, Switzerland
- MR Author ID: 602546
- ORCID: 0000-0003-3307-9475
- Email: benjamin.sudakov@math.ethz.ch
- Received by editor(s): June 5, 2023
- Received by editor(s) in revised form: August 28, 2023, and September 10, 2023
- Published electronically: March 7, 2024
- Additional Notes: The second author was supported by a fellowship at Trinity College
The third author was supported in part by SNSF grant 200021_196965. - Communicated by: Isabella Novik
- © Copyright 2024 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 152 (2024), 1871-1879
- MSC (2020): Primary 05C35, 05C50
- DOI: https://doi.org/10.1090/proc/16675
- MathSciNet review: 4728458