Thursday, October 3 |
07:00 - 08:45 |
Breakfast ↓ Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building. (Vistas Dining Room) |
09:00 - 10:00 |
Bartosz Walczak: Excluding a Burling graph ↓ A class of graphs G is χ-bounded if there is a function
f:N→N such that every graph in G with
chromatic number greater than f(k) contains a k-clique.
Several important classes of graphs, including the class of string graphs
and, more generally, every class of graphs excluding induced subdivisions of
a fixed graph, are not χ-bounded because they contain a specific
infinite family {Bk}∞k=1 of triangle-free graphs with
unbounded chromatic number, first constructed by Burling.
We show that if G is the class of string graphs or any
``2-controlled'' class of graphs excluding induced subdivisions of a
fixed graph, Burling's construction is the only reason for G not
being χ-bounded; that is, there is a function
f:N×N→N such that every graph in
G with chromatic number greater than f(k,ℓ) contains a
k-clique or an induced copy of Bℓ.
This (up to the ``2-controlled'' condition) confirms a conjecture of
Chudnovsky, Scott, and Seymour..
Being 2-controlled means that the chromatic number is bounded in terms of
the maximum chromatic number of a ball of radius 2; this holds for string
graphs and is conjectured to hold for every class of graphs excluding
induced subdivisions of a fixed graph.
This is joint work with Tara Abrishami, Marcin Brianski, James Davies,
Xiying Du, Jana Masarikova, and Pawel Rzazewski. (TCPL 201) |
10:00 - 10:30 |
Coffee Break (TCPL Foyer) |
10:30 - 11:00 |
Hehui Wu: The Betti number of the independence complex of ternary graphs ↓ Given a graph G, the independence complex I(G) is the
simplicial complex whose faces are the independent sets of V(G). Let
˜bi(G) denote the i-th reduced Betti number of I(G), and let
b(G) denote the sum of ˜bi(G)'s. A graph is ternary if it does
not contain induced cycles with length divisible by three. G. Kalai and K.
Meshulam conjectured that b(G)≤1 whenever G is ternary. With my Ph.D.
student Wentao Zhang, we prove this conjecture. This extends a recent
results proved by Chudnovsky, Scott, Seymour and Spirkl that for any ternary
graph G, the number of independent sets with even cardinality and the
independent sets with odd cardinality differ by at most 1. In this talk, we
will give a ``forward'' proof on the structure of the betti number of the
subgraphs, instead of the original "minimum counter-example" proof, and use
it as an approach to use the betti number structure to improve the bound
for the chromatic number of a ternary graph, which was first given by
Bonamy, Charbit and Thomasse. (TCPL 201) |
11:00 - 11:30 |
Sepehr Hajebi: Anticomplete sets of large treewidth ↓ Two sets A,B of vertices in a graph G are anticomplete if A∩B=∅ and there is no edge in G with an end in A and an end in B. When does a graph G of sufficiently large treewidth have two anticomplete sets each inducing a subgraph of large treewidth? The answer turns out to be: ``unless G has either a large complete subgraph or a large complete bipartite induced minor,'' and I will try to show the proof.
The ``complete subgraph'' and the ``complete bipartite induced minor'' are both unavoidable obstructions; the latter cannot even be replaced by a ``complete bipartite induced subgraph.'' Still, the above theorem can be strengthened to have only induced subgraph outcomes. This follows from a more general result, a characterization of the unavoidable induced subgraphs of graphs with a large complete bipartite induced minor. If time permits, I will say a few words about that result.
Based on joint work with Maria Chudnovsky and Sophie Spirkl. (TCPL 201) |
11:30 - 13:00 |
Lunch ↓ Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building. (Vistas Dining Room) |
14:00 - 15:00 |
Louis Esperet: The clustered Hadwiger conjecture ↓ We prove that every Kh-minor-free graph has an (h−1)-coloring in which every monochromatic component has size
at most f(h), for some function f. We also show that every Ks,t-minor-free graph has an (s+1)-coloring in
which every monochromatic component has size at most g(s,t), for some function g. The number of colors is optimal
in both results. The first result was announced by Dvorak and Norin in 2017, but our proof is quite different. The
proof of both results heavily relies on 2 recent technical ingredients: the Product Structure theorem of Dujmović,
Joret, Micek, Morin, Ueckerdt, and Wood, and a clustered coloring lemma for Ks,t-subgraph-free graphs of bounded
treewidth by Liu and Wood.
This is joint work with V. Dujmović, P. Morin, and D. Wood. (TCPL 201) |
15:00 - 15:30 |
Coffee Break (TCPL Foyer) |
15:30 - 16:00 |
Chun-Hung Liu: Weak diameter list coloring for minor-closed families ↓ Weak diameter coloring is the key notion used in the recent result that determines the asymptotic dimension of
minor-closed families of graphs. We consider the list-coloring analog in this talk. For every graph H, we determine
the minimum integer k such that every graph that does not contain Has a minor can be colored so that every
monochromatic component has bounded weak diameter as long as every vertex has at least k available colors. This result
is a common generalization of previous results about weak diameter coloring of graphs with excluded minors, about weak
diameter list-coloring of graphs with bounded Euler genus, and about clustered coloring of graphs with bounded maximum
degree and with excluded minors. This is joint work with Joshua Crouch. (TCPL 201) |
16:00 - 16:30 |
Vida Dujmović: Planar graphs in blowups of fans ↓ I will talk about the following result: every n-vertex planar graph
is contained in the graph obtained from a fan by blowing up each
vertex by a complete graph of order O(√nlog2n).
Equivalently, every n-vertex planar graph G has a set X of
O(√nlog2n) vertices such that G−X has bandwidth.
O(√nlog2n). This result holds in the more general setting
of graphs contained in the strong product of a bounded treewidth graph
and a path, which includes bounded genus graphs, graphs excluding a
fixed apex graph as a minor, and k-planar graphs for fixed k.
This is joint work with Joret, Micek, Morin and Wood (TCPL 201) |
17:30 - 19:30 |
Dinner ↓ A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building. (Vistas Dining Room) |