# Schedule for: 24w5272 - New Perspectives in Colouring and Structure

Beginning on Sunday, September 29 and ending Friday October 4, 2024

All times in Banff, Alberta time, MDT (UTC-6).

Sunday, September 29 | |
---|---|

09:00 - 10:00 | placeholder (Online) |

16:00 - 17:30 | Check-in begins at 16:00 on Sunday and is open 24 hours (Front Desk - Professional Development Centre) |

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) |

20:00 - 22:00 |
Informal gathering ↓ Meet and Greet at the BIRS Lounge (Professional Development Centre, 2nd floor) (Other (See Description)) |

Monday, September 30 | |
---|---|

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) |

08:45 - 09:00 |
Introduction and Welcome by BIRS Staff ↓ A brief introduction to BIRS with important logistical information, technology instruction, and opportunity for participants to ask questions. (TCPL 201) |

09:00 - 10:00 |
Sergey Norin: Hadwiger variations ↓ Hadwiger's conjecture states that for every integer $t \geq 0$
every graph $G$ with no complete minor on $t+1$ vertices can be properly
coloured using $t$ colours.
We will survey recent results on several variants of the conjecture obtained
by relaxing the conditions on the number of colours, on the completeness of
the minor, and on the colouring being proper, and by making the notion of a
minor more restrictive. (TCPL 201) |

10:00 - 10:30 | Coffee Break (TCPL Foyer) |

10:30 - 11:30 |
Problem session ↓ https://www.overleaf.com/2573969174vfqphnjjgffz#5b4929 (TCPL 201) |

10:30 - 12:00 | Alex Scott: Discussions (Do not delete or zoom will shutdown) (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) |

13:00 - 14:00 |
Rose McCarty: Structure of monadically stable graphs ↓ Stability is a fundamental notion in model theory which arose from
Shelah's classification program. Now, there are many different equivalent
definitions, and some have a very combinatorial flavor. We focus on the
structural aspects, as well a result which is analogous to Mader's theorem
that graphs with a forbidden minor have bounded average degree. (TCPL 201) |

14:00 - 14:20 |
Group Photo ↓ Meet in foyer of TCPL to participate in the BIRS group photo. The photograph will be taken outdoors, so dress appropriately for the weather. Please don't be late, or you might not be in the official group photo! (TCPL Foyer) |

14:20 - 15:30 | Problem session (continued) (TCPL 201) |

14:20 - 18:00 | Alex Scott: Discussions (Do not delete or zoom will shutdown) (TCPL 201) |

15:30 - 16:00 | Coffee Break (TCPL Foyer) |

16:00 - 18:00 | Problem session (continued) (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) |

Tuesday, October 1 | |
---|---|

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 |
Freddie Illingworth: Colouring hypergraphs and their intersection spectrums ↓ The chromatic number, $\chi(H)$, of a hypergraph $H$ is usually defined as
the smallest number of colours needed to colour the vertices of $H$ so that
every edge receives at least two colours. The intersection spectrum, $I(H)$,
is the set of all intersection sizes $\lvert e \cap f \rvert$ of distinct
edges $e, f \in E(H)$. That these two notions are related goes back to the
observations of Erdos and Lovasz that if $\chi(H) > 2$, then $1 \in
I(H)$, and if $\chi(H) > 3$, then $0, 1 \in I(H)$.
I will survey some open problems and discuss recent work with Kevin Hendrey,
Nina Kamcev, and Jane Tan where we generalise the second observation to
colourings where all edges receive at least $c$ colours, resolving a problem
of Blais, Weinstein, and Yoshida. (TCPL 201) |

10:00 - 10:30 | Coffee Break (TCPL Foyer) |

10:30 - 11:00 |
Janos Pach: Some geometric nonsense related to colourings ↓ There are many geometric and combinatorial problems that can be reformulated
as problems about chromatic numbers of certain graphs. For instance, let $G$
be a graph drawn in the plane with possibly crossing edges (``arcs'').
Associate with $G$ another graph $G'$ whose vertices are the edges of $G$,
two of them being connected by an edge in $G'$ if the corresponding arcs
intersect. If we consider the arcs open curves, the chromatic number
of $G'$ is the minimum number of plane graphs $G$ can be decomposed into.
What can we say about this parameter? (TCPL 201) |

