2023arXiv (Cornell University)Open access

Counting oriented trees in digraphs with large minimum semidegree

Felix Joos, Jonathan Schrodt

Open full text 0 citations

Abstract

Let $T$ be an oriented tree on $n$ vertices with maximum degree at most $e^{o(\sqrt{\log n})}$. If $G$ is a digraph on $n$ vertices with minimum semidegree $δ^0(G)\geq(\frac12+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}(\frac12-o(1))^nn!$ copies of $T$, which is optimal. This implies the analogous result in the undirected case.

Open-access reader

About this research paper

What this paper is about

Let $T$ be an oriented tree on $n$ vertices with maximum degree at most $e^{o(\sqrt{\log n})}$. If $G$ is a digraph on $n$ vertices with minimum semidegree $δ^0(G)\geq(\frac12+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}(\frac12-o(1))^nn!$ copies of $T$, which is optimal. This implies the analogous result in the undirected case.

Why it matters

A significance statement is not available in the OpenAlex record.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

Let $T$ be an oriented tree on $n$ vertices with maximum degree at most $e^{o(\sqrt{\log n})}$. If $G$ is a digraph on $n$ vertices with minimum semidegree $δ^0(G)\geq(\frac12+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}(\frac12-o(1))^nn!$ copies of $T$, which is optimal. This implies the analogous result in the undirected case.

Key concepts: Digraph, Combinatorics, Mathematics, Spanning tree, Degree (music), Tree (set theory), Undirected graph, Discrete mathematics

Related papers

Back to paper searchBrowse research topicsOriginal source
Counting oriented trees in digraphs with large minimum semidegree — Research Paper | ScholarLens