Open Problems From My Papers and Theses

If you have solved a problem from one of my papers and I have not indicated it here, then please let ​me know by e-mail to noelj@uvic.ca!

32. Turán Colourings in Off-Diagonal Ramsey Multiplicity

    • Question 6.1: Open
    • Question 6.2: Open
    • Question 6.3: Open
    • Question 6.4: Open


31. Off-Diagonal Commonality of Graphs via Entropy

    • Problem 8.1: Open, but some progress was made here, here and here
    • Question 8.2: Open
    • Question 8.3: Open
    • Conjecture 8.4: Open


30. Off-Diagonal Ramsey Multiplicity

    • Problem 6.1: Open
    • Problem 6.2: Open
    • Problem 6.3: Open
    • Conjecture 6.3: Open


29. Sidorenko-Type Inequalities for Pairs of Trees

    • Conjecture 8.1: Open


28. Disconnected Common Graphs via Supersaturation

    • Conjecture 7.1: Open
    • Question 7.2: Open


27. Common Pairs of Graphs

    • Conjecture 1.2: Open
    • Question 1.5: Open
    • Problem 1.10: Open
    • Conjecture 1.12: Open
    • Conjecture 7.1: Open
    • Conjecture 7.2: Open
    • Conjecture 9.7 from an earlier preprint was confirmed here


25. Six Permutation Patterns Force Quasirandomness

    • Conjecture 5.1: Open
    • Conjecture 5.3: Open
    • Problem 5.4: Open


24. Extremal Bounds for Three-Neighbour Bootstrap Percolation in Dimensions Two and ​Three

    • Conjecture 7.1: Open
    • Conjecture 7.2: Open
    • Problem 7.3: Open
    • Problem 7.4: Open
    • Problem 7.8: Open


23. On the Running Time of Hypergraph Bootstrap Percolation

    • Conjecture 25: Disproved here and here
    • Question 26: Answered affirmatively here and here


22. Density maximizers of layered permutations

    • Problem 1: Open
    • Problem 2: Open
    • Problem 3: Open
    • Problem 4: Open
    • Problem 5: Open


20. Non-bipartite k-common graphs

    • Problem 1: Settled positively here
    • Problem 2: Open


12. Graph Homomorphism Reconfiguration and Frozen H-Colourings

    • Question 4.1: Open


10. Extremal Bounds for Bootstrap Percolation in the Hypercube

    • Question 6.1: Open
    • Problem 6.2: Open
    • Question 6.3: Open
    • Problem 6.4: Solved here


8. Supersaturation in Posets and Applications Involving the Container Method

    • Conjecture 7.1: Disproved here
    • Conjecture 7.2: Open but essentially confirmed here


7. Saturation in the Hypercube and Bootstrap Percolation

    • Question 4.1: Open
    • Question 4.2: Open
    • Question 4.3: Open
    • Question 4.4: Open
    • problem 4.5: Open
    • Problem 4.6: Open
    • Problem 4.7: Open
    • Problem 4.8: Open
    • Question 4.9: Open


6. A Dichotomy Theorem for Circular Colouring Reconfiguration

    • Conjecture 22: Open but some progress was made here


5. Mixing Homomorphisms, Recolorings, and Extending Circular Precolorings

    • Question 7.7: Open
    • Question 7.8: Open
    • Conjecture 7.9: Proved here
    • Question 7.10: Open
    • Question 7.11: Open


3. Beyond Ohba's Conjecture: A bound on the choice number of k-chromatic graphs with n ​vertices

    • Problem 1.5: Open


2. On Saturated k-Sperner Systems

    • Problem 5: Open


PhD Thesis

    • Question 2.30: Open
    • Problem 2.33: Open
    • Conjecture 4.9: Open


Master’s Thesis

    • Conjecture 3.8: Proven here
    • Conjecture 5.6: Open
    • Conjecture 5.8: Open
    • Problem 7.1: Solved here

Links to Other Open Problem Pages

Below, I have compiled a list of links to open problems.


• A List of Open Problems for Imre Leader's 60th Birthday: 2023.

• Barbados Graph Theory Workshop: 2022, 2019, 2018, 2017, 2016, 2015, 2014.

• BIRS Workshop on "New Perspectives in Colouring and Structure": 2020.

• Matroid Union open problem session (2020).

• Structural Graph Theory Workshop at Gułtowy: 2019.

• Workshop on Combinatorial Reconfiguration: 2019.

• Workshop Cycles and Colourings: 2018.

• Mittag-Leffler programme on Graphs, Hypergraphs, and Computing: 2014.

• Graduate Research Workshop in Combinatorics: multiple years.

• Graphs and Randomness at IMPA: 2018.

• Midrasha Mathematicae: In and Around Combinatorics: 2015.

• Beyond Randomized Rounding and the Probabilistic Method at the Simons Institute: 2019.

• The Egeváry Research Group maintains an open problem forum called Egres Open.

• Alexey Pokrovskiy's open problem page.

• Louis Esperet's open problem page.

• Stefan Steinerberger's open problem list.

• Joshua Cooper's open problem page.

• Boris Bukh's open problem page.

• Doug West's open problem page.

• The Rutgers DIMACS page on open problems for undergraduates.

• Open problems from Schrijver's book "Combinatorial Optimization - Polyhedra and Efficiency" ​can be found here.

• Some of Erdős' (many) problem papers: Fan Chung's list, another list maintained by Fan ​Chung, 1971, 1973, 1974, 1975, 1976, 1978, 1978, 1979, 1979, 1979, 1980, 1984, 1984, 1988, ​1995, 1997, 1997.