{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,1]],"date-time":"2026-09-01T04:54:19Z","timestamp":1788238459102,"version":"build-2803163510"},"reference-count":23,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2007,1]]},"abstract":"<jats:p>The kth p\u2010power of a graph G is the graph on the vertex set $V(G)^k$, where two k\u2010tuples are adjacent iff the number of their coordinates which are adjacent in G is not congruent to 0 modulo p. The clique number of powers of G is polylogarithmic in the number of vertices; thus graphs with small independence numbers in their p\u2010powers do not contain large homogeneous subsets. We provide algebraic upper bounds for the asymptotic behavior of independence numbers of such powers, settling a conjecture of [N. Alon and E. Lubetzky, Combinatorica, 27 (2007), pp. 13\u201333] up to a factor of 2. For precise bounds on some graphs, we apply Delsarte\u2019s linear programming bound and Hoffman\u2019s eigenvalue bound. Finally, we show that for any nontrivial graph G, one can point out specific induced subgraphs of large p\u2010powers of G with neither a large clique nor a large independent set. We prove that the larger the Shannon capacity of $\\overline{G}$ is, the larger these subgraphs are, and if G is the complete graph, then some p\u2010power of G matches the bounds of the Frankl\u2013Wilson Ramsey construction, and is in fact a subgraph of a variant of that construction.<\/jats:p>","DOI":"10.1137\/060657893","type":"journal-article","created":{"date-parts":[[2007,4,26]],"date-time":"2007-04-26T18:00:21Z","timestamp":1177610421000},"page":"329-348","source":"Crossref","is-referenced-by-count":4,"title":["Graph Powers, Delsarte, Hoffman, Ramsey, and Shannon"],"prefix":"10.1137","volume":"21","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eyal","family":"Lubetzky","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2007,4,27]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(03)00227-9"},{"key":"R2","unstructured":"N. Alon,\n                      Probabilistic methods in extremal finite set theory\n                      , in Extremal Problems for Finite Sets, Bolyai Soc. Math. Stud. 3, P. Frankl, Z. F\u00fcredi, G. O. H. Katona, and D. Mikl\u00f3s, eds., Visegr\u00e1d, Hungary, 1991, pp. 39\u201357."},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009824"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-007-0042-5"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"N. Alon and J. H. Spencer,\n                      The Probabilistic Method\n                      , 2nd ed., Wiley, New York, 2000.","DOI":"10.1002\/0471722154"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"B. Barak, A. Rao, R. Shaltiel, and A. Wigderson,\n                      2\u2013source dispersers for sub\u2010polynomial entropy and Ramsey graphs beating the Frankl\u2010Wilson construction\n                      , in Proceedings of the 38th ACM Symposium on Theory of Computing, 2006, pp. 671\u2013680.","DOI":"10.1145\/1132516.1132611"},{"key":"R7","first-page":"272","volume":"27","author":"Delsarte P.","year":"1972","journal-title":"Philips Res. Rep.","ISSN":"https:\/\/id.crossref.org\/issn\/0031-7918","issn-type":"print"},{"key":"R8","first-page":"1","volume":"10","author":"Delsarte P.","year":"1973","journal-title":"Philips Res. Rep. Suppl."},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1947-08785-1"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579457"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.37236\/1493"},{"key":"R12","unstructured":"M. Hall,\n                      Combinatorial Theory\n                      , 2nd ed., Wiley, New York, 1986."},{"key":"R13","unstructured":"A. J. Hoffman,\n                      On eigenvalues and colorings of graphs\n                      , in Graph Theory and Its Applications, B. Harris, ed., Academic Press, New York, London, 1970, pp. 79\u201391."},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.1013"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"J. H. van Lint and R. M. Wilson,\n                      A Course in Combinatorics\n                      , 2nd ed., Cambridge University Press, Cambridge, UK, 2001.","DOI":"10.1017\/CBO9780511987045"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1109\/18.748991"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1979.1055985"},{"key":"R18","unstructured":"F. J. MacWilliams and N. J. A. Sloane,\n                      The Theory of Error\u2010Correcting Codes\n                      , North\u2013Holland, Amsterdam, 1977."},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1956.1056798"},{"key":"R20","unstructured":"G. Szego\u02dd,\n                      Orthogonal Polynomials\n                      , 4th ed., Amer. Math. Soc. Colloq. Publ. 23, AMS, Providence, RI, 1975."},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1007\/BF01196136"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1007\/BF01223730"},{"key":"R23","first-page":"263","volume":"27","author":"Ward H. N.","year":"2001","journal-title":"Serdica Math. J.","ISSN":"https:\/\/id.crossref.org\/issn\/1310-6600","issn-type":"print"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/060657893","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:55:11Z","timestamp":1787320511000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/060657893"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,1]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2007,1]]}},"alternative-id":["10.1137\/060657893"],"URL":"https:\/\/doi.org\/10.1137\/060657893","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,1]]}}}