A sum of squares characterization of perfect graphs. (English) Zbl 1527.05076
In this paper, the authors present an algebraic characterization of perfect graphs, i.e., graphs for which the clique number and the chromatic number coincide for every induced subgraph, and show that a graph is perfect if and only if certain nonnegative polynomials associated with the graph are sums of squares (sos). As a byproduct, several infinite families of nonnegative polynomials that are not sums of squares are obtained through graph-theoretic constructions. Graphs for which the associated polynomials belong to certain structured subsets of the sum of squares polynomials are also characterized. Finally, some well-known results from the theory of perfect graphs are reformulated as statements about the sum of squares proofs of nonnegativity of certain polynomials. Future research directions conclude the paper.
Reviewer: Ioan Tomescu (Bucureşti)
MSC:
| 05C17 | Perfect graphs |
| 05C31 | Graph polynomials |
| 90C22 | Semidefinite programming |
| 26D05 | Inequalities for trigonometric functions and polynomials |
Keywords:
nonnegative and sum of squares polynomials; perfect graphs; matrix copositivity; semidefinite programming; convex relaxations for the clique numberSoftware:
SPOTlessReferences:
| [1] | Ahmadi, A. A., Dash, S., and Hall, G., Optimization over structured subsets of positive semidefinite matrices via column generation, Discrete Optim., 24 (2017), pp. 129-151. · Zbl 1387.90179 |
| [2] | Ahmadi, A. A. and Majumdar, A., DSOS and SDSOS optimization: More tractable alternatives to sum of squares and semidefinite optimization, SIAM J. Appl. Algebra Geom., 3 (2019), pp. 193-230, doi:10.1137/18M118935X. · Zbl 1465.90061 |
| [3] | Artin, E., Über die Zerlegung Definiter Funktionen in Quadrate, Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 5 (1927), pp. 100-115. · JFM 52.0122.01 |
| [4] | Berge, C., Färbung von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe, 10 (1961), pp. 114-114. |
| [5] | Bland, R. G., Huang, H.-C., and Trotter,, L. E. Jr., Graphical properties related to minimal imperfection, Discrete Math., 27 (1979), pp. 11-22. · Zbl 0421.05028 |
| [6] | Blekherman, G., There are significantly more nonnegative polynomials than sums of squares, Israel J. Math., 153 (2006), pp. 355-380. · Zbl 1139.14044 |
| [7] | Blekherman, G., Convex Forms that Are Not Sums of Squares, preprint, https://arxiv.org/abs/0910.0656, 2009. |
| [8] | Blekherman, G., Parrilo, P. A., and Thomas, R. R., Semidefinite Optimization and Convex Algebraic Geometry, SIAM, Philadelphia, 2012, doi:10.1137/1.9781611972290. · Zbl 1260.90006 |
| [9] | Bollobás, B., Random Graphs, 2nd ed., Cambridge University Press, Cambridge, 2001. · Zbl 0979.05003 |
| [10] | Bomze, I. M., Dür, M., de Klerk, E., Roos, C., Quist, A. J., and Terlaky, T., On copositive programming and standard quadratic optimization problems, J. Global Optim., 18 (2000), pp. 301-320. · Zbl 0970.90057 |
| [11] | Bomze, I. M., Frommlet, F., and Locatelli, M., Gap, cosum and product properties of the \(\theta^{\prime }\) bound on the clique number, Optimization, 59 (2010), pp. 1041-1051. · Zbl 1214.05102 |
| [12] | Brouwer, A. E. and Haemers, W. H., Spectra of Graphs, Springer, New York, 2012. · Zbl 1231.05001 |
| [13] | Choi, M. D. and Lam, T. Y., An Old Question of Hilbert, , Queen’s University, Kingston, ON, 1977, pp. 385-405. · Zbl 0382.12010 |
| [14] | Choi, M. D. and Lam, T. Y., Extremal positive semidefinite forms, Math. Ann., 231 (1977), pp. 1-18. · Zbl 0347.15009 |
| [15] | Choi, M. D., Lam, T. Y., and Reznick, B., Real zeros of positive semidefinite forms. I, Math. Z., 171 (1980), pp. 1-26. · Zbl 0415.10018 |
| [16] | Choi, M.-D., Lam, T.-Y., and Reznick, B., Even symmetric sextics, Math. Z., 195 (1987), pp. 559-580. · Zbl 0654.10024 |
| [17] | Choi, M. D., Lam, T. Y., and Reznick, B., Sums of squares of real polynomials, in Proc. Sympos. Pure Math. 58, AMS, Providence, RI, 1995, pp. 103-126. · Zbl 0821.11028 |
| [18] | Chudnovsky, M., Robertson, N., Seymour, P., and Thomas, R., Progress on perfect graphs, Math. Program., 97 (2003), pp. 405-422. · Zbl 1028.05035 |
| [19] | Chudnovsky, M., Robertson, N., Seymour, P., and Thomas, R., The strong perfect graph theorem, Ann. Math., 164 (2006), pp. 51-229. · Zbl 1112.05042 |
| [20] | Chvátal, V., On certain polytopes associated with graphs, J. Combin. Theory B, 18 (1975), pp. 138-154. · Zbl 0277.05139 |
| [21] | Chvátal, V., Graham, R. L., Perold, A. F., and Whitesides, S., Combinatorial designs related to the strong perfect graph conjecture, Discrete Math., 26 (1979), pp. 83-92. · Zbl 0403.05017 |
| [22] | Coja-Oghlan, A., The Lovász number of random graphs, Combin. Probab. Comput., 14 (2005), pp. 439-465. · Zbl 1076.05072 |
| [23] | Csiszár, I., Körner, J., Lovász, L., Marton, K., and Simonyi, G., Entropy splitting for antiblocking corners and perfect graphs, Combinatorica, 10 (1990), pp. 27-40. · Zbl 0734.05061 |
| [24] | Cubitt, T., Mančinska, L., Roberson, D. E., Severini, S., Stahlke, D., and Winter, A., Bounds on entanglement-assisted source-channel coding via the Lovász \(\vartheta\) number and its variants, IEEE Trans. Inform. Theory, 60 (2014), pp. 7330-7344. · Zbl 1360.81053 |
| [25] | Cvetković, D. M., Doob, M., and Sachs, H., Spectra of Graphs: Theory and Application, Academic Press, New York, 1980. · Zbl 0458.05042 |
| [26] | Dickinson, P. J. and de Zeeuw, R., Generating irreducible copositive matrices using the stable set problem, Discrete Appl. Math., 296 (2021), pp. 103-117. · Zbl 1462.05218 |
| [27] | De Klerk, E. and Pasechnik, D. V., Approximation of the stability number of a graph via copositive programming, SIAM J. Optim., 12 (2002), pp. 875-892, doi:10.1137/S1052623401383248. · Zbl 1035.90058 |
| [28] | Došlic, T., Ghorbani, M., and Hosseinzadeh, M. A., The relationships between Wiener index, stability number and clique number of composite graphs, Bull. Malays. Math. Sci. Soc., 36 (2013), pp. 165-172. · Zbl 1259.05054 |
| [29] | Drew, J. H. and Johnson, C. R., The no long odd cycle theorem for completely positive matrices, in Random Discrete Structures, Springer, New York, 1996, pp. 103-115. · Zbl 0838.15011 |
| [30] | El Khadir, B., On sum of squares representation of convex forms and generalized Cauchy-Schwarz inequalities, SIAM J. Appl. Algebra Geom., 4 (2020), pp. 377-400. · Zbl 1440.14266 |
| [31] | Erdős, P. and Rényi, A., On random graphs I, Publ. Math. Debrecen, 6 (1959), pp. 290-297. · Zbl 0092.15705 |
| [32] | Frobenius, G., Über Matrizen aus nicht negativen Elementen, S.B. Preuss Acad. Wiss., 26 (1912), pp. 456-477. · JFM 43.0204.09 |
| [33] | Fulkerson, D. R., Blocking and anti-blocking pairs of polyhedra, Math. Program., 1 (1971), pp. 168-194. · Zbl 0254.90054 |
| [34] | Gasparian, G. S., Minimal imperfect graphs: A simple approach, Combinatorica, 16 (1996), pp. 209-212. · Zbl 0858.05044 |
| [35] | Gerke, S. and McDiarmid, C., Graph imperfection I, II, J. Combin. Theory B, 83 (2001), pp. 79-101. · Zbl 1018.05027 |
| [36] | Gershgorin, S. A., Über die Abgrenzung der Eigenwerte einer Matrix, Bulletin de l’Académie des Sciences de l’URSS, Classe des sciences mathématiques et na, (1931), pp. 749-754. · Zbl 0003.00102 |
| [37] | Godsil, C., Roberson, D. E., Šámal, R., and Severini, S., Sabidussi versus Hedetniemi for three variations of the chromatic number, Combinatorica, 36 (2016), pp. 395-415. · Zbl 1389.05040 |
| [38] | Gouveia, J., Kovačec, A., and Saee, M., On sums of squares of \(k\)-nomials, J. Pure Appl. Algebra, 226 (2022), 106820. · Zbl 1477.13048 |
| [39] | Gouveia, J., Parrilo, P. A., and Thomas, R. R., Theta bodies for polynomial ideals, SIAM J. Optim., 20 (2010), pp. 2097-2118, doi:10.1137/090746525. · Zbl 1213.90190 |
| [40] | Gouveia, J., Pong, T. K., and Saee, M., Inner approximating the completely positive cone via the cone of scaled diagonally dominant matrices, J. Global Optim., 76 (2020), pp. 383-405. · Zbl 1435.90114 |
| [41] | Grötschel, M., Lovász, L., and Schrijver, A., The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1 (1981), pp. 169-197. · Zbl 0492.90056 |
| [42] | Grötschel, M., Lovász, L., and Schrijver, A., Geometric Algorithms and Combinatorial Optimization, Springer-Verlag, Berlin, 1988. · Zbl 0634.05001 |
| [43] | Hall, G., Applications of sum of squares polynomials, in Sum of Squares: Theory and Applications, Proceedings of Symposia in Applied Mathematics, 77, AMS, Providence, RI, 2020. |
| [44] | Hanson, B. and Petridis, G., Refined estimates concerning sumsets contained in the roots of unity, Proc. Lond. Math. Soc. 3, 122 (2021), pp. 353-358. · Zbl 1497.11029 |
| [45] | Hilbert, D., Über die Darstellung Definiter Formen als Summe von Formenquadraten, Math. Ann., 32 (1888), pp. 342-350. · JFM 20.0198.02 |
| [46] | Kuang, X., Ghaddar, B., Naoum-Sawaya, J., and Zuluaga, L. F., Alternative LP and SOCP hierarchies for ACOPF problems, IEEE Trans. Power Syst., 32 (2016), pp. 2828-2836. |
| [47] | Lasserre, J. B., Global optimization with polynomials and the problem of moments, SIAM J. Optim., 11 (2001), pp. 796-817, doi:10.1137/S1052623400366802. · Zbl 1010.90061 |
| [48] | Lasserre, J. B., Moments, Positive Polynomials and Their Applications, , Imperial College Press, London, 2010. · Zbl 1211.90007 |
| [49] | Laurent, M., Sums of squares, moment matrices and optimization over polynomials, in Emerging Applications of Algebraic Geometry, Springer, New York, 2009, pp. 157-270. · Zbl 1163.13021 |
| [50] | Laurent, M. and Vargas, L. F., Finite convergence of sum-of-squares hierarchies for the stability number of a graph, SIAM J. Optim., 32 (2022), pp. 491-518, doi:10.1137/21M140345X. · Zbl 1487.05259 |
| [51] | Laurent, M. and Vargas, L. F., Exactness of Parrilo’s Conic Approximations for Copositive Matrices and Associated Low Order Bounds for the Stability Number of a Graph, preprint, https://arxiv.org/abs/2109.12876, 2021. |
| [52] | Laurent, M. and Vargas, L. F., On the exactness of sum-of-squares approximations for the cone of \(5\times 5\) copositive matrices, Linear Algebra Appl., 651 (2022), pp. 26-50. · Zbl 1493.90127 |
| [53] | Lovász, L., Normal hypergraphs and the perfect graph conjecture, Discrete Math., 2 (1972), pp. 253-267. · Zbl 0239.05111 |
| [54] | Lovász, L., A characterization of perfect graphs, J. Combin. Theory B, 13 (1972), pp. 95-98. · Zbl 0241.05107 |
| [55] | Lovász, L., On the Shannon capacity of a graph, IEEE Trans. Inform. Theory, 25 (1979), pp. 1-7. · Zbl 0395.94021 |
| [56] | Lovász, L., Perfect graphs, in Selected Topics in Graph Theory 2, Beineke, L. W. and Wilson, R. J., eds., Academic Press, 1983, pp. 55-87. · Zbl 0536.05055 |
| [57] | McEliece, R. J., Rodemich, E. R., and Rumsey, H. C. Jr., The Lovász bound and some generalizations, J. Combin. Inform. Syst. Sci., 3 (1978), pp. 134-152. · Zbl 0408.05031 |
| [58] | Motzkin, T., The arithmetic-geometric inequality, in Proceedings of Symposium on Inequalities, , Academic Press, New York, London, 1967, pp. 205-224. |
| [59] | Motzkin, T. S. and Straus, E. G., Maxima for graphs and a new proof of a theorem of Turán, Canad. J. Math., 17 (1965), pp. 533-540. · Zbl 0129.39902 |
| [60] | Murray, R., Chandrasekaran, V., and Wierman, A., Signomial and polynomial optimization via relative entropy and partial dualization, Math. Program. Comput., 13 (2021), pp. 257-295. · Zbl 1530.90071 |
| [61] | Murty, K. G. and Kabadi, S. N., Some NP-complete problems in quadratic and nonlinear programming, Math. Program., 39 (1987), pp. 117-129. · Zbl 0637.90078 |
| [62] | Mycielski, J., Sur le coloriage des graphes, Colloq. Math., 3 (1955), pp. 161-162. · Zbl 0064.17805 |
| [63] | Padberg, M. W., Perfect zero-one matrices, Math. Program., 6 (1974), pp. 180-196. · Zbl 0284.90061 |
| [64] | Parrilo, P. A., Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization, Ph.D. thesis, California Institute of Technology, Pasadena, CA, 2000. |
| [65] | Parrilo, P. A., Semidefinite programming relaxations for semialgebraic problems, Math. Program., 96 (2003), pp. 293-320. · Zbl 1043.14018 |
| [66] | Pêcher, A., Partitionable graphs arising from near-factorizations of finite groups, Discrete Math., 269 (2003), pp. 191-218. · Zbl 1030.05051 |
| [67] | Pêcher, A., Cayley partitionable graphs and near-factorizations of finite groups, Discrete Math., 276 (2004), pp. 295-311. · Zbl 1031.05110 |
| [68] | Peña, J., Vera, J., and Zuluaga, L. F., Computing the stability number of a graph via linear and semidefinite programming, SIAM J. Optim., 18 (2007), pp. 87-105, doi:10.1137/05064401X. · Zbl 1176.90611 |
| [69] | Perron, O., Zur Theorie der Matrizen, Math. Ann., 64 (1907), pp. 248-263. · JFM 38.0202.01 |
| [70] | Reznick, B., Forms derived from the arithmetic-geometric inequality, Math. Ann., 283 (1989), pp. 431-464. · Zbl 0637.10015 |
| [71] | Reznick, B., Some concrete aspects of Hilbert’s 17th problem, Contemp. Math., 253 (2000), pp. 251-272. · Zbl 0972.11021 |
| [72] | Robinson, R. M., Some definite polynomials which are not sums of squares of real polynomials, in Selected Questions of Algebra and Logic, Academy of Sciences USSR, Novosibirsk, 1973, pp. 264-282. · Zbl 0277.10019 |
| [73] | Roebers, L. M., Vera, J. C., and ga, L. F., Sparse non-SOS Putinar-type Positivstellensätze, preprint, https://arxiv.org/abs/2110.10079, 2021. |
| [74] | Saunderson, J., A Convex Form that Is Not a Sum of Squares, preprint, https://arxiv.org/abs/2105.08432, 2021. |
| [75] | Schrijver, A., A comparison of the Delsarte and Lovász bounds, IEEE Trans. Inform. Theory, 25 (1979), pp. 425-429. · Zbl 0444.94009 |
| [76] | Song, D. and Parrilo, P. A., On approximations of the psd cone by a polynomial number of smaller-sized psd cones, Math. Program., 198 (2023), pp. 733-785. · Zbl 1512.90161 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
