Fakulta matematiky, fyziky
a informatiky
Univerzita Komenského v Bratislave

Seminár z teórie grafov - Daniel Kráľ (3.10.2019)

vo štvrtok 3.10.2019 o 9:50 hod. v miestnosti M/213


01. 10. 2019 12.11 hod.
Od: Martin Škoviera

Prednášajúci: Daniel Kráľ (Masaryk University, Brno, and University of Warwick)

Názov: Extremal problems concerning graphs and tournament

Termín: 3.10.2019, 9:50 hod., M/213


Abstrakt:
One of the most classical themes in extremal graph theory is the study of the interplay of subgraph densities. We will present two results that belong to this theme. The first concerns the following conjecture of Lovasz: any finite feasible set of subgraph density constraints can be extended to a finite set such that the asymptotic structure of graphs satisfying the constraints is unique. We will disprove the conjecture.

The second result is inspired by the Erdos-Rademacher Problem on the minimum possible triangle density in a graph with a given edge density. A conjecture of Linial and Morgenstern which asserts that, among all tournaments with a given density d of cycles of length three, the density of cycles of length four is minimized by tournaments with a structure analogous to that of graphs appearing in the Erdos-Rademacher Problem. We prove this conjecture for d>=1/36 using methods from spectral graph theory, and demonstrate that the structure of extremal examples is more complex than expected by giving its full description for d>=1/16.

The talk is based on results obtained in joint work with Timothy Chan, Andrzej Grzesik, Laszlo Miklos Lovasz and Jonathan Noel.