Subdigraphs of prescribed size and outdegree

2022/10/23 by Steiner, Raphael
#05C07 #05C20 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2210.12699

Abstract

In 2006, Noga Alon raised the following open problem: Does there exist an absolute constant c>0 such that every 2n-vertex digraph with minimum out-degree at least s contains an n-vertex subdigraph with minimum out-degree at least (s)/(2)-c ? In this note, we answer this natural question in the negative, by showing that for arbitrarily large values of n there exists a 2n-vertex tournament with minimum out-degree s=n-1, in which every n-vertex subdigraph contains a vertex of out-degree at most (s)/(2)-((1)/(2)+o(1))log₃(s).

Related

• Subgraphs with a positive minimum semidegree in digraphs with large outdegree
• Subdivisions of digraphs in tournaments
• On splitting digraphs
• Vertex-disjoint cycles of different lengths in tournaments
• Graphs without proper subgraphs of minimum degree 3 and short cycles