Upcoming events
-
27–28 Mar 2025Algorithmic, Combinatorial, and Probabilistic Aspects of Partition Functions and Graph Polynomials, | Amsterdam, Netherlands
Preprints
- Sampling List PackingsE. Camrud, E. Davies, A. Karduna, H. Lee
@article{CDKP23, title = {Sampling {L}ist {P}ackings}, author = {Camrud, Evan and Davies, Ewan and Karduna, Alex and Lee, Holden}, year = {2024}, eprint = {2402.03520}, eprinttype = {arxiv} }
This bib entry works best with biblatex/biber, or a modified version of the standard bibtex style "abbrv" that includes DOI and arXiv links available here.
We study the problem of approximately counting the number of list packings of a graph. The analogous problem for usual vertex coloring and list coloring has attracted a lot of attention. For list packing the setup is similar but we seek a full decomposition of the lists of colors into pairwise-disjoint proper list colorings. In particular, the existence of a list packing implies the existence of a list coloring. Recent works on list packing have focused on existence or extremal results on the number of list packings, but here we turn to the algorithmic aspects of counting. In graphs of maximum degree and when the number of colors is at least , we give an FPRAS based on rapid mixing of a natural Markov chain (the Glauber dynamics) which we analyze with the path coupling technique. Some motivation for our work is the investigation of an atypical spin system, one where the number of spins for each vertex is much larger than the graph degree.
- Graph structure via local occupancyE. Davies, R.J. Kang, F. Pirot, J.-S. Sereni
@article{DKPS20, title = {Graph structure via local occupancy}, author = {Davies, Ewan and Kang, Ross J. and Pirot, Fran\c{c}ois and Sereni, Jean-S\'ebastien}, year = {2020}, eprinttype = {arxiv}, eprint = {2003.14361} }
This bib entry works best with biblatex/biber, or a modified version of the standard bibtex style "abbrv" that includes DOI and arXiv links available here.
The first author together with Jenssen, Perkins and Roberts (2017) recently showed how local properties of the hard-core model on triangle-free graphs guarantee the existence of large independent sets, of size matching the best-known asymptotics due to Shearer (1983). The present work strengthens this in two ways: first, by guaranteeing stronger graph structure in terms of colourings through applications of the Lovász local lemma; and second, by extending beyond triangle-free graphs in terms of local sparsity, treating for example graphs of bounded local edge density, of bounded local Hall ratio, and of bounded clique number. This generalises and improves upon much other earlier work, including that of Shearer (1995), Alon (1996) and Alon, Krivelevich and Sudakov (1999), and more recent results of Molloy (2019), Bernshteyn (2019) and Achlioptas, Iliopoulos and Sinclair (2019). Our results derive from a common framework built around the hard-core model. It pivots on a property we call local occupancy, giving a clean separation between the methods for deriving graph structure with probabilistic information and verifying the requisite probabilistic information itself.
- Regularity inheritance in hypergraphsP. Allen, E. Davies, J. Skokan
@article{ADS19, title = {Regularity inheritance in hypergraphs}, author = {Allen, Peter and Davies, Ewan and Skokan, Jozef}, year = {2019}, eprinttype = {arxiv}, eprint = {1901.05955} }
This bib entry works best with biblatex/biber, or a modified version of the standard bibtex style "abbrv" that includes DOI and arXiv links available here.
We give a new approach to handling hypergraph regularity. This approach allows for vertex-by-vertex embedding into regular partitions of hypergraphs, and generalises to regular partitions of sparse hypergraphs. We also prove a corresponding sparse hypergraph regularity lemma.
Publications
- Algorithms for the Ferromagnetic Potts Model on ExpandersC. Carlson, E. Davies, N. Fraiman, A. Kolla, A. Potukuchi, C. YapCombinatorics, Probability and Computing (2024), to appear
@article{CDF+24, title = {{Algorithms for the Ferromagnetic Potts Model on Expanders}}, author = {Carlson, Charlie and Davies, Ewan and Fraiman, Nicolas and Kolla, Alexandra and Potukuchi, Aditya and Yap, Corrine}, year = {2024}, shortjournal = {Comb. Probab. Comput.}, journal = {Combinatorics, Probability and Computing}, pages = {to appear}, eprint = {2204.01923}, eprinttype = {arxiv}, doi = {10.1017/S0963548324000087} }
This bib entry works best with biblatex/biber, or a modified version of the standard bibtex style "abbrv" that includes DOI and arXiv links available here.
We give algorithms for approximating the partition function of the ferromagnetic Potts model on -regular expanding graphs. We require much weaker expansion than in previous works; for example, the expansion exhibited by the hypercube suffices. The main improvements come from a significantly sharper analysis of standard polymer models, using extremal graph theory and applications of Karger’s algorithm to counting cuts that may be of independent interest. It is #BIS-hard to approximate the partition function at low temperatures on bounded-degree graphs, so our algorithm can be seen as evidence that hard instances of #BIS are rare. We believe that these methods can shed more light on other important problems such as sub-exponential algorithms for approximate counting problems.
- Approximately Counting Independent Sets in Dense Bipartite Graphs via Subspace EnumerationC. Carlson, E. Davies, A. Kolla, A. Potukuchi51st EATCS International Colloquium on Automata, Languages, and Programming (ICALP) 297 (2024), 35:1–35:18
@inproceedings{CDKP24, title = {Approximately Counting Independent Sets in Dense Bipartite Graphs via Subspace Enumeration}, booktitle = {51st EATCS International Colloquium on Automata, Languages, and Programming (ICALP)}, pages = {35:1--35:18}, author = {Carlson, Charlie and Davies, Ewan and Kolla, Alexandra and Potukuchi, Aditya}, year = {2024}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, isbn = {978-3-95977-322-5}, issn = {1868-8969}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f\"ur Informatik}, address = {Dagstuhl, Germany}, doi = {10.4230/LIPIcs.ICALP.2024.35}, eprint = {2307.09533}, eprinttype = {arxiv} }
This bib entry works best with biblatex/biber, or a modified version of the standard bibtex style "abbrv" that includes DOI and arXiv links available here.
We give a randomized algorithm that approximates the number of independent sets in a dense, regular bipartite graph—in the language of approximate counting, we give an FPRAS for #BIS on the class of dense, regular bipartite graphs. Efficient counting algorithms typically apply to “high-temperature” problems on bounded-degree graphs, and our contribution is a notable exception as it applies to dense graphs in a low-temperature setting. Our methods give a counting-focused complement to the long line of work in combinatorial optimization showing that CSPs such as Max-Cut and Unique Games are easy on dense graphs via spectral arguments. The proof exploits the fact that dense, regular graphs exhibit a kind of small-set expansion (i.e. bounded threshold rank), which via subspace enumeration lets us enumerate small cuts efficiently.
- List Packing Number of Bounded Degree GraphsS. Cambie, W. Cames van Batenburg, E. Davies, R.J. KangCombinatorics, Probability and Computing (2024), to appear
@article{CCDK23, title = {List Packing Number of Bounded Degree Graphs}, author = {Cambie, Stijn and {Cames van Batenburg}, Wouter and Davies, Ewan and Kang, Ross J.}, year = {2024}, shortjournal = {Comb. Probab. Comput.}, journal = {Combinatorics, Probability and Computing}, pages = {to appear}, eprint = {2303.01246}, eprinttype = {arxiv} }
This bib entry works best with biblatex/biber, or a modified version of the standard bibtex style "abbrv" that includes DOI and arXiv links available here.
We investigate the list packing number of a graph, the least such that there are always disjoint proper list-colourings whenever we have lists all of size associated to the vertices. We are curious how the behaviour of the list packing number contrasts with that of the list chromatic number, particularly in the context of bounded degree graphs. The main question we pursue is whether every graph with maximum degree has list packing number at most . Our results highlight the subtleties of list packing and the barriers to, for example, pursuing a Brooks’-type theorem for the list packing number.
- Efficient algorithms for the Potts model on small-set expandersC. Carlson, E. Davies, A. KollaChicago Journal of Theoretical Computer Science 2024 (2024), 1–31
@article{CDK24, title = {Efficient algorithms for the Potts model on small-set expanders}, author = {Carlson, Charlie and Davies, Ewan and Kolla, Alexandra}, year = {2024}, shortjournal = {Chic. J. Theor. Comput. Sci.}, journal = {Chicago Journal of Theoretical Computer Science}, volume = {2024}, number = {1}, pages = {1--31}, eprinttype = {arxiv}, eprint = {2003.01154}, doi = {10.4086/cjtcs.2024.001} }
This bib entry works best with biblatex/biber, or a modified version of the standard bibtex style "abbrv" that includes DOI and arXiv links available here.
An emerging trend in approximate counting is to show that certain ‘low- temperature’ problems are easy on typical instances, despite worst-case hardness results. For the class of regular graphs one usually shows that expansion can be exploited algorithmically, and since random regular graphs are good expanders with high probability the problem is typically tractable. Inspired by approaches used in subexponential-time algorithms for Unique Games, we develop an approximation algorithm for the partition function of the ferromagnetic Potts model on graphs with a small-set expansion condition. In such graphs it may not suffice to explore the state space of the model close to ground states, and a novel feature of our method is to efficiently find a larger set of ‘pseudo-ground states’ such that it is enough to explore the model around each pseudo-ground state.
- An algorithmic framework for colouring locally sparse graphsE. Davies, R.J. Kang, F. Pirot, J.-S. SereniTheory of Computing (2024), to appear
@article{DKPS24, title = {An algorithmic framework for colouring locally sparse graphs}, author = {Davies, Ewan and Kang, Ross J. and Pirot, Fran\c{c}ois and Sereni, Jean-S\'ebastien}, year = {2024}, shortjournal = {Theory Comput.}, journal = {Theory of Computing}, pages = {to appear}, issn = {1557-2862}, eissn = {1557-2862}, eprinttype = {arxiv}, eprint = {2004.07151} }
This bib entry works best with biblatex/biber, or a modified version of the standard bibtex style "abbrv" that includes DOI and arXiv links available here.
We develop an algorithmic framework for graph colouring that reduces the problem to verifying a local probabilistic property of the independent sets. With this we give, for any fixed and , a randomised polynomial-time algorithm for colouring graphs of maximum degree in which each vertex is contained in at most copies of a cycle of length , where , with colours. This generalises and improves upon several notable results including those of Kim (1995) and Alon, Krivelevich and Sudakov (1999), and more recent ones of Molloy (2019) and Achlioptas, Iliopoulos and Sinclair (2019). This bound on the chromatic number is tight up to an asymptotic factor and it coincides with a famous algorithmic barrier to colouring random graphs.
- A Robust Corrádi–Hajnal TheoremP. Allen, J. Böttcher, J. Corsten, E. Davies, M. Jenssen, P. Morris, B. Roberts, J. SkokanRandom Structures & Algorithms 65 (2024), 61–130
@article{ABC+24, title = {{A Robust Corr\'adi--Hajnal Theorem}}, author = {Allen, Peter and B\"ottcher, Julia and Corsten, Jan and Davies, Ewan and Jenssen, Matthew and Morris, Patrick and Roberts, Barnaby and Skokan, Jozef}, year = {2024}, shortjournal = {Random Struct. Algorithms}, journal = {Random Structures \& Algorithms}, volume = {65}, number = {1}, pages = {61-130}, issn = {1042-9832}, eissn = {1098-2418}, eprint = {2209.01116}, eprinttype = {arxiv}, doi = {10.1002/rsa.21209} }
This bib entry works best with biblatex/biber, or a modified version of the standard bibtex style "abbrv" that includes DOI and arXiv links available here.
For a graph and , we denote by the random sparsification of obtained by keeping each edge of independently, with probability . We show that there exists a such that if and is an -vertex graph with and , then with high probability contains a triangle factor. Both the minimum degree condition and the probability condition, up to the choice of , are tight. Our result can be viewed as a common strengthening of the seminal theorems of Corrádi and Hajnal, which deals with the extremal minimum degree condition for containing triangle factors (corresponding to in our result), and Johansson, Kahn and Vu, which deals with the threshold for the appearance of a triangle factor in (corresponding to in our result). It also implies a lower bound on the number of triangle factors in graphs with minimum degree at least which gets close to the truth.
- Packing list-colouringsS. Cambie, W. Cames van Batenburg, E. Davies, R.J. KangRandom Structures & Algorithms 64 (2024), 62–93
@article{CCDK24, title = {Packing list-colourings}, author = {Cambie, Stijn and {Cames van Batenburg}, Wouter and Davies, Ewan and Kang, Ross J.}, year = {2024}, shortjournal = {Random Struct. Algorithms}, journal = {Random Structures \& Algorithms}, volume = {64}, number = {1}, pages = {62--93}, issn = {1042-9832}, eissn = {1098-2418}, eprint = {2110.05230}, eprinttype = {arxiv}, doi = {10.1002/rsa.21181} }
This bib entry works best with biblatex/biber, or a modified version of the standard bibtex style "abbrv" that includes DOI and arXiv links available here.
List colouring is an influential and classic topic in graph theory. We initiate the study of a natural strengthening of this problem, where instead of one list-colouring, we seek many in parallel. Our explorations have uncovered a potentially rich seam of interesting problems spanning chromatic graph theory. Given a -list-assignment of a graph , which is the assignment of a list of colours to each vertex , we study the existence of pairwise-disjoint proper colourings of using colours from these lists. We may refer to this as a list-packing. Using a mix of combinatorial and probabilistic methods, we set out some basic upper bounds on the smallest for which such a list-packing is always guaranteed, in terms of the number of vertices, the degeneracy, the maximum degree, or the (list) chromatic number of . (The reader might already find it interesting that such a minimal is well defined.) We also pursue a more focused study of the case when is a bipartite graph. Our results do not yet rule out the tantalising prospect that the minimal above is not too much larger than the list chromatic number. Our study has taken inspiration from study of the strong chromatic number, and we also explore generalisations of the problem above in the same spirit.
- Approximately Counting Independent Sets of a Given Size in Bounded-Degree GraphsE. Davies, W. PerkinsSIAM Journal on Computing 52 (2023), 618–640
@article{DP23, title = {Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs}, author = {Davies, Ewan and Perkins, Will}, year = {2023}, shortjournal = {SIAM J. Comput.}, journal = {SIAM Journal on Computing}, volume = {52}, number = {2}, pages = {618--640}, publisher = {{Society for Industrial and Applied Mathematics}}, issn = {0097-5397}, eissn = {1095-7111}, doi = {10.1137/21M1466220}, eprinttype = {arxiv}, eprint = {2102.04984} }
This bib entry works best with biblatex/biber, or a modified version of the standard bibtex style "abbrv" that includes DOI and arXiv links available here.
We determine the computational complexity of approximately counting and sampling independent sets of a given size in bounded-degree graphs. That is, we identify a critical density and provide (i) for randomized polynomial-time algorithms for approximately sampling and counting independent sets of given size at most in -vertex graphs of maximum degree , and (ii) a proof that unless NP = RP, no such algorithms exist for . The critical density is the occupancy fraction of the hard-core model on the complete graph at the uniqueness threshold on the infinite -regular tree, giving as . Our methods apply more generally to antiferromagnetic 2-spin systems and motivate new questions in extremal combinatorics.
- Algorithms for the Ferromagnetic Potts Model on ExpandersC. Carlson, E. Davies, N. Fraiman, A. Kolla, A. Potukuchi, C. YapIEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) (2022), 344–355
@inproceedings{CDF+22, title = {{Algorithms for the Ferromagnetic Potts Model on Expanders}}, booktitle = {{IEEE} 63rd {Annual} {Symposium} on {Foundations} of {Computer} {Science} ({FOCS})}, author = {Carlson, Charlie and Davies, Ewan and Fraiman, Nicolas and Kolla, Alexandra and Potukuchi, Aditya and Yap, Corrine}, year = {2022}, month = oct, pages = {344--355}, issn = {2575-8454}, doi = {10.1109/FOCS54457.2022.00040}, eprint = {2204.01923}, eprinttype = {arxiv} }
This bib entry works best with biblatex/biber, or a modified version of the standard bibtex style "abbrv" that includes DOI and arXiv links available here.
We give algorithms for approximating the partition function of the ferromagnetic Potts model on -regular expanding graphs. We require much weaker expansion than in previous works; for example, the expansion exhibited by the hypercube suffices. The main improvements come from a significantly sharper analysis of standard polymer models, using extremal graph theory and applications of Karger’s algorithm to counting cuts that may be of independent interest. It is #BIS-hard to approximate the partition function at low temperatures on bounded-degree graphs, so our algorithm can be seen as evidence that hard instances of #BIS are rare. We believe that these methods can shed more light on other important problems such as sub-exponential algorithms for approximate counting problems.
- Computational Thresholds for the Fixed-Magnetization Ising ModelC. Carlson, E. Davies, A. Kolla, W. PerkinsProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC) (2022), 1459–1472
@inproceedings{CDKP22, title = {Computational Thresholds for the Fixed-Magnetization {I}sing Model}, author = {Carlson, Charlie and Davies, Ewan and Kolla, Alexandra and Perkins, Will}, booktitle = {Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC)}, year = {2022}, pages = {1459--1472}, publisher = {{ACM}}, address = {{Rome Italy}}, doi = {10.1145/3519935.3520003}, isbn = {978-1-4503-9264-8}, langid = {english}, eprint = {2111.03033}, eprinttype = {arxiv} }
This bib entry works best with biblatex/biber, or a modified version of the standard bibtex style "abbrv" that includes DOI and arXiv links available here.
The ferromagnetic Ising model is a model of a magnetic material and a central topic in statistical physics. It also plays a starring role in the algorithmic study of approximate counting: approximating the partition function of the ferromagnetic Ising model with uniform external field is tractable at all temperatures and on all graphs, due to the randomized algorithm of Jerrum and Sinclair. Here we show that hidden inside the model are hard computational problems. For the class of bounded-degree graphs we find computational thresholds for the approximate counting and sampling problems for the ferromagnetic Ising model at fixed magnetization (that is, fixing the number of and spins). In particular, letting denote the critical inverse temperature of the zero-field Ising model on the infinite -regular tree, and denote the mean magnetization of the zero-field measure on the infinite -regular tree at inverse temperature , we prove, for the class of graphs of maximum degree : 1. For there is an FPRAS and efficient sampling scheme for the fixed-magnetization Ising model for all magnetizations . 2. For , there is an FPRAS and efficient sampling scheme for the fixed-magnetization Ising model for magnetizations such that . 3. For , there is no FPRAS for the fixed-magnetization Ising model for magnetizations such that unless NP=RP.
- The -Ramsey Problem for Triangle-Free GraphsE. Davies, F. IllingworthSIAM Journal on Discrete Mathematics (2022), 1124–1134
@article{DI22, title = {The $\chi$-Ramsey Problem for Triangle-Free Graphs}, author = {Davies, Ewan and Illingworth, Freddie}, shortjournal = {SIAM Discret. Math.}, journal = {SIAM Journal on Discrete Mathematics}, pages = {1124--1134}, year = {2022}, publisher = {{Society for Industrial and Applied Mathematics}}, issn = {0895-4801}, eissn = {1095-7146}, doi = {10.1137/21M1437573}, eprint = {2107.12288}, eprinttype = {arxiv} }
This bib entry works best with biblatex/biber, or a modified version of the standard bibtex style "abbrv" that includes DOI and arXiv links available here.
In 1967, Erdős asked for the greatest chromatic number, , amongst all -vertex, triangle-free graphs. An observation of Erdős and Hajnal together with Shearer’s classical upper bound for the off-diagonal Ramsey number shows that is at most . We improve this bound by a factor , as well as obtaining an analogous bound on the list chromatic number which is tight up to a constant factor. A bound in terms of the number of edges that is similarly tight follows, and these results confirm a conjecture of Cames van Batenburg, de Joannis de Verclos, Kang, and Pirot.
- Approximately Counting Independent Sets of a Given Size in Bounded-Degree GraphsE. Davies, W. Perkins48th EATCS International Colloquium on Automata, Languages, and Programming (ICALP) 198 (2021), 62:1–62:18
@inproceedings{DP21, title = {{Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs}}, booktitle = {48th EATCS International Colloquium on Automata, Languages, and Programming (ICALP)}, author = {Davies, Ewan and Perkins, Will}, year = {2021}, pages = {62:1--62:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, isbn = {978-3-95977-195-5}, issn = {1868-8969}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f\"ur Informatik}, address = {Dagstuhl, Germany}, doi = {10.4230/LIPIcs.ICALP.2021.62}, eprinttype = {arxiv}, eprint = {2102.04984} }
This bib entry works best with biblatex/biber, or a modified version of the standard bibtex style "abbrv" that includes DOI and arXiv links available here.
We determine the computational complexity of approximately counting and sampling independent sets of a given size in bounded-degree graphs. That is, we identify a critical density and provide (i) for randomized polynomial-time algorithms for approximately sampling and counting independent sets of given size at most in -vertex graphs of maximum degree ; and (ii) a proof that unless NP=RP, no such algorithms exist for . The critical density is the occupancy fraction of the hard core model on the clique at the uniqueness threshold on the infinite -regular tree, giving as .
- An Approximate Blow-up Lemma for Sparse HypergraphsP. Allen, J. Böttcher, E.K. Hng, J. Skokan, E. DaviesProcedia Computer Science 195 (2021), 394–403
@inproceedings{ABDHS21, title = {An Approximate Blow-up Lemma for Sparse Hypergraphs}, shortjournal = {Procedia Comput. Sci.}, journal = {Procedia Computer Science}, author = {Allen, Peter and B\"ottcher, Julia and Hng, Eng Keat and Skokan, Jozef and Davies, Ewan}, year = {2021}, series = {Proceedings of the XI Latin and American Algorithms, Graphs and Optimization Symposium.}, volume = {195}, pages = {394--403}, issn = {1877-0509}, doi = {10.1016/j.procs.2021.11.048} }
This bib entry works best with biblatex/biber, or a modified version of the standard bibtex style "abbrv" that includes DOI and arXiv links available here.
We obtain an approximate sparse hypergraph version of the blow-up lemma, showing that partite hypergraphs with sufficient regularity of small subgraph counts behave as if they were complete partite for the purpose of embedding bounded degree hypergraphs.
- A proof of the Upper Matching Conjecture for large graphsE. Davies, M. Jenssen, W. PerkinsJournal of Combinatorial Theory, Series B 151 (2021), 393–416
@article{DJP21, title = {A proof of the Upper Matching Conjecture for large graphs}, author = {Davies, Ewan and Jenssen, Matthew and Perkins, Will}, shortjournal = {J. Comb. Theory Ser. B}, journal = {Journal of Combinatorial Theory, Series B}, year = {2021}, volume = {151}, pages = {393--416}, issn = {0095-8956}, eissn = {1096-0902}, doi = {10.1016/j.jctb.2021.07.005}, eprinttype = {arxiv}, eprint = {2004.06695} }
This bib entry works best with biblatex/biber, or a modified version of the standard bibtex style "abbrv" that includes DOI and arXiv links available here.
We prove that the ‘Upper Matching Conjecture’ of Friedland, Krop, and Markström and the analogous conjecture of Kahn for independent sets in regular graphs hold for all large enough graphs as a function of the degree. That is, for every and every large enough divisible by , a union of copies of the complete -regular bipartite graph maximizes the number of independent sets and matchings of size for each over all -regular graphs on vertices. To prove this we utilize the cluster expansion for the canonical ensemble of a statistical physics spin model, and we give some further applications of this method to maximizing and minimizing the number of independent sets and matchings of a given size in regular graphs of a given minimum girth.
- Occupancy fraction, fractional colouring, and triangle fractionE. Davies, R. de Joannis de Verclos, R.J. Kang, F. PirotJournal of Graph Theory 97 (2021), 557–568
@article{DJKP21, title = {Occupancy fraction, fractional colouring, and triangle fraction}, author = {Davies, Ewan and de Joannis de Verclos, R\'{e}mi and Kang, Ross J. and Pirot, Fran\c{c}ois}, shortjournal = {J. Graph Theory}, journal = {Journal of Graph Theory}, year = {2021}, volume = {97}, number = {4}, pages = {557--568}, issn = {0364-9024}, eissn = {1097-0118}, doi = {10.1002/jgt.22671}, eprinttype = {arxiv}, eprint = {1812.11152} }
This bib entry works best with biblatex/biber, or a modified version of the standard bibtex style "abbrv" that includes DOI and arXiv links available here.
Given , there exists such that, if , then for any graph on vertices of maximum degree in which the neighbourhood of every vertex in spans at most edges, we have (i) an independent set drawn uniformly at random from has expected size at least ; and (ii) the fractional chromatic number of is at most . The asymptotic factors cannot in general be improved by more than a factor of . One may view these as stronger versions of results of Ajtai, Komlós and Szemerédi (1981) and Shearer (1983) on the independence number. The proofs of both use a tight analysis of the hard-core model.
- On Zero-Free Regions for the Anti-Ferromagnetic Potts Model on Bounded-Degree GraphsF. Bencs, E. Davies, V. Patel, G. RegtsAnnales De l’Institut Henri Poincaré D 8 (2021), 459–489
@article{BDPR21, title = {On Zero-Free Regions for the Anti-Ferromagnetic Potts Model on Bounded-Degree Graphs}, shortjournal = {Ann. Inst. Henri Poincare D}, journal = {Annales de l'Institut Henri Poincar\'e D}, author = {Bencs, Ferenc and Davies, Ewan and Patel, Viresh and Regts, Guus}, year = {2021}, volume = {8}, number = {3}, pages = {459--489}, issn = {2308-5827}, eissn = {2308-5835}, doi = {10.4171/AIHPD/108}, eprinttype = {arxiv}, eprint = {1812.07532} }
This bib entry works best with biblatex/biber, or a modified version of the standard bibtex style "abbrv" that includes DOI and arXiv links available here.
We give zero-free regions for the partition function of the anti-ferromagnetic Potts model on bounded degree graphs. In particular we show that for any and any , there exists an open set in the complex plane that contains the interval such that for any and any graph of maximum degree at most . For small values of we are able to give better results. As an application of our results we obtain improved bounds on for the existence of deterministic approximation algorithms for counting the number of proper -colourings of graphs of small maximum degree.
- Statistical Physics Approaches to Unique GamesM. Coulson, E. Davies, A. Kolla, V. Patel, G. Regts35th Computational Complexity Conference (CCC) 169 (2020), 13:1–13:27
@inproceedings{CDKPR20, author = {Coulson, Matthew and Davies, Ewan and Kolla, Alexandra and Patel, Viresh and Regts, Guus}, title = {{Statistical Physics Approaches to Unique Games}}, booktitle = {35th Computational Complexity Conference (CCC)}, pages = {13:1--13:27}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, isbn = {978-3-95977-156-6}, issn = {1868-8969}, year = {2020}, eprinttype = {arxiv}, eprint = {1911.01504}, volume = {169}, editor = {Saraf, Shubhangi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f\"ur Informatik}, address = {Dagstuhl, Germany}, doi = {10.4230/LIPIcs.CCC.2020.13}, annote = {Keywords: Unique Games Conjecture, approximation algorithm, Potts model, cluster expansion, polynomial interpolation} }
This bib entry works best with biblatex/biber, or a modified version of the standard bibtex style "abbrv" that includes DOI and arXiv links available here.
We show how two techniques from statistical physics can be adapted to solve a variant of the notorious Unique Games problem, potentially opening new avenues towards the Unique Games Conjecture. The variant, which we call Count Unique Games, is a promise problem in which the “yes” case guarantees a certain number of highly satisfiable assignments to the Unique Games instance. In the standard Unique Games problem, the “yes” case only guarantees at least one such assignment. We exhibit efficient algorithms for Count Unique Games based on approximating a suitable partition function for the Unique Games instance via (i) a zero-free region and polynomial interpolation, and (ii) the cluster expansion. We also show that a modest improvement to the parameters for which we give results would be strong negative evidence for the truth of the Unique Games Conjecture.
- Colouring triangle-free graphs with local list sizesE. Davies, R. de Joannis de Verclos, R.J. Kang, F. PirotRandom Structures & Algorithms 57 (2020), 730–744
@article{DJKP18a, title = {Colouring triangle-free graphs with local list sizes}, author = {Davies, Ewan and de Joannis de Verclos, Rémi and Kang, Ross J. and Pirot, François}, shortjournal = {Random Struct. Algorithms}, journal = {Random Structures \& Algorithms}, volume = {57}, number = {3}, pages = {730-744}, year = {2020}, doi = {10.1002/rsa.20945}, issn = {1042-9832}, eissn = {1098-2418}, eprinttype = {arxiv}, eprint = {1812.01534} }
This bib entry works best with biblatex/biber, or a modified version of the standard bibtex style "abbrv" that includes DOI and arXiv links available here.
We prove two distinct and natural refinements of a recent breakthrough result of Molloy (and a follow-up work of Bernshteyn) on the (list) chromatic number of triangle-free graphs. In both our results, we permit the amount of colour made available to vertices of lower degree to be accordingly lower. One result concerns list colouring and correspondence colouring, while the other concerns fractional colouring. Our proof of the second illustrates the use of the hard-core model to prove a Johansson-type result, which may be of independent interest.
- Counting proper colourings in 4-regular graphs via the Potts modelE. DaviesElectronic Journal of Combinatorics 25 (2018), P4.7
@article{Dav18, title = {Counting proper colourings in 4-regular graphs via the Potts model}, author = {Davies, Ewan}, shortjournal = {Electron. J. Comb.}, journal = {Electronic Journal of Combinatorics}, volume = {25}, number = {4}, pages = {P4.7}, year = {2018}, doi = {10.37236/7743}, issn = {1077-8926}, eissn = {1077-8926}, eprinttype = {arxiv}, eprint = {1801.07547} }
This bib entry works best with biblatex/biber, or a modified version of the standard bibtex style "abbrv" that includes DOI and arXiv links available here.
We give tight upper and lower bounds on the internal energy per particle in the antiferromagnetic -state Potts model on -regular graphs, for . This proves the first case of a conjecture of the author, Perkins, Jenssen, and Roberts on extensions of their methods, and implies tight bounds on the antiferromagnetic Potts partition function. The zero-temperature limit gives upper and lower bounds on the number of proper -colourings of -regular graphs, which almost proves the case of a conjecture of Galvin and Tetali. For any we prove that the number of proper -colourings of a -regular graph is maximised by a union of ’s.
- Tight bounds on the coefficients of partition functions via stabilityE. Davies, M. Jenssen, W. Perkins, B. RobertsJournal of Combinatorial Theory, Series A 160 (2018), 1–30
@article{DJPR18c, title = {Tight bounds on the coefficients of partition functions via stability}, author = {Davies, Ewan and Jenssen, Matthew and Perkins, Will and Roberts, Barnaby}, shortjournal = {J. Combin. Theory Ser. A}, journal = {Journal of Combinatorial Theory, Series A}, volume = {160}, pages = {1--30}, year = {2018}, doi = {10.1016/j.jcta.2018.06.005}, eprinttype = {arxiv}, eprint = {1704.07784} }
This bib entry works best with biblatex/biber, or a modified version of the standard bibtex style "abbrv" that includes DOI and arXiv links available here.
Partition functions arise in statistical physics and probability theory as the normalizing constant of Gibbs measures and in combinatorics and graph theory as graph polynomials. For instance the partition functions of the hard-core model and monomer-dimer model are the independence and matching polynomials respectively. We show how stability results follow naturally from the recently developed occupancy method for maximizing and minimizing physical observables over classes of regular graphs, and then show these stability results can be used to obtain tight extremal bounds on the individual coefficients of the corresponding partition functions. As applications, we prove new bounds on the number of independent sets and matchings of a given size in regular graphs. For large enough graphs and almost all sizes, the bounds are tight and confirm the Upper Matching Conjecture of Friedland, Krop, and Markström and a conjecture of Kahn on independent sets for a wide range of parameters. Additionally we prove tight bounds on the number of -colorings of cubic graphs with a given number of monochromatic edges, and tight bounds on the number of independent sets of a given size in cubic graphs of girth at least .
- Extremes of the internal energy of the Potts model on cubic graphsE. Davies, M. Jenssen, W. Perkins, B. RobertsRandom Structures & Algorithms 53 (2018), 59–75
@article{DJPR18b, title = {Extremes of the internal energy of the {P}otts model on cubic graphs}, author = {Davies, Ewan and Jenssen, Matthew and Perkins, Will and Roberts, Barnaby}, shortjournal = {Random Struct. Algorithms}, journal = {Random Structures \& Algorithms}, volume = {53}, number = {1}, pages = {59-75}, year = {2018}, doi = {10.1002/rsa.20767}, issn = {1042-9832}, eissn = {1098-2418}, eprinttype = {arxiv}, eprint = {1610.08496} }
This bib entry works best with biblatex/biber, or a modified version of the standard bibtex style "abbrv" that includes DOI and arXiv links available here.
We prove tight upper and lower bounds on the internal energy per particle (expected number of monochromatic edges per vertex) in the anti-ferromagnetic Potts model on cubic graphs at every temperature and for all . This immediately implies corresponding tight bounds on the anti-ferromagnetic Potts partition function. Taking the zero-temperature limit gives new results in extremal combinatorics: the number of -colorings of a -regular graph, for any , is maximized by a union of ’s. This proves the case of a conjecture of Galvin and Tetali.
- On the average size of independent sets in triangle-free graphsE. Davies, M. Jenssen, W. Perkins, B. RobertsProceedings of the American Mathematical Society 146 (2018), 111–124
@article{DJPR18a, title = {On the average size of independent sets in triangle-free graphs}, author = {Davies, Ewan and Jenssen, Matthew and Perkins, Will and Roberts, Barnaby}, shortjournal = {Proc. Amer. Math. Soc.}, journal = {Proceedings of the American Mathematical Society}, volume = {146}, pages = {111--124}, year = {2018}, doi = {10.1090/proc/13728}, eprinttype = {arxiv}, eprint = {1606.01043} }
This bib entry works best with biblatex/biber, or a modified version of the standard bibtex style "abbrv" that includes DOI and arXiv links available here.
We prove an asymptotically tight lower bound on the average size of independent sets in a triangle-free graph on vertices with maximum degree , showing that an independent set drawn uniformly at random from such a graph has expected size at least . This gives an alternative proof of Shearer’s upper bound on the Ramsey number . We then prove that the total number of independent sets in a triangle-free graph with maximum degree is at least . The constant in the exponent is best possible. In both cases, tightness is exhibited by a random -regular graph. Both results come from considering the hard-core model from statistical physics: a random independent set drawn from a graph with probability proportional to , for a fugacity parameter . We prove a general lower bound on the occupancy fraction (normalized expected size of the random independent set) of the hard-core model on triangle-free graphs of maximum degree . The bound is asymptotically tight in for all . We conclude by stating several conjectures on the relationship between the average and maximum size of an independent set in a triangle-free graph and give some consequences of these conjectures in Ramsey theory.
- Multicolour Ramsey numbers of paths and even cyclesE. Davies, M. Jenssen, B. RobertsEuropean Journal of Combinatorics 63 (2017), 124–133
@article{DJR17, title = {Multicolour Ramsey numbers of paths and even cycles}, author = {Davies, Ewan and Jenssen, Matthew and Roberts, Barnaby}, shortjournal = {European J. Combin.}, journal = {European Journal of Combinatorics}, volume = {63}, pages = {124--133}, year = {2017}, doi = {10.1016/j.ejc.2017.03.002}, publisher = {Elsevier}, eprinttype = {arxiv}, eprint = {1606.00762} }
This bib entry works best with biblatex/biber, or a modified version of the standard bibtex style "abbrv" that includes DOI and arXiv links available here.
We prove new upper bounds on the multicolour Ramsey numbers of paths and even cycles. It is well known that . The upper bound was recently improved by Sárközy who showed that . Here we show , obtaining the first improvement to the coefficient of the linear term by an absolute constant.
- Independent Sets, Matchings, and Occupancy FractionsE. Davies, M. Jenssen, W. Perkins, B. RobertsJournal of the London Mathematical Society 96 (2017), 47–66
@article{DJPR17, title = {{Independent Sets, Matchings, and Occupancy Fractions}}, author = {Davies, Ewan and Jenssen, Matthew and Perkins, Will and Roberts, Barnaby}, shortjournal = {J. Lond. Math. Soc.}, journal = {Journal of the London Mathematical Society}, volume = {96}, pages = {47--66}, year = {2017}, doi = {10.1112/jlms.12056}, issn = {0024-6107}, eissn = {1469-7750}, eprinttype = {arxiv}, eprint = {1508.04675} }
This bib entry works best with biblatex/biber, or a modified version of the standard bibtex style "abbrv" that includes DOI and arXiv links available here.
We prove tight upper bounds on the logarithmic derivative of the independence and matching polynomials of -regular graphs. For independent sets, this theorem is a strengthening of the results of Kahn, Galvin and Tetali, and Zhao showing that a union of copies of maximizes the number of independent sets and the independence polynomial of a -regular graph. For matchings, this shows that the matching polynomial and the total number of matchings of a -regular graph are maximized by a union of copies of . Using this we prove the asymptotic upper matching conjecture of Friedland, Krop, Lundow, and Markström. In probabilistic language, our main theorems state that for all -regular graphs and all , the occupancy fraction of the hard-core model and the edge occupancy fraction of the monomer-dimer model with fugacity are maximized by . Our method involves constrained optimization problems over distributions of random variables and applies to all -regular graphs directly, without a reduction to the bipartite case.
- Tight bounds on the coefficients of partition functions via stability (extended abstract)E. Davies, M. Jenssen, W. Perkins, B. RobertsElectronic Notes in Discrete Mathematics 61 (2017), 317–321
@article{DJPR17abs, title = {Tight bounds on the coefficients of partition functions via stability (extended abstract)}, author = {Davies, Ewan and Jenssen, Matthew and Perkins, Will and Roberts, Barnaby}, shortjournal = {Electron. Notes Discrete Math.}, journal = {Electronic Notes in Discrete Mathematics}, volume = {61}, pages = {317--321}, year = {2017}, doi = {10.1016/j.endm.2017.06.054}, publisher = {Elsevier} }
This bib entry works best with biblatex/biber, or a modified version of the standard bibtex style "abbrv" that includes DOI and arXiv links available here.
We show how to use the recently-developed occupancy method and stability results that follow easily from the method to obtain extremal bounds on the individual coefficients of the partition functions over various classes of bounded degree graphs. As applications, we prove new bounds on the number of independent sets and matchings of a given size in regular graphs. For large enough graphs and almost all sizes, the bounds are tight and confirm the Upper Matching Conjecture of Friedland, Krop, and Markström, and a conjecture of Kahn on independent sets for a wide range of parameters. Additionally we prove tight bounds on the number of -colorings of cubic graphs with a given number of monochromatic edges, and tight bounds on the number of independent sets of a given size in cubic graphs of girth at least .
- Counting in hypergraphs via regularity inheritance (extended abstract)E. DaviesElectronic Notes in Discrete Mathematics 49 (2015), 413–417
@article{Dav15abs, title = {Counting in hypergraphs via regularity inheritance (extended abstract)}, author = {Davies, Ewan}, shortjournal = {Electron. Notes Discrete Math.}, journal = {Electronic Notes in Discrete Mathematics}, volume = {49}, pages = {413--417}, year = {2015}, doi = {10.1016/j.endm.2015.06.058}, publisher = {Elsevier} }
This bib entry works best with biblatex/biber, or a modified version of the standard bibtex style "abbrv" that includes DOI and arXiv links available here.
We develop a theory of regularity inheritance in -uniform hypergraphs. As a simple consequence we deduce a strengthening of a counting lemma of Frankl and Rödl. We believe that the approach is sufficiently flexible and general to permit extensions of our results in the direction of a hypergraph blow-up lemma.
Other work
- Extremal and probabilistic results for regular graphsE. DaviesPhD thesis, The London School of Economics and Political Science (2017)
@phdthesis{Dav17thesis, title = {Extremal and probabilistic results for regular graphs}, author = {Davies, Ewan}, institution = {The London School of Economics and Political Science}, year = {2017}, doi = {10.21953/lse.bijk2dsj3hlb} }
This bib entry works best with biblatex/biber, or a modified version of the standard bibtex style "abbrv" that includes DOI and arXiv links available here.
In this thesis we explore extremal graph theory, focusing on new methods which apply to different notions of regular graph. The first notion is -regularity, which means each vertex of a graph is contained in exactly edges, and the second notion is Szemerédi regularity, which is a strong, approximate version of this property that relates to pseudorandomness. We begin with a novel method for optimising observables of Gibbs distributions in sparse graphs. The simplest application of the method is to the hard-core model, concerning independent sets in -regular graphs, where we prove a tight upper bound on an observable known as the occupancy fraction. We also cover applications to matchings and colourings, in each case proving a tight bound on an observable of a Gibbs distribution and deriving an extremal result on the number of a relevant combinatorial structure in regular graphs. The results relate to a wide range of topics including statistical physics and Ramsey theory. We then turn to a form of Szemerédi regularity in sparse hypergraphs, and develop a method for embedding complexes that generalises a widely-applied method for counting in pseudorandom graphs. We prove an inheritance lemma which shows that the neighbourhood of a sparse, regular subgraph of a highly pseudorandom hypergraph typically inherits regularity in a natural way. This shows that we may embed complexes into suitable regular hypergraphs vertex-by-vertex, in much the same way as one can prove a counting lemma for regular graphs. Finally, we consider the multicolour Ramsey number of paths and even cycles. A well-known density argument shows that when the edges of a complete graph on vertices are coloured with colours, one can find a monochromatic path on vertices. We give an improvement to this bound by exploiting the structure of the densest colour, and use the regularity method to extend the result to even cycles.
Current
- CS 220: Discrete Structures and their Applications, Colorado State University, Fall 2024
- I am able to supervise Master's Theses and PhD Dissertations, feel free to inquire about finding a suitable project/topic
Past
- CS 520: Analysis of Algorithms, Colorado State University, Spring 2024
- CS 220: Discrete Structures and their Applications, Colorado State University, Fall 2023
- Undergraduate research on redistricting, Summer 2023
- Undergraduate research on packing list colorings, Summer 2023
- CS 520: Analysis of Algorithms, Colorado State University, Spring 2023
- CSCI 3104: Algorithms, CU Boulder, Fall 2020
- Representation Theory, University of Amsterdam, 2018
- Algebraic Methods in Combinatorics, University of Amsterdam, 2018
- Mathematics Support Centre, London School of Economics, 2015, 2016
- MA203 Real Analysis, London School of Economics, 2015
- MA316 Graph Theory, London School of Economics, 2014
- MA212 Further Mathematical Methods, London School of Economics, 2014
- MA100 Mathematical Methods, London School of Economics, 2013
Upcoming events
-
27–28 Mar 2025Algorithmic, Combinatorial, and Probabilistic Aspects of Partition Functions and Graph Polynomials, | Amsterdam, Netherlands
Past events
-
11–16 Aug 2024
-
13–16 May 2024Summer School on Probability, Algorithms, and Inference | Atlanta, GA
-
7–11 Mar 2024UCSC Theory Group Retreat | Mammoth, CA
-
23 Feb 2024Rocky Mountain Algebraic Combinatorics Seminar | Fort Collins, COTitle: Graph homomorphisms, partition functions and extremal problems (colloquium and seminar talks)
-
6 Oct 2023Georgia Tech Combinatorics Seminar | Atlanta, GATitle: Packing colorings
-
25 Sep 2023Discrete Seminar, University of Colorado Denver | Denver, COTitle: Why not make coloring even more difficult?
-
21 Sep 2023Applied Mathematics and Statistics (AMS) Seminar, Johns Hopkins University | Baltimore, MDTitle: Counting independent sets in dense bipartite graphs
-
7–12 Aug 2023Random Theory 2023 | Estes Park, CO
-
13–14 May 20238th Lake Michigan Workshop on Combinatorics and Graph Theory | Notre Dame, IN
-
27 Nov – 2 Dec 2022Dagstuhl Workshop on Counting and Sampling | Wadern, Germany
-
31 Oct – 3 Nov 2022FOCS 2022 | Denver, CO
-
8–12 Aug 2022New tools for optimal mixing of Markov chains | Santa Barbara, CA
-
18–19 May 2022DIMACS Workshop on Entropy and Optimization | New Brunswick, NJ (Online)
-
14–15 May 2022AMS 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 2022CS Colloquium (BMAC), Colorado State | Fort Collins, COTitle: The Complexity of Approximate Counting Problems
-
27 Sep 2021Combinatorics and Probability Seminar, UIC | Chicago, ILTitle: Graph coloring, independent transversals and packing
-
12–16 Jul 2021ICALP 2021 | Glasgow, Scotland (Online)
-
17–21 May 2021Extremal and algorithmic aspects of partition functions, Sparse Graphs Coalition | Online
-
8–12 Mar 2021Entropy Compression and Related Methods, Sparse Graphs Coalition | OnlineTalk: The cluster expansion, Lovász local lemma and algorithms (10 Mar)
-
19 Feb 2021Discrete Math and Combinatorics Seminar, UofSC | Columbia, SC (Online)Title: Independent sets of a given size
-
8 Feb 2021Combinatorics and Probability Seminar, UIC | Chicago, IL (Online)Title: Independent sets of a given size
-
14–16 Dec 2020
-
21–25 Sep 2020Computational Phase Transitions | Berkeley, CA (Online)
-
8–11 Sep 2020Geometry of Polynomials Reunion | Berkeley, CA (Online)
-
19–28 Aug 2020Probability, Geometry, and Computation in High Dimensions Boot Camp | Berkeley, CA (Online)
-
28–31 Jul 2020Computational Complexity Conference (CCC) 2020 | Saarbrücken, Germany (Online)Talk: Statistical physics approaches to Unique Games (29 Jul)
-
4–5 Apr 2020POSTPONED Lake Michigan Workshop on Combinatorics and Graph Theory | Chicago, IL
-
19 Mar 2020POSTPONED Computer Science Theory Seminar, UIC | Chicago, ILTitle: Statistical physics approaches to Unique Games (with Alex Kolla)
-
12 Feb 2020Discrete Mathematics Seminar, KdVI / CWI | Amsterdam, NetherlandsTitle: Statistical physics approaches to Unique Games
-
22 Jan 2020CS Theory Seminar, CU Boulder | Boulder, COTitle: Statistical physics approaches to Unique Games
-
25 Sep 2019CS Theory Seminar, CU Boulder | Boulder, COTitle: Graph colouring and the hard-core model
-
15 Jan – 17 May 2019Simons Institute: Geometry of Polynomials | Berkeley, CATalk: Colouring locally sparse graphs via the hard-core model (17 Apr)
-
23–24 Aug 2018Algorithmic and Combinatorial Aspects of Partition Functions | Amsterdam, NetherlandsTalk: Fractional colouring of triangle-free graphs via the hard-core model (24 Aug)
-
9–10 May 2018Two one-day Colloquia in Combinatorics | London, UK
-
1 May 2018Applied Stochastics Seminar, Radboud University | Nijmegen, NetherlandsTitle: Using Gibbs measures in extremal combinatorics
-
26–30 Mar 2018Workshop on Graph limits | Janov, CzechiaTalk: Tight bounds on the coefficients of partition functions via stability (30 Mar)
-
19 Feb – 4 Mar 2018Graphs and Randomness, IMPA | Rio de Janeiro, Brazil
-
26 Jan 2018Discrete Mathematics Seminar, KdVI / CWI | Amsterdam, NetherlandsTitle: A new approach to Sidorenko's conjecture
-
18 Oct 2017Discrete Mathematics Seminar, KdVI / CWI | Amsterdam, NetherlandsTitle: Shamir's problem revisited
-
28 Aug – 1 Sep 2017EUROCOMB 2017 | Vienna, AustriaTalk: Tight bounds on the coefficients of partition functions via stability (31 Aug, slides)
-
17–21 Jul 2017Novi Sad Workshop on Foundations Of Computer Science | Novi Sad, SerbiaTalk: Regularity inheritance in 3-uniform hypergraphs (20 Jul)
-
11 May 2017Two one-day Colloquia in Combinatorics (invited) | London, UKTitle: Tight bounds on the coefficients of partition functions via stability
-
21 Feb 2017Combinatorics Seminar | Oxford, UKTitle: Extremal problems on colourings in cubic graphs via the Potts model
-
3 Feb 2017Discrete Mathematics Seminar, KdVI / CWI | Amsterdam, NetherlandsTitle: A probabilistic approach to bounding graph polynomials
-
27 Jan 2017PhD Seminar on Combinatorics, Games and Optimisation, LSE | London, UKTitle: A probabilistic approach to bounding graph polynomials
-
3 Aug 2016Student Combinatorics Day (invited) | Birmingham, UKTitle: On the average size of independent sets in triangle-free graphs (slides)
-
8 Apr 2016Seminário de Teoria da Computação, Combinatória e Otimização | São Paulo, BrazilTitle: Independent sets, matchings, and occupancy fractions II
-
3 Nov 2015Discrete Geometry and Combinatorics Seminar, UCL | London, UKTitle: Independent sets, matchings, and occupancy fractions
-
9 Oct 2015Mathematics Lunchtime Seminar, LSE | London, UKTitle: Independent sets, matchings, and occupancy fractions I
-
31 Aug – 4 Sep 2015EUROCOMB 2015 | Bergen, NorwayTalk: Counting in hypergraphs via regularity inheritance (31 Aug, slides)
-
15 Apr 2015Postgraduate Combinatorial Conference, QMUL | London, UKTitle: Counting in hypergraphs via regularity inheritance
-
9 Apr 2015Combinatorics Seminar, Freie Universität | Berlin, GermanyTitle: Regularity inheritance in 3-uniform hypergraphs
-
3 Jul 2014SUMMIT 190: Balogh, Csaba, Hajnal, and Pluhar are 190 (invited) | Szeged, HungaryTitle: Robustness of triangle factors
-
29 Nov 2013Mathematics Lunchtime Seminar, LSE | London, UKTitle: Cycle packing
View my full CV as a pdf here
Positions held
- Assistant Professor at Colorado State, CS Department (2022-Present)
- Postdoc at CU Boulder, CS Department (2019-2022)
- Research Fellow at the Simons Institute, Geometry of Polynomials Program (2019)
- Postdoc at the University of Amsterdam, Mathematics Department (2017-2018)
Education
- Ph.D. Mathematics, London School of Economics and Political Science (2013-2017)
- M.Math, University of Cambridge (2012-2013)
- B.A. (Hons) Mathematics, University of Cambridge (2009-2012)
Awards
- Sampling and Optimization under Global Constraints, NSF Grant #2309707
- PhD Prize for Outstanding Academic Performance, London School of Economics
- Mathematics Department New Teacher Prize, London School of Economics
- Foundation Scholarship and R.A. Watchman Prize, Jesus College, Cambridge
- Foundation Scholarship and Sir Harold Spencer Jones Prize, Jesus College, Cambridge
- Foundation Scholarship and Ware Prize, Jesus College, Cambridge
- Foundation Exhibition and Bronowski Prize, Jesus College, Cambridge
Some demonstrations of my work can be found here
arXiv recent feeds
A list of my papers on arXiv is here