Search

Alon and Krivelevich proved that for every n -vertex subcubic graph H and every integer q ≥ 2 there exists a (smallest) integer f = f (H , q) such that every K f -minor contains a subdivision of H in which the length of every subdivision-path is divisible by q. Improving their superexponential bound, we show that f (H , q) ≤ 21 2 q n + 8 n + 14 q , which is optimal up to a constant multiplicative factor. [ABSTRACT FROM AUTHOR]

A basic result in graph theory says that any n -vertex tournament with in- and out-degrees larger than n − 2 4 contains a Hamilton cycle, and this is tight. In 1990, Bollobás and Häggkvist significantly extended this by showing that for any fixed k and ε > 0 , and sufficiently large n , all tournaments with degrees at least n 4 + ε n contain the k -th power of a Hamilton cycle. Up until now, there has not been any progress on determining a more accurate error term in the degree condition, neither in understanding how large n should be in the Bollobás-Häggkvist theorem. We essentially resolve both of these questions. First, we show that if the degrees are at least n 4 + c n 1 − 1 / ⌈ k / 2 ⌉ for some constant c = c (k) , then the tournament contains the k -th power of a Hamilton cycle. In particular, in order to guarantee the square of a Hamilton cycle, one only needs a constant additive term. We also present a construction which, modulo a well known conjecture on Turán numbers for complete bipartite graphs, shows that the error term must be of order at least n 1 − 1 / ⌈ (k − 1) / 2 ⌉ , which matches our upper bound for all even k. For odd k , we believe that the lower bound can be improved. Indeed, we show that for k = 3 , there are tournaments with degrees n 4 + Ω (n 1 / 5) and no cube of a Hamilton cycle. In addition, our results imply that the Bollobás-Häggkvist theorem already holds for n = ε − Θ (k) , which is best possible. [ABSTRACT FROM AUTHOR]

The study of problems concerning subdivisions of graphs has a rich history in extremal combinatorics. Confirming a conjecture of Burr and Erdős, Alon proved in 1994 that subdivided graphs have linear Ramsey numbers. Later, Alon, Krivelevich and Sudakov showed that every n -vertex graph with at least ε n 2 edges contains a 1-subdivision of the complete graph on c ε n vertices, resolving another old conjecture of Erdős. In this paper we consider the directed analogue of these problems and show that every tournament on at least (2 + o (1)) k 2 vertices contains the 1-subdivision of a transitive tournament on k vertices. This is optimal up to a multiplicative factor of 4 and confirms a conjecture of Girão, Popielarz and Snyder. [ABSTRACT FROM AUTHOR]

The following very natural problem was raised by Chung and Erdős in the early 80's and has since been repeated a number of times. What is the minimum of the Turán number ex (n , H) among all r -graphs H with a fixed number of edges? Their actual focus was on an equivalent and perhaps even more natural question which asks what is the largest size of an r -graph that can not be avoided in any r -graph on n vertices and e edges? In the original paper they resolve this question asymptotically for graphs, for most of the range of e. In a follow-up work Chung and Erdős resolve the 3-uniform case and raise the 4-uniform case as the natural next step. In this paper we make first progress on this problem in over 40 years by asymptotically resolving the 4-uniform case which gives us some indication on how the answer should behave in general. [ABSTRACT FROM AUTHOR]