Please send your open problems and comments to Linda Cook or Sophie Spirkl to be included here.

A (possibly slightly out-of-date) PDF version of this list is available here.

The webpage of the 2019 workshop can be found here.

See also the open problems from the 2016 workshop, the 2017 workshop, the 2018 workshop and the 2019 workshop.

    1. (David Wood)

    2. What is the minimum average degree that forces a subdivision of a complete bipartite graph Kt, t? In particular, is there a function f with f(t) ≤ o(t2), such that every graph with average degree at least f(t)$ contains a subdivision of Kt, t? It is known that quadratic average degree suffices. Indeed, for every graph H with p vertices and q edges, every graph with average degree at least 2p + 20q contains a subdivision of H. The proof uses the Thomas-Wollan result for linkages. This bound is tight up to a constant factor, whenever H has the property that any set of half the vertices of H induces a subgraph with at least εq edges (for fixed ε > 0). In this case, if the complete bipartite graph Kn, n contains a subdivision of H, then n ≥ εq. Of course, if H is a complete bipartite graph, then this example does not apply.

    3. (David Wood)

    4. What is the maximum chromatic number of graphs containing no Kt-subdivision? The answer is between Ω(t2/log t) and O(t2). The lower bound is by Erdős and Fajtlowicz, while the upper bound follows from results showing that linear connectivity forces a k-linkage. Perhaps the techniques by Norin-Song-Postle for improving the upper bound on the chromatic number of Kt-minor-free graphs might be relevant. Another relevant paper is here.

    5. (Nina Kamčev)

    6. Minimizing the number of edge-disjoint monochromatic copies of Kk (k fixed) in colourings of Kn is a line of research in Ramsey theory initiated by Erdős, Faudree, Gould, Jacobson and Lehel and motivated by Goodman's Theorem. Given a graph G, let ηk(G) be the maximal number of edge-disjoint copies of Kk in G. The focus so far has been on triangles (k=3). Throughout the question, G is an n-vertex graph and Gc is its complement. The main conjecture of Erdős et al. is that for any G, η3(G) + η3(Gc) ≥ (n2 ⁄ 12) (1+o(1)). The best known bound is n2 ⁄ 13 due to Keevash and Sudakov. The following modifications may be more accessible.

    7. Conjecture: (Erdős et al.) For any G, min{η3(G), η3(Gc)} ≥ (n2 ⁄ 20)(1+o(1)).

    8. Equality is asymptotically attained by a blow-up of C5. The following question has recently been answered by Tyomkyn for k=3.

    9. Question: (Alon and Linial) What is the minimum of ηk(G) over all n-vertex graphs G for which Gc is Kk-free, i.e. ηk(Gc) =0?

    10. Tyomkyn showed that any extremal example is "close to" a union of two cliques, that is, its complement is close to bipartite, so ηk(G) ≥ (n2 ⁄ 12)(1+o(1)). The extremal examples for larger k could still be unions of k−1 cliques. This is relevant to any solution attempt since all the known approaches use induction (after an LP-relaxation, every counterexample can be turned into a smaller one by removing a vertex), and of course characterising the extremal examples is a strong induction hypothesis.

    11. In contrast, the original conjecture of Erdős et al. has more complicated examples -- if G is a union of two copies of Kn ⁄ 2 with any n⁄8 additional edges, we still have η3(G) + η3(Gc) ≥ (n2 ⁄ 12)(1+o(1)). For k ≥ 5, they even construct graphs which "beat" the union of k−1 cliques.

    12. It might be interesting to modify Sidorenko's conjecture in this direction, that is, to replace Kk by any bipartite graph H, starting with C4. The definitions and questions extend naturally.

    13. Question: What is the minimum of ηC4(G) + ηC4(Gc) over n-vertex graphs G

    14. This problem looks rather different since C4-free graphs are sparse, and there is no entirely obvious blow-up structure that would minimise ηC4(G) + ηC4(Gc). Hence the first step is to find candidate graphs, or equivalently, colourings. (We remark that it is well-known that any 2-colouring of Kn contains asymptotically at least as many copies of C4 as the random colouring, which follows from Sidorenko's famous asymmetric version of this statement. However, G(n, 1/2) is very close to C4-decomposable and thus not suitable for the edge-disjoint setting.

    15. (Rose McCarty)

    16. What are the unavoidable induced subgraphs of large minimum degree? Kwan, Letzter, Sudakov, and Tran showed that every graph of sufficiently large minimum degree has either a Kt-subgraph or an induced, bipartite subgraph of minimum degree at least t, proving a conjecture of Esperet, Kang, and Thomassé.

    17. Question: Does every bipartite graph of sufficiently large minimum degree have either a Kt,t-subgraph or an induced, C4-free subgraph of minimum degree at least t?

    18. Kühn and Osthus showed this is true if we remove the "induced", and the Lovász Local Lemma can be used to prove this for regular graphs. Neither proof is too involved, and hopefully they can be combined.

    19. (Marthe Bonamy)

    20. Is every 4-regular graph of large enough girth 3-colourable?

    21. Remarks: Here is the official reference for this problem. It's the last interesting open case regarding how the chromatic number of k-regular graphs behaves with respect to higher girth. (We don't really care about k-regular, max degree k is the same). Exoo and Goedgebeur give examples with girth 7 that need 4 colors.

    22. (This submission was edited from email correspondence)

    23. (Marthe Bonamy)

    24. Take all planar graphs on n vertices. How small a graph can contain them all as induced subgraphs?

    25. Remarks: By using 5-degeneracy, it's not very hard to obtain that there's one on n6 vertices. There's a long history after that, but here is a very recent breakthrough by Dujmović, Esperet, Joret, Gavoille, Micek, and Morin. It says you can actually find them all (as induced subgraph) in a graph using n1 + o(1) vertices. I refuse to believe that this can be lowered to O(n) vertices.

    26. (This submission was edited from email correspondence)