11:00 - 11:30 |
Natasha Morrison: Spanning trees in pseudorandom graphs via sorting networks ↓ We show that \((n,d,\lambda)\)-graphs with
\(\lambda=O(d/log^3n)\) are universal with respect to all bounded degree
spanning trees. This significantly improves upon the previous best bound due
to Han and Yang, and makes progress towards a problem of Alon, Krivelevich,
and Sudakov from 2007. The key new idea in our proof relies on the existence
of sorting networks of logarithmic depth, as given by a celebrated
construction of Ajtai, Komlos and Szemeredi, with further
applications to the vertex disjoint paths problem. Joint work with Joseph
Hyde, Alp Muyesser, and Matías Pavez-Signé. (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) |

13:00 - 14:00 |
Agelos Georgakopoulos: A survey of coarse graph theory ↓ I will survey recent results and open questions on `coarse graph theory',
an emerging area that combines ideas from graph theory and coarse geometry. (TCPL 201) |

15:00 - 15:30 | Coffee Break (TCPL Foyer) |

15:30 - 16:00 |
Paul Wollan: Some results on coarse structure ↓ We look at extending several classical results to the coarse setting, including the structure of graphs excluding a $K_4$ minor and Gallai's theorem on packing $A$-paths.
This is joint work with Sandra Albrechtsen, Raphael Jacobs, and Paul Knappe. (TCPL 201) |

16:00 - 16:30 |
Liana Yepremyan: Counterexample to Babai's lonely colour conjecture ↓ Motivated by colouring minimal Cayley graphs, in 1978, Babai conjectured
that no-lonely-colour graphs have bounded chromatic number.
We disprove this in a strong sense by constructing graphs of arbitrarily
large girth and chromatic number that have a proper edge-colouring in which
each cycle contains no colour exactly once. Joint work with Meike Hatzel and
James Davies. (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) |

Wednesday, October 2 | |
---|---|

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 - 09:30 |
Antonio Girao: Strongly restricted partitions of graphs with bounded clique number ↓ Given a graph $G$ and any $\epsilon>0,$ say that a set $S\subseteq V(G)$ is weakly $\epsilon$-restricted if $G[S]$ or its complement contains at most $\epsilon|S|^2$ edges. A classical theorem of Rodl states that $H$-free graphs contain linear-sized sets which are restricted in this way.
$$ $$
Theorem [Rodl, 1985]
For every graph $H$ and any $\epsilon>0,$ there exists $\delta>0$ with the following property: if $G$ is an $H$-free graph, then there is some subset $S\subseteq V(G)$ with $|S| \ge \delta |G|,$ such that $S$ is weakly $\epsilon$-restricted.
$$ $$
For a given graph $H$, how large can we take $\delta$ as a function of $\epsilon$ in the above? If it is the case that we may take $\delta$ to be polynomial in $\epsilon,$ then an easy application of Turan's Theorem shows that $H$ would have the Erdos-Hajnal property. A partition version follows easily.
$$ $$
Theorem:
For every graph $H$ and for all $\epsilon>0,$ there exists $N\ge 1$ such that any $H$-free graph $G$ partitions into at most $N$ sets, all of which weakly $\epsilon$-restricted.
$$ $$
Given a graph $G$ and any $\epsilon>0,$ say now that a set $S\subseteq V(G)$ is strongly $\epsilon$-restricted if $G[S]$ or its complement has maximum degree at most $\epsilon|S|$.
A natural question would be to determine whether the 'strong' version of the Rodl partitions also hold i.e. each part is strongly $\varepsilon$-restricted.
It turns out that this is the case, however, this was only proved recently by Chudnovsky, Scott, Seymour and Spirkl.
In this talk we will show that a polynomial bound holds in $\varepsilon$ for $K_r$-free graphs.
$$ $$
Theorem:
For every $r\geq 2$ and $\epsilon>0$, there is $C<0$ such that every $K_r$-free graph $G$ has a vertex partition into at most $\epsilon^C$ parts $A_1,\ldots , A_t$ each of which has $\Delta(G[A_i])\leq \epsilon |A_i|$. (TCPL 201) |

09:30 - 10:00 |
Sang-il Oum: Bounding the chromatic number of t-perfect graphs ↓ Perfect graphs can be described as the graphs whose stable set polytopes are defined by their
non-negativity and clique inequalities (including edge inequalities).
In 1975, Chvatal defined an analogous class called t-perfect graphs, which are the graphs whose stable
set polytopes are defined by their non-negativity, edge and odd circuit inequalities.
We show that t-perfect graphs are 150000-colourable.
This is the first finite bound on the chromatic number of t-perfect graphs, and answers a question of
Shepherd from 1995.
This is joint work with Maria Chudnovsky, Linda Cook, James Davies, and Jane Tan. (TCPL 201) |

10:00 - 10:30 | Coffee Break (TCPL Foyer) |

10:30 - 11:00 |
Zdenek Dvorak: Towards a characterization of minimal non-4-colourable graphs of crossing number one ↓ It is natural to try to generalize the famous Four Color Theorem to ``nearly
planar'' graphs. However, already for the simplest generalization -- to
graphs
that can be drawn in the plane with only one crossing -- one runs into a
substantial difficulty: It is easy to construct infinitely many (minimal)
counterexamples,
i.e., non-4-colorable graphs of crossing number one. Moreover, as the
constructions
are usually somewhat ad-hoc, it seems likely that many other counterexamples
exist, and possibly have quite different structure. To shed some light on
the
situation, we use computer-assisted enumeration to exhaustively list all
minimal counterexamples with up to around 25 vertices, analyze the
constructions from
which they arise, and propose conjectures concerning their properties.
This is joint work with Bernard Lidicky and Bojan Mohar. (TCPL 201) |

11:00 - 11:30 |
James Davies: Non-measurable colourings avoiding large distances ↓ In 1983, Furstenberg, Katznelson, and Weiss proved that for every finite measurable colouring of the plane, there
exists a $d_0$ such that for every $d \ge d_0$ there is a monochromatic pair of points at distance $d$. In contrast to
this, we show that there is a finite colouring avoiding arbitrarily large distances.
Joint work with Rutger Campbell. (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) |

13:30 - 17:30 | Free Afternoon (Banff National Park) |

17:30 - 19:30 |
Dinner ↓ |

Thursday, October 3 | |
---|---|

07:00 - 08:45 |
Breakfast ↓ |

09:00 - 10:00 |
Bartosz Walczak: Excluding a Burling graph ↓ A class of graphs $\mathcal{G}$ is $\chi$-bounded if there is a function
$f\colon\mathbb{N}\to\mathbb{N}$ such that every graph in $\mathcal{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 $\chi$-bounded because they contain a specific
infinite family $\{B_k\}_{k=1}^\infty$ of triangle-free graphs with
unbounded chromatic number, first constructed by Burling.
We show that if $\mathcal{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 $\mathcal{G}$ not
being $\chi$-bounded; that is, there is a function
$f\colon\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ such that every graph in
$\mathcal{G}$ with chromatic number greater than $f(k,\ell)$ contains a
$k$-clique or an induced copy of $B_\ell$.
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
$\tilde{b}_i(G)$ denote the $i$-th reduced Betti number of $I(G)$, and let
$b(G)$ denote the sum of $\tilde{b}_i(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)\le 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\cap B=\emptyset$ 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 ↓ |

14:00 - 15:00 |
Louis Esperet: The clustered Hadwiger conjecture ↓ We prove that every $K_h$-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 $K_{s,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 $K_{s,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 $H $as 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(\sqrt{n}\log^2 n)$.
Equivalently, every $n$-vertex planar graph $G$ has a set $X$ of
$O(\sqrt{n}\log^2 n)$ vertices such that $G-X$ has bandwidth.
$O(\sqrt{n}\log^2 n)$. 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 ↓ |

Friday, October 4 | |
---|---|

07:00 - 08:45 |
Breakfast ↓ |

10:00 - 10:30 | Coffee Break (TCPL Foyer) |

10:30 - 11:00 |
Checkout by 11AM ↓ 5-day workshop participants are welcome to use BIRS facilities (TCPL ) until 3 pm on Friday, although participants are still required to checkout of the guest rooms by 11AM. (Front Desk - Professional Development Centre) |

12:00 - 13:30 | Lunch from 11:30 to 13:30 (Vistas Dining Room) |