EUVIMEDEUVIMED entdecken
Crossref

The Binomial Random Graph is a Bad Inducer

Vishesh Jain, Marcus Michelen, Fan Wei

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →