On MaxCut and the Lovász theta function

Balla, Igor; Janzer, Oliver; Sudakov, Benny

doi:10.1090/proc/16675

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