Immersing cliques in graphs and digraphs

Combinatorics Seminar
Friday, October 28, 2011 - 3:00pm
1 hour (actually 50 minutes)
Skiles 005
Simon Frazer University
Immersion is a containment relation between graphs (or digraphs) which is defined similarly to the more familiar notion of minors, but is incomparable to it. Of particular interest is to find conditions on a graph (or digraph) G which guarantee that G contains a clique (or bidirected clique) of order t as an immersion. This talk will begin with a gentle introduction, and will then share two new results of this form, one for graphs and one for digraphs. In the former case, we find that minimum degree 200t is sufficient, and in the later case, we find that minimum degree t(t-1) is sufficient, provided that G is Eulerian. These results come from joint work with Matt DeVos, Jacob Fox, Zdenek Dvorak, Bojan Mohar and Diego Scheide.