Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Prof. Emo Welzl and Prof. Bernd Gärtner
Mittagsseminar Talk Information |
Date and Time: Thursday, June 23, 2016, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Jan Volec
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, Erdő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.
Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)
Previous talks by year: 2025 2024 2023 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996
Information for students and suggested topics for student talks
Automatic MiSe System Software Version 1.4803M | admin login