Combinatorical and Algebraic Structures Seminar

Session details

Date: 2.11.2021
Speaker: Jan Volec, FJFI, České vysoké učení technické v Praze
Title: Three open problems in extremal graph theory
Abstract: In this talk, we aim to discuss three connected open problems in extremal graph theory and some possible approaches how to tackle them: 1) Given a large graph $G$ that does not contain a complete subgraph of a fixed size, how many edges do we need to remove to make it bipartite? The most famous instance of this general question is the so-called triangle-free case: Erdos conjectured that any $n$-vertex graph without triangles can be made bipartite by removing at most $n^2/25$ edges. If true, this bound would be best possible. 2) If $G$ is an $n$-vertex triangle-free (or more generally $K_k$-free) graph, then it has at most as many edges as the corresponding Turán graph. But what if instead of trying to maximize total edge-count, we aim to find a graph that has no ``sparse'' induced subgraph on $n/2$ vertices? In this direction, a well known conjecture of Erdos states that in every triangle-free $n$-vertex graph we will find a subset of $n/2$ vertices inducing at most $n^2/50$ edges. 3) Given a pair of numbers $(e,t)$ from $[0,1]^2$, is there an easy condition to check whether there exists, for every large enough $n$, an $n$-vertex graph with roughly $e*(n^2/2)$ edges and $t*(n^3/6)$ triangles? Yes, there is, thanks to a recent result of Razborov. His result was then generalized by Reiher to the analogous problem where we are, given a natural number $k$ and a pair $(e,d)$ from $[0,1]^2$, concerned with finding an $n$-vertex graph $G$ with $e*(n^2/2)$ edges and $d*(n^k/k!)$ cliques of order $k$. Can this be generalized even further? For example, given two natural numbers $k_1$ and $k_2$, can we find a nice condition for the so-called realizable pairs $(d_1,d_2)$ from $[0,1]^2$, where $d_1$ and $d_2$ are the normalized counts of cliques of order $k_1$ and $k_2$, respectively?

Return to index.