Graph Theory and Combinatorics Seminar: Triangle-free graphs: many questions, few answers
- Event Type
- Seminar/Symposium
- Sponsor
- N/A
- Location
- 345 AH
- Date
- Mar 1, 2022 1:00 pm
- Speaker
- Felix Clemen (UIUC)
- Contact
- Sean English
- senglish@illinois.edu
- Views
- 15
We will present problems (and solve some of them) about triangle-free graphs related to Erdős' Sparse Half Conjecture: Every triangle-free graph on n vertices has an induced subgraph on n/2 vertices with at most n^2/50 edges.
Among others we prove the following variant of it: For every sufficiently large even integer n the following holds. Every triangle-free graph on n vertices has a partition V(G)=A U B with |A|=|B|=n/2 such that e(G[A])+e(G[B]) <= n^2/16.