When: Sunday, April 11,
10am
Where: Schreiber 309
Speaker: Tom Calvari, Tel Aviv University
Title: Graphs Without
Induced Odd Cycles Are Probably Bipartite
In this talk, we will investigate the typical structure of a graph with a
fixed number of vertices and edges and no induced copies of some fixed
graph $H$.
We will discuss some of the previous work done on this
problem,
and present two new results:
1. For any graph $H$ with chromatic number $k > 2$, almost all graphs on
$n$
vertices and with $m$ edges without induced copies of $H$ are
near-$(k-1)$-partite, so long as $m$ belongs to some necessary range.
2. For $H=C_r$ an odd cycle, almost all such graphs are actually fully
bipartite.
Joint work with Wojciech Samotij