EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC-ND 4.0

Independent Sets of Random Trees and Sparse Random Graphs

Steven Heilman

Journal of Graph Theory · 2025-07 · 109 (3) · 294-309

DOI: 10.1002/jgt.23225 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Graph Theory, online erschienen am 10.02.2025. Verfasst von Steven Heilman. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 35 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC-ND 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

An independent set of size in a finite undirected graph is a set of vertices of the graph, no two of which are connected by an edge. Let be the number of independent sets of size in the graph and let . In 1987, Alavi, Malde, Schwenk, and Erdős asked if the independent set sequence of a tree is unimodal (the sequence goes up and then down). This problem is still open. In 2006, Levit and Mandrescu showed that the last third of the independent set sequence of a tree is decreasing. We show that the first 46.8% of the independent set sequence of a random tree is increasing with (exponentially) high probability as the number of vertices goes to infinity. So, the question of Alavi, Malde, Schwenk, and Erdős is “four‐fifths true,” with high probability. We also show unimodality of the independent set sequence of Erdős–Rényi random graphs, when the expected degree of a single vertex is large (with [exponentially] high probability as the number of vertices in the graph goes to infinity, except for a small region near the mode). A weaker result is shown for random regular graphs. The structure of independent sets of size as varies is of interest in probability, statistical physics, combinatorics, and computer science.

Zitieren

APA

Heilman, S. (2025). Independent Sets of Random Trees and Sparse Random Graphs. Journal of Graph Theory, 109(3), 294-309. https://doi.org/10.1002/jgt.23225

Vancouver

Heilman S. Independent Sets of Random Trees and Sparse Random Graphs. Journal of Graph Theory. 2025;109(3):294-309. doi:10.1002/jgt.23225

BibTeX
@article{Heilman2025,
  author = {Heilman, Steven},
  title = {Independent Sets of Random Trees and Sparse Random Graphs},
  journal = {Journal of Graph Theory},
  year = {2025},
  volume = {109},
  number = {3},
  pages = {294--309},
  doi = {10.1002/jgt.23225}
}
Kostenlos starten →