General Events - Department of Mathematics

View Full Calendar

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
E-Mail
senglish@illinois.edu
Views
6

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. 

link for robots only