Ewan Davies

A picture of me

I am an assistant professor in the Department of Computer Science at Colorado State University.

My research interests include approximate counting and sampling, probabilistic combinatorics, and extremal graph theory. I investigate high-dimensional combinatorial spaces and whether they can be efficiently enumerated or explored. My work frequently combines ideas from computer science, mathematics, and physics.

My department is able to fund a number of MS and PhD students via Graduate Teaching Assistant (GTA) positions, though appointments are competitive. If you are a strong candidate interested in doing Master's or PhD research with me, then get in touch and we can discuss applying to CSU and funding options.

Email: research@ewandavies.org, ewan.davies@colostate.edu

Links: arXiv, DBLP, Google Scholar, MathSciNet, ORCID, Scopus, Web of Science, zbMATH

My coauthors include:

Unfortunately, not every journal or conference I publish in has a permissive open access policy. I try to ensure my work is accessible, e.g. on some open preprint server, and encourage you to do the same. The Sherpa Romeo service makes navigating publisher preprint policies a little easier than it might be otherwise.

Upcoming events

Preprints

  1. Sampling List Packings
    E. Camrud, E. Davies, A. Karduna, H. Lee
  2. Approximately Counting Independent Sets in Dense Bipartite Graphs via Subspace Enumeration
    C. Carlson, E. Davies, A. Kolla, A. Potukuchi
  3. List Packing Number of Bounded Degree Graphs
    S. Cambie, W. Cames van Batenburg, E. Davies, R.J. Kang
  4. Graph structure via local occupancy
    E. Davies, R.J. Kang, F. Pirot, J.-S. Sereni
  5. Regularity inheritance in hypergraphs
    P. Allen, E. Davies, J. Skokan

Publications

  1. Algorithms for the Ferromagnetic Potts Model on Expanders
    C. Carlson, E. Davies, N. Fraiman, A. Kolla, A. Potukuchi, C. Yap
    Combinatorics, Probability and Computing (2024), to appear
  2. Efficient algorithms for the Potts model on small-set expanders
    C. Carlson, E. Davies, A. Kolla
    Chicago Journal of Theoretical Computer Science (2024), to appear
  3. An algorithmic framework for colouring locally sparse graphs
    E. Davies, R.J. Kang, F. Pirot, J.-S. Sereni
    Theory of Computing (2024), to appear
  4. A Robust Corrádi–Hajnal Theorem
    P. Allen, J. Böttcher, J. Corsten, E. Davies, M. Jenssen, P. Morris, B. Roberts, J. Skokan
    Random Structures & Algorithms (2024), to appear
  5. Packing list-colourings
    S. Cambie, W. Cames van Batenburg, E. Davies, R.J. Kang
    Random Structures & Algorithms 64 (2024), 62–93
  6. Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs
    E. Davies, W. Perkins
    SIAM Journal on Computing 52 (2023), 618–640
  7. Algorithms for the Ferromagnetic Potts Model on Expanders
    C. Carlson, E. Davies, N. Fraiman, A. Kolla, A. Potukuchi, C. Yap
    2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) (2022), 344–355
  8. Computational Thresholds for the Fixed-Magnetization Ising Model
    C. Carlson, E. Davies, A. Kolla, W. Perkins
    Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC) (2022), 1459–1472
  9. The χχ-Ramsey Problem for Triangle-Free Graphs
    E. Davies, F. Illingworth
    SIAM Journal on Discrete Mathematics (2022), 1124–1134
  10. Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs
    E. Davies, W. Perkins
    48th International Colloquium on Automata, Languages, and Programming (ICALP) 198 (2021), 62:1–62:18
  11. An Approximate Blow-up Lemma for Sparse Hypergraphs
    P. Allen, J. Böttcher, E.K. Hng, J. Skokan, E. Davies
    Procedia Computer Science 195 (2021), 394–403
  12. A proof of the Upper Matching Conjecture for large graphs
    E. Davies, M. Jenssen, W. Perkins
    Journal of Combinatorial Theory, Series B 151 (2021), 393–416
  13. Occupancy fraction, fractional colouring, and triangle fraction
    E. Davies, R. de Joannis de Verclos, R.J. Kang, F. Pirot
    Journal of Graph Theory 97 (2021), 557–568
  14. On Zero-Free Regions for the Anti-Ferromagnetic Potts Model on Bounded-Degree Graphs
    F. Bencs, E. Davies, V. Patel, G. Regts
    Annales De l’Institut Henri Poincaré D 8 (2021), 459–489
  15. Statistical Physics Approaches to Unique Games
    M. Coulson, E. Davies, A. Kolla, V. Patel, G. Regts
    35th Computational Complexity Conference (CCC) 169 (2020), 13:1–13:27
  16. Colouring triangle-free graphs with local list sizes
    E. Davies, R. de Joannis de Verclos, R.J. Kang, F. Pirot
    Random Structures & Algorithms 57 (2020), 730–744
  17. Counting proper colourings in 4-regular graphs via the Potts model
    E. Davies
    Electronic Journal of Combinatorics 25 (2018), P4.7
  18. Tight bounds on the coefficients of partition functions via stability
    E. Davies, M. Jenssen, W. Perkins, B. Roberts
    Journal of Combinatorial Theory, Series A 160 (2018), 1–30
  19. Extremes of the internal energy of the Potts model on cubic graphs
    E. Davies, M. Jenssen, W. Perkins, B. Roberts
    Random Structures & Algorithms 53 (2018), 59–75
  20. On the average size of independent sets in triangle-free graphs
    E. Davies, M. Jenssen, W. Perkins, B. Roberts
    Proceedings of the American Mathematical Society 146 (2018), 111–124
  21. Multicolour Ramsey numbers of paths and even cycles
    E. Davies, M. Jenssen, B. Roberts
    European Journal of Combinatorics 63 (2017), 124–133
  22. Independent Sets, Matchings, and Occupancy Fractions
    E. Davies, M. Jenssen, W. Perkins, B. Roberts
    Journal of the London Mathematical Society 96 (2017), 47–66
  23. Tight bounds on the coefficients of partition functions via stability (extended abstract)
    E. Davies, M. Jenssen, W. Perkins, B. Roberts
    Electronic Notes in Discrete Mathematics 61 (2017), 317–321
  24. Counting in hypergraphs via regularity inheritance (extended abstract)
    E. Davies
    Electronic Notes in Discrete Mathematics 49 (2015), 413–417

