Buchumschlag

Counting oriented trees in digraphs with large minimum semidegree

Let T be an oriented tree on n vertices with maximum degree at most eo(log⁡n). If G is a digraph on n vertices with minimum semidegree δ0(G)≥(12+o(1))n, then G contains T as a spanning tree, as recently shown by Kathapurkar and Montgomery (in fact, they only require maximum degree o(n/log⁡n)). This...

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Hauptverfasser: Joos, Felix (VerfasserIn) , Schrodt, Jonathan (VerfasserIn)
Dokumenttyp: Article (Journal)
Sprache:Englisch
Veröffentlicht: September 2024
In: Journal of combinatorial theory
Year: 2024, Jahrgang: 168, Pages: 236-270
DOI:10.1016/j.jctb.2024.05.004
Online-Zugang:Verlag, kostenfrei, Volltext: https://doi.org/10.1016/j.jctb.2024.05.004
Verlag, kostenfrei, Volltext: https://www.sciencedirect.com/science/article/pii/S0095895624000431
Volltext
Verfasserangaben:Felix Joos, Jonathan Schrodt
Beschreibung
Zusammenfassung:Let T be an oriented tree on n vertices with maximum degree at most eo(log⁡n). If G is a digraph on n vertices with minimum semidegree δ0(G)≥(12+o(1))n, then G contains T as a spanning tree, as recently shown by Kathapurkar and Montgomery (in fact, they only require maximum degree o(n/log⁡n)). This generalizes the corresponding result by Komlós, Sárközy and Szemerédi for graphs. We investigate the natural question how many copies of T the digraph G contains. Our main result states that every such G contains at least |Aut(T)|−1(12−o(1))nn! copies of T, which is optimal. This implies the analogous result in the undirected case.
Beschreibung:Online verfügbar: 29. Mai 2024
Gesehen am 14.11.2024
Beschreibung:Online Resource
DOI:10.1016/j.jctb.2024.05.004

Ähnliche Einträge