Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2507.13327 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918096466345984 |
|---|---|
| author | Chowdhury, Zawad Steinerberger, Stefan Thomas, Rekha R. |
| author_facet | Chowdhury, Zawad Steinerberger, Stefan Thomas, Rekha R. |
| contents | Graphical designs are subsets of vertices of a graph that perfectly average a selected set of eigenvectors of the Graph Laplacian. We show that in highly-structured graphs, graphical designs can coincide with highly structured and well-known combinatorial objects: orthogonal arrays in hypercube graphs, combinatorial block designs and extremizers of the Erdos-Ko-Rado theorem in Johnson graphs, and t-wise uniform sets of permutations and symmetric subgroups in normal Cayley graphs on the symmetric group. These connections allow tools from spectral graph theory to bear on these combinatorial objects. We also show that the central vertex in a Mycielskian is an extremely good design and certain designs of the Mycielskian coincide with designs of the original graph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_13327 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Graphical Designs find Combinatorial Structures Chowdhury, Zawad Steinerberger, Stefan Thomas, Rekha R. Combinatorics Spectral Theory Graphical designs are subsets of vertices of a graph that perfectly average a selected set of eigenvectors of the Graph Laplacian. We show that in highly-structured graphs, graphical designs can coincide with highly structured and well-known combinatorial objects: orthogonal arrays in hypercube graphs, combinatorial block designs and extremizers of the Erdos-Ko-Rado theorem in Johnson graphs, and t-wise uniform sets of permutations and symmetric subgroups in normal Cayley graphs on the symmetric group. These connections allow tools from spectral graph theory to bear on these combinatorial objects. We also show that the central vertex in a Mycielskian is an extremely good design and certain designs of the Mycielskian coincide with designs of the original graph. |
| title | Graphical Designs find Combinatorial Structures |
| topic | Combinatorics Spectral Theory |
| url | https://arxiv.org/abs/2507.13327 |