Other work

  1. Extremal and probabilistic results for regular graphs
    E. Davies
    PhD thesis, The London School of Economics and Political Science (2017)

Current

Past

Upcoming events

Past events

  • 6 Oct 2023
    Georgia Tech Combinatorics Seminar | Atlanta, GA
    Title: Packing colorings
  • 25 Sep 2023
    Discrete Seminar, University of Colorado Denver | Denver, CO
    Title: Why not make coloring even more difficult?
  • 21 Sep 2023
    Applied Mathematics and Statistics (AMS) Seminar, Johns Hopkins University | Baltimore, MD
    Title: Counting independent sets in dense bipartite graphs
  • 7–12 Aug 2023
    Random Theory 2023 | Estes Park, CO
  • 13–14 May 2023
  • 27 Nov – 2 Dec 2022
  • 31 Oct – 3 Nov 2022
    FOCS 2022 | Denver, CO
  • 8–12 Aug 2022
    New tools for optimal mixing of Markov chains | Santa Barbara, CA
  • 18–19 May 2022
    DIMACS Workshop on Entropy and Optimization | New Brunswick, NJ (Online)
  • 14–15 May 2022
    AMS Spring Western Sectional Meeting | Denver, CO (Online)
    Talk: Bounding the (list) chromatic number of triangle-free graphs (15 May, slides)
  • 14–15 May 2022
  • 3 Mar 2022
    Title: The Complexity of Approximate Counting Problems
  • 27 Sep 2021
    Title: Graph coloring, independent transversals and packing
  • 12–16 Jul 2021
    ICALP 2021 | Glasgow, Scotland (Online)
  • 17–21 May 2021
    Extremal and algorithmic aspects of partition functions, Sparse Graphs Coalition | Online
  • 8–12 Mar 2021
    Entropy Compression and Related Methods, Sparse Graphs Coalition | Online
    Talk: The cluster expansion, Lovász local lemma and algorithms (10 Mar)
  • 19 Feb 2021
    Title: Independent sets of a given size
  • 8 Feb 2021
    Title: Independent sets of a given size
  • 14–16 Dec 2020
  • 21–25 Sep 2020
    Computational Phase Transitions | Berkeley, CA (Online)
  • 8–11 Sep 2020
    Geometry of Polynomials Reunion | Berkeley, CA (Online)
  • 19–28 Aug 2020
  • 28–31 Jul 2020
    Computational Complexity Conference (CCC) 2020 | Saarbrücken, Germany (Online)
    Talk: Statistical physics approaches to Unique Games (29 Jul)
  • 4–5 Apr 2020
  • 19 Mar 2020
    POSTPONED Computer Science Theory Seminar, UIC | Chicago, IL
    Title: Statistical physics approaches to Unique Games (with Alex Kolla)
  • 12 Feb 2020
    Discrete Mathematics Seminar, KdVI / CWI | Amsterdam, Netherlands
    Title: Statistical physics approaches to Unique Games
  • 22 Jan 2020
    CS Theory Seminar, CU Boulder | Boulder, CO
    Title: Statistical physics approaches to Unique Games
  • 25 Sep 2019
    CS Theory Seminar, CU Boulder | Boulder, CO
    Title: Graph colouring and the hard-core model
  • 15 Jan – 17 May 2019
    Talk: Colouring locally sparse graphs via the hard-core model (17 Apr)
  • 23–24 Aug 2018
    Talk: Fractional colouring of triangle-free graphs via the hard-core model (24 Aug)
  • 9–10 May 2018
  • 1 May 2018
    Applied Stochastics Seminar, Radboud University | Nijmegen, Netherlands
    Title: Using Gibbs measures in extremal combinatorics
  • 26–30 Mar 2018
    Workshop on Graph limits | Janov, Czechia
    Talk: Tight bounds on the coefficients of partition functions via stability (30 Mar)
  • 19 Feb – 4 Mar 2018
    Graphs and Randomness, IMPA | Rio de Janeiro, Brazil
  • 26 Jan 2018
    Discrete Mathematics Seminar, KdVI / CWI | Amsterdam, Netherlands
    Title: A new approach to Sidorenko's conjecture
  • 18 Oct 2017
    Discrete Mathematics Seminar, KdVI / CWI | Amsterdam, Netherlands
    Title: Shamir's problem revisited
  • 28 Aug – 1 Sep 2017
    EUROCOMB 2017 | Vienna, Austria
    Talk: Tight bounds on the coefficients of partition functions via stability (31 Aug, slides)
  • 17–21 Jul 2017
    Talk: Regularity inheritance in 3-uniform hypergraphs (20 Jul)
  • 11 May 2017
    Title: Tight bounds on the coefficients of partition functions via stability
  • 21 Feb 2017
    Combinatorics Seminar | Oxford, UK
    Title: Extremal problems on colourings in cubic graphs via the Potts model
  • 3 Feb 2017
    Discrete Mathematics Seminar, KdVI / CWI | Amsterdam, Netherlands
    Title: A probabilistic approach to bounding graph polynomials
  • 27 Jan 2017
    PhD Seminar on Combinatorics, Games and Optimisation, LSE | London, UK
    Title: A probabilistic approach to bounding graph polynomials
  • 3 Aug 2016
    Student Combinatorics Day (invited) | Birmingham, UK
    Title: On the average size of independent sets in triangle-free graphs (slides)
  • 8 Apr 2016
    Seminário de Teoria da Computação, Combinatória e Otimização | São Paulo, Brazil
    Title: Independent sets, matchings, and occupancy fractions II
  • 3 Nov 2015
    Discrete Geometry and Combinatorics Seminar, UCL | London, UK
    Title: Independent sets, matchings, and occupancy fractions
  • 9 Oct 2015
    Mathematics Lunchtime Seminar, LSE | London, UK
    Title: Independent sets, matchings, and occupancy fractions I
  • 31 Aug – 4 Sep 2015
    EUROCOMB 2015 | Bergen, Norway
    Talk: Counting in hypergraphs via regularity inheritance (31 Aug, slides)
  • 15 Apr 2015
    Title: Counting in hypergraphs via regularity inheritance
  • 9 Apr 2015
    Combinatorics Seminar, Freie Universität | Berlin, Germany
    Title: Regularity inheritance in 3-uniform hypergraphs
  • 3 Jul 2014
    Title: Robustness of triangle factors
  • 29 Nov 2013
    Mathematics Lunchtime Seminar, LSE | London, UK
    Title: Cycle packing

View my full CV as a pdf here

Positions held

Education

Awards

Some demonstrations of my work can be found here