PreprintarXiv licencearXiv
An Induced Subgraph Paradigm for Strongly Regular Graph Constructions
Abstract
How many disjoint copies of some graph H can appear in an induced subgraph of a strongly regular graph? We give upper and lower bounds that depend on the number of vertices in their boundary. This generalizes a result of Lou-Murin which bounds the independence number of a (hitherto still elusive) strongly regular graph with parameters $(99,14,1,2)$. The equality cases suggest alternative structural approaches for potential constructions of such a graph. We show, using computer searches, that one cannot impose certain additional natural conditions for some of the cases.
Related
- Upper tail large deviations of regular subgraph counts in sparse random regular graphs
- Bipodal optimizers in the upper-tail variational problem for regular subgraph densities
- Capillary-gravity water waves with compactly supported vorticity I: Local constructions and regular drift
- Enumeration of small vertex-transitive directed strongly regular graphs
- Coherent configuration on 3-uniform hypergraph over strongly regular graph
BibTeX
@misc{baker2026induced,
title = {{An Induced Subgraph Paradigm for Strongly Regular Graph Constructions}},
author = {Benjamin Baker},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.22299},
eprint = {2610.22299},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.22299},
}
RIS
TY - UNPB
TI - An Induced Subgraph Paradigm for Strongly Regular Graph Constructions
AU - Benjamin Baker
PY - 2026
DA - 2026/10/15
PB - arXiv
DO - 10.48550/arxiv.2610.22299
UR - https://arxiv.org/abs/2610.22299
AB - How many disjoint copies of some graph H can appear in an induced subgraph of a strongly regular graph? We give upper and lower bounds that depend on the number of vertices in their boundary. This generalizes a result of Lou-Murin which bounds the independence number of a (hitherto still elusive) strongly regular graph with parameters $(99,14,1,2)$. The equality cases suggest alternative structural approaches for potential constructions of such a graph. We show, using computer searches, that one cannot impose certain additional natural conditions for some of the cases.
ER -