Metraipolis › archive › dc_e2f8d08f4229

Explicit Fractalizers: Prime-Order Paley Graphs and other Cayley Graphs — arXiv:2609.33526

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.33526
License (as archived)
CC0-1.0
Archived
2026-10-07T23:29:05.250Z
SHA-256 of the archived text
1a956936c649181377b4101a9446adc63c8e13c14b776effc5fbed58b0f3d1af
Stable URL of this page
https://metraipolis.com/documento/dc_e2f8d08f4229

How to cite

Explicit Fractalizers: Prime-Order Paley Graphs and other Cayley Graphs — arXiv:2609.33526 — arXiv (en), https://arxiv.org/abs/2609.33526 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e2f8d08f4229 (Metraipolis archive dc_e2f8d08f4229, sha256 1a956936c649181377b4101a9446adc63c8e13c14b776effc5fbed58b0f3d1af)
BibTeX
@misc{dce2f8d08f4229,
  title = {Explicit Fractalizers: Prime-Order Paley Graphs and other Cayley Graphs — arXiv:2609.33526},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.33526},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e2f8d08f4229; sha256 1a956936c649181377b4101a9446adc63c8e13c14b776effc5fbed58b0f3d1af},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.33526. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

The inducibility problem asks for the maximum number of induced copies of a fixed graph among all graphs with a prescribed number of vertices. Inducibility has been an active area of research in extremal combinatorics, but determining all extremal graphs for explicitly defined patterns remains challenging, particularly when the description is required to hold at every host order. A graph $H$ is called a fractalizer if, for every positive integer $n$, every $n$-vertex graph maximizing the number of induced copies of $H$ is a balanced iterated blow-up of $H$, obtained by recursively repeating the same pattern in parts whose sizes differ by at most one. Previous probabilistic results show that large random graphs and random abelian Cayley graphs are fractalizers with probability tending to one, establishing their abundance without directly providing explicit families. We prove that every sufficiently large prime-order Paley graph is a fractalizer. Thus these classical arithmetic patterns determine the exact recursive structure of every extremal host, at every host order and without any algebraic assumptions on the host. We also construct a second explicit infinite family of nontrivial Cayley fractalizers, for which the fractalizer property admits a simpler proof than in the Paley case. Together, these results resolve the explicit-construction question discussed at the 2025 American Institute of Mathematics workshop "Flag Algebras and Extremal Combinatorics."

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-29 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.33526 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T23:08:10.810Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).