2022/11/03 by Oliver Janzer, Benny Sudakov, Janzer, Oliver +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2211.02015
openalex publication_date 2022/11/03 · openalex created_date 2022/11/09 · openalex updated_date 2026/07/28
In 1964, Erdős proposed the problem of estimating the Turán number of the d-dimensional hypercube Qd. Since Qd is a bipartite graph with maximum degree d, it follows from results of Füredi and Alon, Krivelevich, Sudakov that ex(n,Qd)=Od(n2-1/d). A recent general result of Sudakov and Tomon implies the slightly stronger bound ex(n,Qd)=o(n2-1/d). We obtain the first power-improvement for this old problem by showing that ex(n,Qd)=Od(n^2-(1)/(d-1)+\frac1(d-1)2d-1). This answers a question of Liu. Moreover, our techniques give a power improvement for a larger class of graphs than cubes. We use a similar method to prove that any n-vertex, properly edge-coloured graph without a rainbow cycle has at most O(n(log n)2) edges, improving the previous best bound of n(log n)2+o(1) by Tomon. Furthermore, we show that any properly edge-coloured n-vertex graph with ω(nlog n) edges contains a cycle which is almost rainbow: that is, almost all edges in it have a unique colour. This latter result is tight.