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 |
MARC
| LEADER | 00000caa a2200000 c 4500 | ||
|---|---|---|---|
| 001 | 1908544600 | ||
| 003 | DE-627 | ||
| 005 | 20241205220520.0 | ||
| 007 | cr uuu---uuuuu | ||
| 008 | 241114s2024 xx |||||o 00| ||eng c | ||
| 024 | 7 | |a 10.1016/j.jctb.2024.05.004 |2 doi | |
| 035 | |a (DE-627)1908544600 | ||
| 035 | |a (DE-599)KXP1908544600 | ||
| 035 | |a (OCoLC)1475647365 | ||
| 040 | |a DE-627 |b ger |c DE-627 |e rda | ||
| 041 | |a eng | ||
| 084 | |a 28 |2 sdnb | ||
| 100 | 1 | |a Joos, Felix |d 1989- |e VerfasserIn |0 (DE-588)1075006171 |0 (DE-627)832846244 |0 (DE-576)442747438 |4 aut | |
| 245 | 1 | 0 | |a Counting oriented trees in digraphs with large minimum semidegree |c Felix Joos, Jonathan Schrodt |
| 264 | 1 | |c September 2024 | |
| 300 | |a 35 | ||
| 336 | |a Text |b txt |2 rdacontent | ||
| 337 | |a Computermedien |b c |2 rdamedia | ||
| 338 | |a Online-Ressource |b cr |2 rdacarrier | ||
| 500 | |a Online verfügbar: 29. Mai 2024 | ||
| 500 | |a Gesehen am 14.11.2024 | ||
| 520 | |a 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. | ||
| 650 | 4 | |a (Di)graphs | |
| 650 | 4 | |a Counting | |
| 650 | 4 | |a Spanning trees | |
| 700 | 1 | |a Schrodt, Jonathan |e VerfasserIn |0 (DE-588)1348291885 |0 (DE-627)1908545232 |4 aut | |
| 773 | 0 | 8 | |i Enthalten in |t Journal of combinatorial theory |d Orlando, Fla. : Academic Press, 1971 |g 168(2024) vom: Sept., Seite 236-270 |h Online-Ressource |w (DE-627)266892426 |w (DE-600)1469158-9 |w (DE-576)104193816 |7 nnas |a Counting oriented trees in digraphs with large minimum semidegree |
| 773 | 1 | 8 | |g volume:168 |g year:2024 |g month:09 |g pages:236-270 |g extent:35 |a Counting oriented trees in digraphs with large minimum semidegree |
| 856 | 4 | 0 | |u https://doi.org/10.1016/j.jctb.2024.05.004 |x Verlag |x Resolving-System |z kostenfrei |3 Volltext |
| 856 | 4 | 0 | |u https://www.sciencedirect.com/science/article/pii/S0095895624000431 |x Verlag |z kostenfrei |3 Volltext |
| 951 | |a AR | ||
| 992 | |a 20241114 | ||
| 993 | |a Article | ||
| 994 | |a 2024 | ||
| 998 | |g 1348291885 |a Schrodt, Jonathan |m 1348291885:Schrodt, Jonathan |d 110000 |d 110300 |e 110000PS1348291885 |e 110300PS1348291885 |k 0/110000/ |k 1/110000/110300/ |p 2 |y j | ||
| 998 | |g 1075006171 |a Joos, Felix |m 1075006171:Joos, Felix |d 110000 |d 110300 |e 110000PJ1075006171 |e 110300PJ1075006171 |k 0/110000/ |k 1/110000/110300/ |p 1 |x j | ||
| 999 | |a KXP-PPN1908544600 |e 4614754821 | ||
| BIB | |a Y | ||
| SER | |a journal | ||
| JSO | |a {"relHost":[{"physDesc":[{"extent":"Online-Ressource"}],"id":{"eki":["266892426"],"zdb":["1469158-9"]},"origin":[{"publisherPlace":"Orlando, Fla.","dateIssuedDisp":"1971-","dateIssuedKey":"1971","publisher":"Academic Press"}],"recId":"266892426","language":["eng"],"disp":"Counting oriented trees in digraphs with large minimum semidegreeJournal of combinatorial theory","type":{"bibl":"periodical","media":"Online-Ressource"},"note":["Gesehen am 13.01.14"],"part":{"pages":"236-270","year":"2024","extent":"35","text":"168(2024) vom: Sept., Seite 236-270","volume":"168"},"titleAlt":[{"title":"Journal of combinatorial theory / B"},{"title":"JCTB"}],"pubHistory":["10.1971 - 103.2013; Vol. 104.2014 -"],"title":[{"subtitle":"JCTB","title":"Journal of combinatorial theory","title_sort":"Journal of combinatorial theory"}]}],"physDesc":[{"extent":"35 S."}],"id":{"eki":["1908544600"],"doi":["10.1016/j.jctb.2024.05.004"]},"origin":[{"dateIssuedDisp":"September 2024","dateIssuedKey":"2024"}],"name":{"displayForm":["Felix Joos, Jonathan Schrodt"]},"language":["eng"],"recId":"1908544600","type":{"bibl":"article-journal","media":"Online-Ressource"},"note":["Online verfügbar: 29. Mai 2024","Gesehen am 14.11.2024"],"title":[{"title":"Counting oriented trees in digraphs with large minimum semidegree","title_sort":"Counting oriented trees in digraphs with large minimum semidegree"}],"person":[{"roleDisplay":"VerfasserIn","display":"Joos, Felix","role":"aut","family":"Joos","given":"Felix"},{"display":"Schrodt, Jonathan","roleDisplay":"VerfasserIn","role":"aut","family":"Schrodt","given":"Jonathan"}]} | ||
| SRT | |a JOOSFELIXSCOUNTINGOR2024 | ||