Counting oriented trees in digraphs with large minimum semidegree

• Verfasst von: Joos, Felix [VerfasserIn]
• Verfasst von: Schrodt, Jonathan [VerfasserIn]
• Titel: Counting oriented trees in digraphs with large minimum semidegree
• Verf.angabe: Felix Joos, Jonathan Schrodt
• E-Jahr: 2024
• Jahr: September 2024
• Umfang: 35 S.
• Fussnoten: Online verfügbar: 29. Mai 2024 ; Gesehen am 14.11.2024
• Titel Quelle: Enthalten in: Journal of combinatorial theory
• Ort Quelle: Orlando, Fla. : Academic Press, 1971
• Jahr Quelle: 2024
• Band/Heft Quelle: 168(2024) vom: Sept., Seite 236-270
• DOI: doi:10.1016/j.jctb.2024.05.004
• Datenträger: Online-Ressource
• Sprache: eng
• Sach-SW: (Di)graphs
• Sach-SW: Counting
• Sach-SW: Spanning trees
• K10plus-PPN: 1908544600

Abstract

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.