The Binomial Random Graph is a Bad Inducer
Random Structures & Algorithms · 2026-05 · 68 (3)
DOI: 10.1002/rsa.70067 ↗Kurz gefasst
Fachartikel in der Zeitschrift Random Structures & Algorithms, online erschienen am 16.04.2026. Verfasst von Vishesh Jain und 2 weiteren Autor:innen. Die Arbeit nennt 12 Literaturangaben. Gefördert von: National Science Foundation.
Abstract (Originalsprache)
For a finite graph and a value , let denote the largest for which there is a sequence of graphs of edge density approaching so that the induced ‐density of the sequence approaches . We show that for all on at least three vertices and all , the binomial random graph has induced ‐density strictly less than This provides a negative answer to a problem posed by Liu et al. (2023). Our approach is in the limiting setting of graphons, and we in fact show a stronger result: the binomial random graph is never a local maximum in the space of graphons of edge density . This is done by finding a sequence of balanced perturbations of arbitrarily small norm that increase the ‐density.
Förderung
- National Science Foundation
Zitieren
APA
Jain, V., Michelen, M., & Wei, F. (2026). The Binomial Random Graph is a Bad Inducer. Random Structures & Algorithms, 68(3). https://doi.org/10.1002/rsa.70067
Vancouver
Jain V, Michelen M, Wei F. The Binomial Random Graph is a Bad Inducer. Random Structures & Algorithms. 2026;68(3). doi:10.1002/rsa.70067
BibTeX
@article{Jain2026,
author = {Jain, Vishesh and Michelen, Marcus and Wei, Fan},
title = {The Binomial Random Graph is a Bad Inducer},
journal = {Random Structures & Algorithms},
year = {2026},
volume = {68},
number = {3},
doi = {10.1002/rsa.70067}
}
EUVIMED