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