Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 11 min ago
PreprintarXiv licencearXiv

Exact Realization of Edge and Induced Three-Vertex Subgraph Counts

  • Hillel Schein
Open at sourcePDFDOICite

Abstract

The study of three-vertex subgraph densities has developed along two complementary lines: exact finite realization in large graphs of a given order, and asymptotic approximate realization by sequences of graphs. We bridge these viewpoints for the edge density and the four induced three-vertex subgraph densities. By analyzing local modifications of finite samples from graphons, we show that, for any nonempty subset of these densities, every asymptotically feasible target vector lying a fixed positive distance from the boundary of the corresponding feasible region is realized exactly by a graph of every sufficiently large order, subject only to the natural arithmetic constraints. Thus, in the interior of these feasible regions, asymptotic feasibility implies exact finite realizability up to the unavoidable arithmetic obstructions.

Related

  1. Normal approximation for subgraph counts in random intersection graphs: the case of cliques
    Katarzyna Rybarczyk, Grzegorz Serafin
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. Tests of graph homogeneity, subgraph counts, and quasirandomness
    Rudolf Grübel
    arXivPreprintarXiv licenceFull textStatisticsarXiv
  3. Fluctuations of subgraph counts in exponential random graphs
    Hui-Lin Liu, Song-Hao Liu, Dawei Lu
    arXivPreprintarXiv licenceFull textProbabilityarXiv
  4. Transposition Cayley Spectra and Subgraph Counts
    Boris Shapiro
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  5. Quasirandomness from balanced and repeated subgraph counts
    Guoqing Wang, Linlin Wang, Jun Yue
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{schein2026exact,
  title = {{Exact Realization of Edge and Induced Three-Vertex Subgraph Counts}},
  author = {Hillel Schein},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.30166},
  eprint = {2610.30166},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.30166},
}
RIS
TY  - UNPB
TI  - Exact Realization of Edge and Induced Three-Vertex Subgraph Counts
AU  - Hillel Schein
PY  - 2026
DA  - 2026/10/14
PB  - arXiv
DO  - 10.48550/arxiv.2610.30166
UR  - https://arxiv.org/abs/2610.30166
AB  - The study of three-vertex subgraph densities has developed along two complementary lines: exact finite realization in large graphs of a given order, and asymptotic approximate realization by sequences of graphs. We bridge these viewpoints for the edge density and the four induced three-vertex subgraph densities. By analyzing local modifications of finite samples from graphons, we show that, for any nonempty subset of these densities, every asymptotically feasible target vector lying a fixed positive distance from the boundary of the corresponding feasible region is realized exactly by a graph of every sufficiently large order, subject only to the natural arithmetic constraints. Thus, in the interior of these feasible regions, asymptotic feasibility implies exact finite realizability up to the unavoidable arithmetic obstructions.
ER  -