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, 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. A Robust Corrádi–Hajnal Theorem
    P. Allen, J. Böttcher, J. Corsten, E. Davies, M. Jenssen, P. Morris, B. Roberts, J. Skokan
  2. Packing list-colourings
    S. Cambie, W. Cames van Batenburg, E. Davies, R.J. Kang
  3. An algorithmic framework for colouring locally sparse graphs
    E. Davies, R.J. Kang, F. Pirot, J.-S. Sereni
  4. Graph structure via local occupancy
    E. Davies, R.J. Kang, F. Pirot, J.-S. Sereni
  5. Efficient algorithms for the Potts model on small-set expanders
    C. Carlson, E. Davies, A. Kolla
  6. 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
    FOCS (2022), to appear
  2. 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, 1459–1472
  3. The χχ-Ramsey Problem for Triangle-Free Graphs
    E. Davies, F. Illingworth
    SIAM Journal on Discrete Mathematics (2022), 1124–1134
  4. 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 2021) 198, 62:1–62:18
  5. An Approximate Blow-up Lemma for Sparse Hypergraphs
    P. Allen, J. Böttcher, E.K. Hng, J. Skokan, E. Davies
    Procedia Computer Science 195, 394–403
  6. 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
  7. Statistical Physics Approaches to Unique Games
    M. Coulson, E. Davies, A. Kolla, V. Patel, G. Regts
    35th Computational Complexity Conference (CCC 2020) 169, 13:1–13:27
  8. 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
  9. 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
  10. 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
  11. Counting proper colourings in 4-regular graphs via the Potts model
    E. Davies
    Electronic Journal of Combinatorics 25 (2018), P4.7
  12. 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
  13. 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
  14. 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
  15. Multicolour Ramsey numbers of paths and even cycles
    E. Davies, M. Jenssen, B. Roberts
    European Journal of Combinatorics 63 (2017), 124–133
  16. Independent Sets, Matchings, and Occupancy Fractions
    E. Davies, M. Jenssen, W. Perkins, B. Roberts
    Journal of the London Mathematical Society 96 (2017), 47–66
  17. 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
  18. 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)
  2. Counting the number of ways a gas can fill a room
    E. Davies
    Maths at LSE Blog (2016)

Future

Current

Past

Upcoming events

Past events

  • 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
    CS Colloquium (BMAC), Colorado State | Fort Collins, Colorado
    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
    Discrete Math and Combinatorics Seminar, UofSC | Columbia, South Carolina (Online)
    Title: Independent sets of a given size
  • 8 Feb 2021
    Combinatorics and Probability Seminar, UIC | Chicago, Illinois (Online)
    Title: Independent sets of a given size
  • 14–16 Dec 2020
  • 21–25 Sep 2020
    Computational Phase Transitions | Berkeley, California (Online)
  • 8–11 Sep 2020
    Geometry of Polynomials Reunion | Berkeley, California (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, Illinois
    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, Colorado
    Title: Statistical physics approaches to Unique Games
  • 25 Sep 2019
    CS Theory Seminar, CU Boulder | Boulder, Colorado
    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