## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Thursday, June 23, 2016, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Jan Volec

## Minimum number of edges that occur in odd cycles

If an n-vertex graph G has more than n^2/4 edges and n is at least 4k, then G contains a copy of a cycle of length 2k+1. But can we guarantee something stronger than just a single copy? In 1992, Erdős, Faudree and Rousseau showed that the number of edges that occur in a copy of a triangle in G is at least n+1-(n mod 2), and this bound is tight. They also showed that the number of edges in G that occur in a copy of (2k+1)-cycle, where k>1 is fixed, suddenly starts being quadratic in n, and it is asymptotically at least 11/144 * n^2. However, they conjectured that the graph G must contain at least (2/9+o(1))n^2 such edges.

Very recently, Füredi and Maleki showed that the conjecture is false in the case of 5-cycles by constructing n-vertex graphs with n^2/4 + 1 edges such that only (1/8+Sqrt(2)/16+o(1))n^2 < 0.2134n^2 edges occur in 5-cycles. They also proved the asymptotically correct lower bound on the number of such edges under the additional assumption that G has more than (1/4+epsilon)n^2 edges. In this talk, we present a flag algebra approach to tackle this problem which we then combine with a stability-type argument in order to show that every n-vertex graph with more than n^2/4 edges contains at least (1/8+Sqrt(2)/16-o(1))n^2 edges that occur in 5-cycles, which settles a conjecture of Füredi and Maleki. Moreover, we obtain the corresponding stability result, and discuss the analogous results for longer odd cycles.

This is a joint work with Andrzej Grzesik and Ping Hu.

Information for students and suggested topics for student talks