Graph powers, Delsarte, Hoffman, Ramsey and Shannon
| dc.creator | Alon, Noga | |
| dc.creator | Lubetzky, Eyal | |
| dc.date | 2006-08-01 | |
| dc.date.accessioned | 2026-07-07T07:21:14Z | |
| dc.date.available | 2026-07-07T07:21:14Z | |
| dc.description | The $k$-th $p$-power of a graph $G$ is the graph on the vertex set $V(G)^k$, where two $k$-tuples 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 poly-logarithmic in the number of vertices, thus graphs with small independence numbers in their $p$-powers do not contain large homogenous subsets. We provide algebraic upper bounds for the asymptotic behavior of independence numbers of such powers, settling a conjecture of Alon and Lubetzky up to a factor of 2. For precise bounds on some graphs, we apply Delsarte's linear programming bound and Hoffman's eigenvalue bound. Finally, we show that for any nontrivial graph $G$, one can point out specific induced subgraphs of large $p$-powers of $G$ with neither a large clique nor a large independent set. We prove that the larger the Shannon capacity of $\bar{G}$ is, the larger these subgraphs are, and if $G$ is the complete graph, then some $p$-power of $G$ matches the bounds of the Frankl-Wilson Ramsey construction, and is in fact a subgraph of a variant of that construction. | |
| dc.identifier | https://arxiv.org/abs/math/0608013 | |
| dc.identifier | http://arxiv.org/abs/math/0608013 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/115233 | |
| dc.subject | Combinatorics | |
| dc.title | Graph powers, Delsarte, Hoffman, Ramsey and Shannon | |
| dc.type | text |