Combinatorial Carousel 22 April 2022

A casual afternoon discussing combinatorial questions and answers.

 12:45ish Welcome 13:00ish Penny Haxell The Integrality Gap for the Santa Claus Problem  ± In the max-min allocation problem a set $P$ of players are to be allocated disjoint subsets of a set $R$ of indivisible resources, such that the minimum utility among all players is maximized. In the restricted variant, also known as the Santa Claus problem, each resource ("toy") has an intrinsic positive value, and each player ("child") covets a subset of the resources. Thus Santa wants to distribute the toys amongst the children, while (to satisfy jealous parents?) wishing to maximize the minimum total value of toys received by each child. This problem turns out to have a natural reformulation in terms of hypergraph matching. Bez\'akov\'a and Dani showed that the Santa Claus problem is NP-hard to approximate within a factor less than $2$, consequently a great deal of work has focused on approximate solutions. To date, the principal approach for obtaining approximation algorithms has been via the Configuration LP of Bansal and Sviridenko, and bounds on its integrality gap. The existing algorithms and integrality gap estimations tend to be based one way or another on a combinatorial local search argument for finding perfect matchings in certain hypergraphs. Here we introduce a different approach, which in particular replaces the local search technique with the use of topological methods for finding hypergraph matchings. This yields substantial improvements in the integrality gap of the CLP, from the previously best known bound of $3.808$ for the general problem to $3.534$. We also address the $(1,\varepsilon)$-restricted version, in which resources can take only two values, and improve the integrality gap in most cases. (joint work with Tibor Szab\'o) Carla Groenland Graphs of low average degree without independent transversals  ± An independent transversal of a graph G with a vertex partition P is an independent set of G intersecting each block of P in a single vertex. Wanless and Wood proved that if each block of P has size at least t and the average degree of vertices in each block is at most t/4, then an independent transversal of P exists. We present a construction showing that this result is optimal: for any eps > 0 and sufficiently large t, there is a family of forests with vertex partitions whose block size is at least t, average degree of vertices in each block is at most (1/4 + eps)t, and there is no independent transversal. This is joint work with Tomas Kaiser, Oscar Treffers and Matthew Wales. Wouter Cames van Batenburg The list-packing number  ± List-colouring is an influential and classic topic in graph theory. We initiate the study of a natural strengthening of this problem, where instead of one list-colouring, we seek many in parallel. Given the assignment of a list $L(v)$ of $k$ colours to each vertex $v$ of a graph $G$, we study the existence of $k$ pairwise-disjoint proper colourings of $G$ using colours from these lists. We refer to this as a list-packing and we define the list-packing number $\chi_\ell^{\star}(G)$ as the smallest $k$ for which every list-assignment of $G$ admits a list-packing. We prove several results that (asymptotically) match the best-known bounds for the usual list chromatic number. Our main open question is whether $\chi_\ell^\star(G)$ can be bounded by a constant times the list chromatic number. (Joint work with Stijn Cambie, Ewan Davies and Ross Kang) Stijn Cambie Regular Cereceda's Conjecture  ± The reconfiguration graph ${\cal C}_k(G)$ for the $k$-colourings of a graph $G$ has a vertex for each proper $k$-colouring of $G$, and two vertices of ${\cal C}_k(G)$ are adjacent precisely when those $k$-colourings differ on a single vertex of $G$. Much work has focused on bounding the maximum value of ${\rm diam} {\cal C}_k(G)$ over all $n$-vertex graphs $G$. One of the most famous conjectures related related to ${\cal C}_k(G)$ is Cereceda's conjecture, which says that if $k \ge {\rm degen}(G) + 2$, the diameter of ${\cal C}_k(G)$ is $O(n^2)$. In this talk, we give some ideas towards a precise form for Cereceda's conjecture, when restricting to regular graphs. This is based on joint work with Wouter Cames van Batenburg and Daniel Cranston. This project originates from the online workshop Graph Reconfiguration of the Sparse Graphs Coalition. 16:00ish Closing

This impromptu meeting was organised by Ross Kang in conjunction with Stijn's PhD defence.

Congratulations Dr. Stijn Cambie!

Last modification: