Explicit Fractalizers: Prime-Order Paley Graphs and other Cayley Graphs
Abstract
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."
Related
BibTeX
@misc{kiem2026explicit,
title = {{Explicit Fractalizers: Prime-Order Paley Graphs and other Cayley Graphs}},
author = {Aldo Kiem and Fan Wei},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.33526},
eprint = {2609.33526},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.33526},
}
RIS
TY - UNPB
TI - Explicit Fractalizers: Prime-Order Paley Graphs and other Cayley Graphs
AU - Aldo Kiem
AU - Fan Wei
PY - 2026
DA - 2026/09/27
PB - arXiv
DO - 10.48550/arxiv.2609.33526
UR - https://arxiv.org/abs/2609.33526
AB - 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."
ER -