Seminar

# Zykov’s symmetrization for multiple graphs, a new tool for Turán type problems with an application to Erdos’ conjecture on pentagonal edges

#### Graphs, Hypergraphs, and Computing

#### 22 April 15:30 - 16:30

#### Zoltan Furedi - University of Illinois at Urbana-Champaign

Erdos, Faudree, and Rousseau (1992) showed that a graph on $n$ vertices with [n^2/4]+1$ edges has at least 2[n/2]+1$ edges on triangles and this result is sharp.

They also showed that such a graph has at least cn^2 pentagonal edges and conjectured that an extremal graph has two components, a complete graph on $[2n/3] +1$ vertices and a complete bipartite graph on the rest.

In this talk we give a graph of [n^2/4]+1 edges with much fewer, namely n^2(2+\sqrt{2})/16 + O(n) = 0.213...n^2 pentagonal edges, disproving the original conjecture of Erdos. This coefficient is asymptotically the best possible.

Given graphs H and F let {\cal E}(H,F) denote the set of edges of H which appear in a subgraph isomorphic to F, and let h(n,e,F) denote the minimum of |{\cal E}(H,F)| among all graphs H of n vertices and e edges. We asymptotically determine h(n,\lambda n^2, C_3) and h(n,\lambda n^2, C_5) for fixed \lambda, 1/4 < \lambda < 1/2. For 2k+1\ge 7 we establish the conjecture of Erd\H{o}s et al. that h(n,cn^2, C_{2k+1}) is obtained from the above two-component example.

One of our main tools (beside Szemer\'edi's regularity) is a new version of Zykov's symmetrization what we can apply for several graphs, simultaneously.

A joint work with Z. Maleki (Isfahan University).

They also showed that such a graph has at least cn^2 pentagonal edges and conjectured that an extremal graph has two components, a complete graph on $[2n/3] +1$ vertices and a complete bipartite graph on the rest.

In this talk we give a graph of [n^2/4]+1 edges with much fewer, namely n^2(2+\sqrt{2})/16 + O(n) = 0.213...n^2 pentagonal edges, disproving the original conjecture of Erdos. This coefficient is asymptotically the best possible.

Given graphs H and F let {\cal E}(H,F) denote the set of edges of H which appear in a subgraph isomorphic to F, and let h(n,e,F) denote the minimum of |{\cal E}(H,F)| among all graphs H of n vertices and e edges. We asymptotically determine h(n,\lambda n^2, C_3) and h(n,\lambda n^2, C_5) for fixed \lambda, 1/4 < \lambda < 1/2. For 2k+1\ge 7 we establish the conjecture of Erd\H{o}s et al. that h(n,cn^2, C_{2k+1}) is obtained from the above two-component example.

One of our main tools (beside Szemer\'edi's regularity) is a new version of Zykov's symmetrization what we can apply for several graphs, simultaneously.

A joint work with Z. Maleki (Isfahan University).

Organizers

Magnus M. Halldorsson

Reykjavik University

Klas Markström

Umeå University

Andrzej Rucinski

Adam Mickiewicz University

Carsten Thomassen

Technical University of Denmark, DTU