David Ellis
Welcome! I am a mathematician working mainly in combinatorics and related areas. I am particularly interested in exploring links between extremal combinatorics and other areas of pure and applied mathematics (principally algebra, analysis, probability theory, geometry, and of course theoretical computer science). I am a Reader (a.k.a. Associate Professor) in Pure Mathematics at the University of Bristol (in the School of Mathematics).
Previously, I have been a Lecturer in Pure Mathematics at Queen Mary, University of London, and before that, I was a Junior Research Fellow at St John's College, Cambridge. My Ph.D was supervised by Imre Leader at the Department of Pure Mathematics and Mathematical Statistics at the University of Cambridge; I received my Ph.D in 2010. During the academic year 2013-14, I was a Feinberg Visiting Fellow at the Weizmann Institute of Science, hosted by Ehud Friedgut, and also working with Itai Benjamini.
Here are most of my publications and preprints.
D. Ellis, M.-R. Ivan and I. Leader, Turán densities for daisies and hypercubes. Preprint. arXiv.
D. Ellis, G. Kindler, N. Lifshitz and D. Minzer, Product mixing in compact Lie groups. Preprint. arXiv.
H. T. Chau, D. Ellis, E. Friedgut and N. Lifshitz, On the maximum degree of induced subgraphs of the Kneser graph. Preprint. arXiv.
D. Ellis, G. Kindler and N. Lifshitz, An analogue of Bonami's lemma for functions on spaces of linear maps, and 2-2 games. Proceedings of the 55th Annual ACM Symposium on the Theory of Computing (STOC), 656-660 (2023). arXiv.
D. Ellis, G. Kindler and N. Lifshitz, Forbidden intersection problems for families of linear maps. Discrete Analysis 2023:19, 23pp. arXiv.
D. Ellis and D. King, Lower bounds for the Turán densities of daisies. Electronic Journal of Combinatorics 30 (2023), P4.4. arXiv.
D. Ellis, M.-R. Ivan and I. Leader, Small sets in union-closed families. Electronic Journal of Combinatorics 30 (2023), P1.8. arXiv.
J. Aaronson, D. Ellis and I. Leader, A note on transitive union-closed families. Electronic Journal of Combinatorics 28 (2021), P2.3. arXiv.
D. Ellis and N. Lifshitz, Approximation by juntas in the symmetric group, and forbidden intersection problems. Duke Mathematical Journal 171 (2022), 1417-1467. arXiv.
D. Ellis, Union-closed families with small average overlap densities. Electronic Journal of Combinatorics 29 (2022), P1.11. arXiv.
I. Benjamini and D. Ellis, On the structure of random graphs with constant r-balls. Journal of the European Mathematical Society 25 (2023), 515-570. arXiv.
D. Ellis, N. Keller and N. Lifshitz, Stability for the Complete Intersection Theorem, and the forbidden intersection problem of Erdős and Sós. To appear in Journal of the European Mathematical Society. arXiv.
B. Narayanan, D. Ellis and G. Kalai, On symmetric intersecting families. European Journal of Combinatorics 86 (2020), 103094. arXiv.
P. Cameron, D. Ellis and W. Raynaud, Smallest cyclically covering subspaces of Fqn, and lower bounds in Isbell's conjecture. European Journal of Combinatorics 81 (2019), 242-255. arXiv.
D. Ellis, N. Keller and N. Lifshitz, Stability versions of Erdős-Ko-Rado type theorems, via isoperimetry. Journal of the European Mathematical Society 21 (2019), 3857-3902. arXiv.
D. Ellis and N. Lifshitz, On the union of intersecting families. Combinatorics, Probability and Computing 28 (2019), 826-839. arXiv
D. Ellis, N. Keller and N. Lifshitz, On a biased edge isoperimetric inequality for the discrete cube. Journal of Combinatorial Theory, Series A 163 (2019), 118-162. arXiv.
D. Ellis and I. Leader, An isoperimetric inequality for antipodal subsets of the discrete cube. European Journal of Combinatorics 70 (2018), 149-154. arXiv.
D. Ellis, N. Keller and N. Lifshitz, On the structure of subsets of the discrete cube with small edge boundary. Discrete Analysis 2018:9. arXiv.
D. Ellis, Y. Filmus and E. Friedgut, Low-degree Boolean functions on Sn, with an application to isoperimetry. Forum of Mathematics, Sigma 5 (2017), e23. arXiv.
D. Ellis and B. Narayanan, On symmetric 3-wise intersecting families. Proceedings of the American Mathematical Society 145 (2017), 2843-2847. arXiv.
I. Benjamini and D. Ellis, On the structure of graphs which are locally indistinguishable from a lattice. Forum of Mathematics, Sigma 4 (2016), e31. arXiv.
I. Benjamini, D. Ellis, E. Friedgut, N. Keller and A. Sen, Juntas in the L1-grid, and Lipschitz maps between discrete tori. Random Structures and Algorithms 49 (2016), 253-279. arXiv.
N. Atzmon, D. Ellis and D. Kogan, An isoperimetric inequality for conjugation-invariant sets in the symmetric group. Israel Journal of Mathematics 212 (2016), 139-162. arXiv.
D. Ellis, E. Friedgut, G. Kindler and A. Yehudayoff, Geometric stability via information theory. Discrete Analysis 2016:10. arXiv.
D. Ellis, Y. Filmus and E. Friedgut, A stability result for balanced dicatorships in Sn. Random Structures and Algorithms 46 (2015), 494--530. arXiv.
D. Ellis, Y. Filmus and E. Friedgut, A quasi-stability result for dictatorships in Sn. Combinatorica 25 (2015), 573-618. arXiv.
D. Ellis, Forbidding just one intersection, for permutations. Journal of Combinatorial Theory, Series A 126 (2014), 136-165. arXiv.
D. Ellis and N. Linial, On regular hypergraphs of high girth. Electronic Journal of Combinatorics 21 (2014), P1.54. arXiv.
D. Christofides, D. Ellis and P. Keevash, An approximate vertex-isoperimetric inequality for r-sets. Electronic Journal of Combinatorics 20 (2013), P15. arXiv.
D. Ellis, Y. Filmus and E. Friedgut, Triangle-intersecting families of graphs. Journal of the European Mathematical Society 14 (2012), 841-885. arXiv.
D. Ellis, Setwise intersecting families of permutations. Journal of Combinatorial Theory, Series A 119 (2012), 825-849. arXiv.
D. Ellis, A proof of the Cameron-Ku conjecture. Journal of the London Mathematical Society 85 (2012), 165-190. arXiv.
D. Ellis and B. Sudakov, Generating all subsets of a finite set with disjoint unions. Journal of Combinatorial Theory, Series A 118 (2011), 2319-2345. arXiv.
D. Ellis, E. Friedgut and H. Pilpel, Intersecting families of permutations. Journal of the American Mathematical Society 24 (2011), 649-682. arXiv.
D. Ellis, Almost isoperimetric subsets of the discrete cube. Combinatorics, Probability and Computing 20 (2011), 363-380. arXiv.
D. Ellis, Stability for t-intersecting families of permutations. Journal of Combinatorial Theory, Series A 118 (2011), 208-227. arXiv.
D. Ellis, Irredundant families of subcubes. Mathematical Proceedings of the Cambridge Philosophical Society 150 (2011), 363-380. arXiv.
Here is a survey paper I wrote in June 2021, on intersection problems in extremal combinatorics. It's an expanded version of a paper that appeared in the Proceedings of the 29th British Combinatorial Conference (University of Lancaster, 11th-15th July 2022). It's a personal perspective on the area, and is not intended to be exhaustive; it is, however, intended to be useful to graduate students, as well as to more established researchers.
Here are some lecture notes for some courses I have taught in the past, in case they are useful.
Algebraic Methods in Combinatorics. (A 16-lecture Graduate Course / non-examinable Part III course which I lectured at DPMMS, University of Cambridge, in the Lent Term of 2011.) Lecture 1; Lectures 2-5; Lecture 6; Lecture 7; Lectures 8-10; Lecture 11; Lecture 12; Lecture 13; Lecture 14.
Extremal Combinatorics. (A first course in extremal combinatorics, lectured at Queen Mary, University of London in 2014-2015, 2015-16 and 2018-19. In general, the content could be aimed at third-year undergraduates or first-year Masters students.)
Random Processes. (A first course in Markov chains, lectured at Queen Mary, University of London in 2014-15, 2015-16, 2017-18 and 2018-19. In general, the content could be aimed at second-year or third-year undergraduates in applied mathematics.)
Graph Theory. (A combined first-and-second course in Graph Theory; this would probably cover about fifty 50-minute lectures at an average Russell Group UK university, depending on the pace of the lecturer.)
Here is a link to the Bristol Combinatorics Seminar webpage. (I am one of the organisers.)
Here is a collection of open problems that Robert Johnson and I collated and edited to celebrate the occasion of Imre Leader's 60th birthday, in October 2023. It is intended to be useful for graduate students, as well as to more established researchers.
From May 2020 (until its activities ceased), I was a member of the Action Team of DELVE (Data Evaluation & Learning for Viral Epidemics); this was a multidisciplinary group convened by the Royal Society in April 2020, to support a data-driven approach to learning from the different approaches countries are taking to managing the coronavirus pandemic. DELVE's remit subsequently broadened and its members worked on a variety of projects to inform the policy response to COVID-19. I contributed substantially to the statistical/mathematical research underpinning the following DELVE reports. The second report was cited by the UK's Chief Medical Officers explaining their decision to recommend to the UK government that schools be reopened in September 2020.
DELVE Initiative (2020), Scoping Report on Hospital and Health Care Acquisition of COVID-19 and its Control. DELVE Report No. 3. Published 6th July 2020. Available here. My work was mainly on Technical Appendix 1: Estimates concerning COVID-19 infections of patient-facing healthcare workers and resident-facing social care workers in England between 26th April and 7th June, and related estimates. This is available here.
DELVE Initiative (2020), Balancing the Risks of Pupils Returning to Schools. DELVE Report No. 4. Published 24th July 2020. Available here.
I was Principal Investigator of the EPSRC-funded project EP/W000032/1. As part of this project, I have written (jointly with Matthew Aldridge) an introduction to the basics of pooled testing algorithms, with particular emphasis on applications in testing for Covid-19 infection. It is aimed at people who are not specialists in mathematics or statistics. It is available here.
Here is a briefing note with estimates of how the vaccine rollout (and vaccine uptake among young people) may affect the basic reproduction number of the coronavirus among UK university students during the Autumn Term of the Academic Year 2021/2022. The estimates are tailored to the situation for the University of Bristol, but with minor alterations they are transferrable to other UK universities.