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

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Meet and Greet at the BIRS Lounge (Professional Development Centre, 2nd floor)

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

A brief introduction to BIRS with important logistical information, technology instruction, and opportunity for participants to ask questions.

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.

https://www.overleaf.com/2573969174vfqphnjjgffz#5b4929

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

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.

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!

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

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.

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?

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é.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

I will survey recent results and open questions on `coarse graph theory', an emerging area that combines ideas from graph theory and coarse geometry.

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.

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.

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

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|$.

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.

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.

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.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

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.

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.

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.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

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.

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.

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

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

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.