On Sparse Halves in Triangle-Free Graphs
- Event Type
- Lecture
- Sponsor
- Combinatorics Colloquium
- Location
- 119 MSEB (Material Science and Engineering Building)
- Date
- Apr 26, 2023 2:00 pm
- Speaker
- Alexander Razborov (U. Chicago)
- Contact
- Jozsef Balogh
- jobal@illinois.edu
- Views
- 15
- Originating Calendar
- Mathematics Colloquium & Named Lectures
One of Erdos’s favorite still unresolved conjectures states that every triangle-free graph on $n$ vertices has an induced subgraph on $n/2$ vertices (a “half”) with at most $n^2/50$ edges. We review known partial results in this direction, including recent contributions by the speaker. Among the latter are the new bound $27n^2/1024$ in the general case and the complete solution for graphs of girth $\geq 5$, for graphs with independence number $\geq 2n/5$ and for strongly regular graphs. If time permits we will also give a sketch of a proof.