Please send your open problems and comments to Sophie Spirkl to be included here.
Click here to download a PDF version.
The webpage of the workshop can be found here.
Let G be a graph and D a tournament, with the same vertex set. For each vertex v, A(v) denotes its outneighbour set in D. Suppose that for every vertex v, the chromatic number of G[A(v)] is at most k. Is the chromatic number of G bounded by some function of k? This is true with chromatic number replaced by fractional chromatic number. (Alex Scott and Paul Seymour)
The particular case of Borsuk graphs is very interesting and amounts to the existence of a tournament (or in fact semicomplete digraph) whose vertices are the points of the sphere Sd and out-neighborhoods have low chromatic number.
For instance bipartite outneighborhoods would be that every out-neighborhood avoids a "fat equator" of the sphere. I think that the following question is extremely close: A good function f is a continuous function of Sd into the compact sets of Sd (here f(x) is the outneighborhood of x) such that every f(x) is disjoint from some equator of Sd.
If there exists such an f which is semicomplete, i. e. where for all x, y we have x in f(y) or y in f(x), then we have a counterexample: this defines a semicomplete digraph with bipartite outneighborhoods (for some suitably chosen ε-Borsuk graph).
But I think that good functions are never semicomplete, indeed if we now interpret f(x) as the north pole of the avoided equator, we have the equivalent question: Is it true that for every continuous function f from Sd into itself there is x, y such that f(x) is orthogonal to y, and f(y) is orthogonal to x (call these pairs xy bi-independent)?
I think this is true (apart when d = 1 where it suffices to take any small rotation) and doable. In fact, I think that the graph of bi-independent pairs is always of some large chromatic number (maybe d). If this is not the case, we can again form a counterexample I think. (Stéphan Thomassé)
In response to "Is it true that for every continuous function f from Sd into itself there is x, y such that f(x) is orthogonal to y, and f(y) is orthogonal to x (call these pairs xy bi-independent)?".
I think this much is true by an elementary argument. For each point x, let S(x) be the points in Sd that are orthogonal to x (i. e. the copy of Sd-1 around the equator). Then let T(x) = S(f(x)), so everything in T(x) is orthogonal to f(x). Now let I(x) be the set of inner products
{⟨f(y), x⟩ : y ∈ T(x)}
So I(x) is an interval, say [m(x), M(x)]. If 0 is in I(x) we are done, as we can just pick a y that witnesses this. If 0 is never in I(x) then, as m(x) and M(x) are continuous functions of x, we see that I(x) is always the same sign. Let us show that this does not happen: pick x, x' antipodal and consider the intersection of T(x) and T(x'). This must be nonempty (here is where we use d > 1) and so we can pick y in both. Then ⟨f(y), x⟩ and ⟨f(y), x'⟩ have opposite signs, but the first is in I(x) and the second is in I(x').
Does that make sense? I would hope it to be possible to prove that the bi-independent pairs have large χ (for instance, there is room to pick several points and then use the fact that every set of d - 1 equators has a common point). (Alex Scott)
Suppose G is an Eulerian digraph which is strongly 100-edge-connected. Must there exist a partition of E(G) into {A, B} so that both G ∖ A and G ∖ B are strongly connected? (Matt DeVos)
If A, B are finite sets of integers and |A + B| < |A| + 2|B| - 3, must A be contained in an arithmetic progression of length at most |A| + |B|? (Matt DeVos)
Update: False, but is it true that if |A + B| < |A| + |B| + √ |A||B| - 3 and |A| ≤ |B|, then A is contained in an arithmetic progression of length |A + B| - |A| + 1? (Matt DeVos)
The broadcast domination number γb(G) of a graph G is the minimum integer d such that there are pairs (v1, d1), …, (vℓ, dℓ), where vi is a vertex of G and di is a positive integer, such that d1 + … + dℓ ≤ d, and, for every vertex u of G, there is some index i with distG(u, vi) ≤ di. Surprisingly, the broadcast domination number can be computed in polynomial time for every graph [11]. Considering the dual of the LP relaxation of a natural IP formulation for broadcast domination, motivated the definition of so-called multipackings as dual objects (see [16] for a survey). A set M of vertices of G is a multipacking of G if for every vertex u of G and every integer d between 1 and the diameter of G, the set M contains at most d vertices at distance at most d from u. The duality of the corresponding LP relaxations implies that the multipacking number mp(G), defined as the maximum cardinality of a multipacking in G, is a natural lower bound on the broadcast domination number γb(G). It has been shown (cf. [16]) that the duality gap is 0 for trees and, more generally, strongly chordal graphs. Since the diameter is a trivial upper bound on γb(G) and the set containing every third vertex of a longest shortest path is easily seen to be a multipacking, it follows that γb(G) ≤ 3mp(G). Can this trivial upper bound be improved? Not even something like 3 - ε seems to be known. Can this bound be improved at least within certain graph classes? A simple candidate class to look at first would be cacti. (Dieter Rautenbach)
The burning number b(G) of a graph G [4] is the smallest integer k for which there are vertices x1, …, xk such that for every vertex u of G, there is some index i with distG(u, xi) ≤ k - i. Using the fact that 1 + 3 + 5 + … + (2k - 1) = k2, it follows easily that b(Pn) = ⌈√ n ⌉. Bonato et al. [4] conjecture that b(G) ≤ ⌈√ n(G) ⌉ for every connected graph G. They prove b(G) ≤ 2√ n(G) + 1, which we [3] managed to improve to b(G) ≤ 1.3√ n + 3. Clearly, it suffices to show the conjecture for trees, which seems to indicate that it might be doable. Surprisingly though, the calculation of the burning number is already NP-hard for trees with exactly one vertex of degree at least 3 [3]. (Dieter Rautenbach)
Update: Reformulation -- given a tree of radius k2, can it be covered with trees with radii 0, 1, ..., k? (Eli Berger)
A graph is a (q, q - 4)-graph for some integer q at least 4 if every q vertices induce at most q - 4 distinct P4s. Clearly, cographs coincide with (4, 0)-graphs. Quite surprisingly, (q, q - 4)-graphs have a very restricted structure [1], which allows to solve many problems efficiently for such graphs. Motivated by some problems on P5-free graphs, we were recently led to consider graphs which might be called (q, q - 5)-graphs for some integer q at least 5, where every q vertices induce at most q - 5 distinct P5s. Again, P5-free graphs coincide with (5, 0)-graphs. Do (q, q - 5)-graphs have a nice structure? Do at least triangle-free (q, q - 5)-graphs have a nice structure? A triangle-free (6, 1)-graph for instance is either P5-free or a subdivision of a star. (Mitre Dourado, Lucia Penso, Dieter Rautenbach)
Given a collection N of subsets of some finite ground set V, we consider the function
f : 2V → ℕ0 : S ↦ minn∈N |n ∖ S|.
For which collections N is this function submodular? If N consists of all k-element subsets of V for some integer k, then f(S) = min {k - |S|, 0}, which is submodular. Is this maybe (essentially) the only kind of collection for which f is submodular? We are interested in this question because submodularity of f would imply a logarithmic approximation guarantee for some simple greedy algorithm we considered. (Carlos Vinícius Lima, Dieter Rautenbach, Uéverton Souza, Jayme Szwarcfiter)
Update: Bases of matroids also satisfy this. (Paul Seymour)
Update: This characterizes set systems with this property, but the function is supermodular. (Sang-il Oum)
Let V be a set of order n. For which vectors (t0, t1, …, tn) does there exist a set system T ⊆ 2V with
∀X ∈ T : ∀Y ⊆ V : X ⊆ Y ⇒ Y ∈ T
such that ti = |T ∩ (Vi)| for every i? Here (Vi) is the set of all i-element subsets of V . (Carlos Vinícius Lima, Dieter Rautenbach, Uéverton Souza, Jayme Szwarcfiter)
Update: Kruskal-Katona theorem. (Peter Keevash)
Let c, ε > 0. We say that a graph G has (c, ε)-separators if every subgraph H of G has a balanced separator of order at most c|V(H)|1-ε.
Is there a way to "efficiently certify" that G has this property, at least in an approximate sense? Formally, do there exists c', ε' > 0 and a polynomial-time algorithm A such that
for each graph G with (c, ε)-separators, there exists a polynomial-size witness X such that A accepts (G, X), and
if G does not have (c', ε')-separators, then there does not exist any polynomial-size witness X such that A accepts (G, X).
(Zdeněk Dvořák)
Conjecture (Brewster et al. [5]): For k ≥ 3, if χ(G) > k, then G has at least (k + 1)(k - 1)!/2 cycles of length 0 mod k.
It follows from a lovely argument of Wrochna (unpublished; see [5]) that every graph G with χ(G) > k contains at least (k - 1)!/2 cycles of length 0 mod k. If the above conjecture is true, then the complete graph on k + 1 vertices would be a tight example. The conjecture is open for every k ≥ 3. (Jon Noel)
Let H be a fixed graph. A graph G on n vertices is said to be weakly H-saturated if the edges of E(Kn) ∖ E(G) can be added to G, one edge at a time, so that every edge completes a copy of H when it is added. Let Qd be the hypergraph of dimension d. What is the minimum number of edges in a weakly Qd-saturated graph on n ≥ 2d vertices? A related, but probably very different, problem was solved by Morrison, Noel and Scott [12]; many related problems and 'weak saturation' references can be found there. (Jon Noel)
Let G be an edge-colored d-regular bipartite graph where every color appears at most d/100 times. Does G have a perfect rainbow matching? (A perfect matching is rainbow if every color appears at most once in it). This is true if G is the complete bipartite graph [8]. (Guillem Perarnau)
Conjecture: For every graph G