Counting oriented trees in digraphs with large minimum semidegree
Let T be an oriented tree on n vertices with maximum degree at most eo(logn). 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/logn)). This...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article (Journal) |
| Language: | English |
| Published: |
September 2024
|
| In: |
Journal of combinatorial theory
Year: 2024, Volume: 168, Pages: 236-270 |
| DOI: | 10.1016/j.jctb.2024.05.004 |
| Online Access: | Verlag, kostenfrei, Volltext: https://doi.org/10.1016/j.jctb.2024.05.004 Verlag, kostenfrei, Volltext: https://www.sciencedirect.com/science/article/pii/S0095895624000431 
|
| Author Notes: | Felix Joos, Jonathan Schrodt |
| Summary: | Let T be an oriented tree on n vertices with maximum degree at most eo(logn). 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/logn)). 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. |
|---|---|
| Item Description: | Online verfügbar: 29. Mai 2024 Gesehen am 14.11.2024 |
| Physical Description: | Online Resource |
| DOI: | 10.1016/j.jctb.2024.05.004 |