Imre Leader
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Imre Leader has a total of 44 co-authors. Here are the top co-authors by number of shared publications:
- Ta Sheng Tan
Institute of Mathematical Sciences Faculty of Science Universiti Malaya 50603 Kuala Lumpur Malaysia
10 shared publications - Neil Hindman
Department of Mathematics, Howard University, Washington, USA
9 shared publications - Béla Bollobás
University of Cambridge, Cambridge, UK
8 shared publications - Paul A. Russell
Department of Pure Mathematics and Mathematical Statistics, Centre for Mathematical Sciences, Wilberforce Road, Cambridge CB3 0WB, UK
7 shared publications - Mark Walters
Queen Mary University of London
6 shared publications - Dona Strauss
University of Leeds
5 shared publications
Latest Publications
- Open Access
- 17 February 2025
- Published by Springer Nature in Israel Journal of Mathematics
- Vol. 268 (1) , 253-314
Large sumsets from small subsets
In this paper we start to investigate a new body of questions in additive combinatorics. The fundamental Cauchy–Davenport theorem gives a lower bound on the size of a sumset A + B for subsets of the cyclic group ℤ p of order p (p prime), and this is just one example of a large family of results. Our aim in this paper is to investigate what happens if we restrict the number of elements of one set that we may use to form the sums. Here is the question we set out to answer: given two subsets, A and B, does B have a subset B′ of bounded size such that A + B′ is large, perhaps even comparable to the size of A + B? In particular, can we get close to the lower bound of the Cauchy–Davenport theorem? Our main results show that, rather surprisingly, in many circumstances it is possible to obtain not merely an asymptotic version of the usual sumset bound, but even the exact bound itself. For example, in ℤ, we show that if A and B have size n then there are three elements b 1, b 2, b 3 ∈ B such that ∣(A + b 1) ∪ (A + b 2) ∪ (A + b 3)∣ ⩾ 2n − 1. And for ℤ p itself, we show the following: if A and B have size n, where n ⩽ p/3, then there is a subset B′ of B of size c such that ∣A + B′∣ ⩾ 2n − 1. Here c is an absolute constant. In the inverse direction for this result, we show that if for every subset B′ of B of size c we have ∣A + B′∣ ⩽ 2n − 1 + r, where r ⩽ εn for some absolute constant ε, then B is contained in an arithmetic progression of size n + r. We also prove ‘unbalanced’ forms of our results, when the sizes of A and B may differ. As an application, we prove some considerable extensions of the Erdős–Heilbronn problem. We also present versions in the continuous setting, and give several open problems.
- 17 February 2025
- Published by Springer Nature in Israel Journal of Mathematics
- Vol. 268 (1) , 253-314
Open AccessLarge sumsets from small subsets
In this paper we start to investigate a new body of questions in additive combinatorics. The fundamental Cauchy–Davenport theorem gives a lower bound on the size of a sumset A + B for subsets of the cyclic group ℤ p of order p (p prime), and this is just one example of a large family of results. Our aim in this paper is to investigate what happens if we restrict the number of elements of one set that we may use to form the sums. Here is the question we set out to answer: given two subsets, A and B, does B have a subset B′ of bounded size such that A + B′ is large, perhaps even comparable to the size of A + B? In particular, can we get close to the lower bound of the Cauchy–Davenport theorem? Our main results show that, rather surprisingly, in many circumstances it is possible to obtain not merely an asymptotic version of the usual sumset bound, but even the exact bound itself. For example, in ℤ, we show that if A and B have size n then there are three elements b 1, b 2, b 3 ∈ B such that ∣(A + b 1) ∪ (A + b 2) ∪ (A + b 3)∣ ⩾ 2n − 1. And for ℤ p itself, we show the following: if A and B have size n, where n ⩽ p/3, then there is a subset B′ of B of size c such that ∣A + B′∣ ⩾ 2n − 1. Here c is an absolute constant. In the inverse direction for this result, we show that if for every subset B′ of B of size c we have ∣A + B′∣ ⩽ 2n − 1 + r, where r ⩽ εn for some absolute constant ε, then B is contained in an arithmetic progression of size n + r. We also prove ‘unbalanced’ forms of our results, when the sizes of A and B may differ. As an application, we prove some considerable extensions of the Erdős–Heilbronn problem. We also present versions in the continuous setting, and give several open problems.
- Open Access
- 3 October 2024
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 31 (4) , P4.21
Layered Subgraphs of the Hypercube
A subgraph of the $n$-dimensional hypercube is called 'layered' if it is a subgraph of a layer of some hypercube. In this paper we show that there exist subgraphs of the cube of arbitrarily large girth that are not layered. This answers a question of Axenovich, Martin and Winter. Perhaps surprisingly, these subgraphs may even be taken to be induced.
- 3 October 2024
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 31 (4) , P4.21
Open AccessLayered Subgraphs of the Hypercube
A subgraph of the $n$-dimensional hypercube is called 'layered' if it is a subgraph of a layer of some hypercube. In this paper we show that there exist subgraphs of the cube of arbitrarily large girth that are not layered. This answers a question of Axenovich, Martin and Winter. Perhaps surprisingly, these subgraphs may even be taken to be induced.
- Open Access
Odd Covers of Complete Graphs and Hypergraphs
The `odd cover number' of a complete graph is the smallest size of a family of complete bipartite graphs that covers each edge an odd number of times. For $n$ odd, Buchanan, Clifton, Culver, Nie, O'Neill, Rombach and Yin showed that the odd cover number of $K_n$ is equal to $(n+1)/2$ or $(n+3)/2$, and they conjectured that it is always $(n+1)/2$. We prove this conjecture. For $n$ even, Babai and Frankl showed that the odd cover number of $K_n$ is always at least $n/2$, and the above authors and Radhakrishnan, Sen and Vishwanathan gave some values of $n$ for which equality holds. We give some new examples. Our constructions arise from some very symmetric constructions for the corresponding problem for complete hypergraphs. Thus the odd cover number of the complete 3-graph $K_n^{(3)}$ is the smallest number of complete 3-partite 3-graphs such that each 3-set is in an odd number of them. We show that the odd cover number of $K_n^{(3)}$ is exactly $n/2$ for even $n$, and we show that for odd $n$ it is $(n-1)/2$ for infinitely many values of $n$. We also show that for $r=3$ and $r=4$ the odd cover number of $K_n^{(r)}$ is strictly less than the partition number, answering a question of Buchanan, Clifton, Culver, Nie, O'Neill, Rombach and Yin for those values of $r$.Open AccessOdd Covers of Complete Graphs and Hypergraphs
The `odd cover number' of a complete graph is the smallest size of a family of complete bipartite graphs that covers each edge an odd number of times. For $n$ odd, Buchanan, Clifton, Culver, Nie, O'Neill, Rombach and Yin showed that the odd cover number of $K_n$ is equal to $(n+1)/2$ or $(n+3)/2$, and they conjectured that it is always $(n+1)/2$. We prove this conjecture. For $n$ even, Babai and Frankl showed that the odd cover number of $K_n$ is always at least $n/2$, and the above authors and Radhakrishnan, Sen and Vishwanathan gave some values of $n$ for which equality holds. We give some new examples. Our constructions arise from some very symmetric constructions for the corresponding problem for complete hypergraphs. Thus the odd cover number of the complete 3-graph $K_n^{(3)}$ is the smallest number of complete 3-partite 3-graphs such that each 3-set is in an odd number of them. We show that the odd cover number of $K_n^{(3)}$ is exactly $n/2$ for even $n$, and we show that for odd $n$ it is $(n-1)/2$ for infinitely many values of $n$. We also show that for $r=3$ and $r=4$ the odd cover number of $K_n^{(r)}$ is strictly less than the partition number, answering a question of Buchanan, Clifton, Culver, Nie, O'Neill, Rombach and Yin for those values of $r$. - Open Access
Layered subgraphs of the hypercube
A subgraph of the $n$-dimensional hypercube is called 'layered' if it is a subgraph of a layer of some hypercube. In this paper we show that there exist subgraphs of the cube of arbitrarily large girth that are not layered. This answers a question of Axenovich, Martin and Winter. Perhaps surprisingly, these subgraphs may even be taken to be induced.
Open AccessLayered subgraphs of the hypercube
A subgraph of the $n$-dimensional hypercube is called 'layered' if it is a subgraph of a layer of some hypercube. In this paper we show that there exist subgraphs of the cube of arbitrarily large girth that are not layered. This answers a question of Axenovich, Martin and Winter. Perhaps surprisingly, these subgraphs may even be taken to be induced.
- Open Access
Random Translates in Minkowski Sums
Suppose that $A$ and $B$ are sets in $\mathbb{R}^d$, and we form the sumset of $A$ with $n$ random points of $B$. Given the volumes of $A$ and $B$, how should we choose them to minimize the expected volume of this sumset? Our aim in this paper is to show that we should take $A$ and $B$ to be Euclidean balls. We also consider the analogous question in the torus $\mathbb{T}^d$, and we show that in this case the optimal choices of $A$ and $B$ are bands, in other words, sets of the form $[x,y]\times\mathbb{T}^{d-1}$. We also give stability versions of our results.Open AccessRandom Translates in Minkowski Sums
Suppose that $A$ and $B$ are sets in $\mathbb{R}^d$, and we form the sumset of $A$ with $n$ random points of $B$. Given the volumes of $A$ and $B$, how should we choose them to minimize the expected volume of this sumset? Our aim in this paper is to show that we should take $A$ and $B$ to be Euclidean balls. We also consider the analogous question in the torus $\mathbb{T}^d$, and we show that in this case the optimal choices of $A$ and $B$ are bands, in other words, sets of the form $[x,y]\times\mathbb{T}^{d-1}$. We also give stability versions of our results. - Open Access
Some New Results on Monochromatic Sums and Products in the Rationals
Our aim in this paper is to show that, for any $k$, there is a finite colouring of the set of rationals whose denominators contain only the first $k$ primes such that no infinite set has all of its finite sums and products monochromatic. We actually prove a `uniform' form of this: there is a finite colouring of the rationals with the property that no infinite set whose denominators contain only finitely many primes has all of its finite sums and products monochromatic. We also give various other results, including a new short proof of the old result that there is a finite colouring of the naturals such that no infinite set has all of its pairwise sums and products monochromatic.Open AccessSome New Results on Monochromatic Sums and Products in the Rationals
Our aim in this paper is to show that, for any $k$, there is a finite colouring of the set of rationals whose denominators contain only the first $k$ primes such that no infinite set has all of its finite sums and products monochromatic. We actually prove a `uniform' form of this: there is a finite colouring of the rationals with the property that no infinite set whose denominators contain only finitely many primes has all of its finite sums and products monochromatic. We also give various other results, including a new short proof of the old result that there is a finite colouring of the naturals such that no infinite set has all of its pairwise sums and products monochromatic. - Open Access
A Ramsey Characterisation of Eventually Periodic Words
A factorisation $x = u_1 u_2 \cdots$ of an infinite word $x$ on alphabet $X$ is called `monochromatic', for a given colouring of the finite words $X^*$ on alphabet $X$, if each $u_i$ is the same colour. Wojcik and Zamboni proved that the word $x$ is periodic if and only if for every finite colouring of $X^*$ there is a monochromatic factorisation of $x$. On the other hand, it follows from Ramsey's theorem that, for \textit{any} word $x$, for every finite colouring of $X^*$ there is a suffix of $x$ having a monochromatic factorisation. A factorisation $x = u_1 u_2 \cdots$ is called `super-monochromatic' if each word $u_{k_1} u_{k_2} \cdots u_{k_n}$, where $k_1 < \cdots < k_n$, is the same colour. Our aim in this paper is to show that a word $x$ is eventually periodic if and only if for every finite colouring of $X^*$ there is a suffix of $x$ having a super-monochromatic factorisation. Our main tool is a Ramsey result about alternating sums that may be of independent interest.Open AccessA Ramsey Characterisation of Eventually Periodic Words
A factorisation $x = u_1 u_2 \cdots$ of an infinite word $x$ on alphabet $X$ is called `monochromatic', for a given colouring of the finite words $X^*$ on alphabet $X$, if each $u_i$ is the same colour. Wojcik and Zamboni proved that the word $x$ is periodic if and only if for every finite colouring of $X^*$ there is a monochromatic factorisation of $x$. On the other hand, it follows from Ramsey's theorem that, for \textit{any} word $x$, for every finite colouring of $X^*$ there is a suffix of $x$ having a monochromatic factorisation. A factorisation $x = u_1 u_2 \cdots$ is called `super-monochromatic' if each word $u_{k_1} u_{k_2} \cdots u_{k_n}$, where $k_1 < \cdots < k_n$, is the same colour. Our aim in this paper is to show that a word $x$ is eventually periodic if and only if for every finite colouring of $X^*$ there is a suffix of $x$ having a super-monochromatic factorisation. Our main tool is a Ramsey result about alternating sums that may be of independent interest. - Open Access
Large sumsets from small subsets
In this paper we start to investigate a new body of questions in additive combinatorics. The fundamental Cauchy--Davenport theorem gives a lower bound on the size of a sumset A+B for subsets of the cyclic group Zp of order p (p prime), and this is just one example of a large family of results. Our aim in this paper is to investigate what happens if we restrict the number of elements of one set that we may use to form the sums. Here is the question we set out to answer: given two subsets, A and B, does B have a subset C of bounded size such that A+C is large, perhaps even comparable to the size of A+B? In particular, can we get close to the lower bound of the Cauchy--Davenport theorem? Our main results show that, rather surprisingly, in many circumstances it is possible to obtain not merely an asymptotic version of the usual sumset bound, but even the exact bound itself.
Open AccessLarge sumsets from small subsets
In this paper we start to investigate a new body of questions in additive combinatorics. The fundamental Cauchy--Davenport theorem gives a lower bound on the size of a sumset A+B for subsets of the cyclic group Zp of order p (p prime), and this is just one example of a large family of results. Our aim in this paper is to investigate what happens if we restrict the number of elements of one set that we may use to form the sums. Here is the question we set out to answer: given two subsets, A and B, does B have a subset C of bounded size such that A+C is large, perhaps even comparable to the size of A+B? In particular, can we get close to the lower bound of the Cauchy--Davenport theorem? Our main results show that, rather surprisingly, in many circumstances it is possible to obtain not merely an asymptotic version of the usual sumset bound, but even the exact bound itself.
- Open Access
The extremal number of Venn diagrams
We show that there exists an absolute constant $C>0$ such that any family $\mathcal{F}\subset \{0,1\}^n$ of size at least $Cn^3$ has dual VC-dimension at least 3. Equivalently, every family of size at least $Cn^3$ contains three sets such that all eight regions of their Venn diagram are non-empty. This improves upon the $Cn^{3.75}$ bound of Gupta, Lee and Li and is sharp up to the value of the constant.Open AccessThe extremal number of Venn diagrams
We show that there exists an absolute constant $C>0$ such that any family $\mathcal{F}\subset \{0,1\}^n$ of size at least $Cn^3$ has dual VC-dimension at least 3. Equivalently, every family of size at least $Cn^3$ contains three sets such that all eight regions of their Venn diagram are non-empty. This improves upon the $Cn^{3.75}$ bound of Gupta, Lee and Li and is sharp up to the value of the constant. - Open Access
Inequalities on Projected Volumes
In this paper we study the following geometric problem: given $2^n-1$ real numbers $x_A$ indexed by the non-empty subsets $A\subset \{1,..,n\}$, is it possible to construct a body $T\subset \mathbb{R}^n$ such that $x_A=|T_A|$ where $|T_A|$ is the $|A|$-dimensional volume of the projection of $T$ onto the subspace spanned by the axes in $A$? As it is more convenient to take logarithms we denote by $\psi_n$ the set of all vectors $x$ for which there is a body $T$ such that $x_A=\log |T_A|$ for all $A$. Bollob\'as and Thomason showed that $\psi_n$ is contained in the polyhedral cone defined by the class of `uniform cover inequalities'. Tan and Zeng conjectured that the convex hull $\DeclareMathOperator{\conv}{conv}$ $\conv(\psi_n)$ is equal to the cone given by the uniform cover inequalities. We prove that this conjecture is `nearly' right: the closed convex hull $\overline{\conv}(\psi_n)$ is equal to the cone given by the uniform cover inequalities. However, perhaps surprisingly, we also show that $\conv (\psi_n)$ is not closed for $n\ge 4$, thus disproving the conjecture.Open AccessInequalities on Projected Volumes
In this paper we study the following geometric problem: given $2^n-1$ real numbers $x_A$ indexed by the non-empty subsets $A\subset \{1,..,n\}$, is it possible to construct a body $T\subset \mathbb{R}^n$ such that $x_A=|T_A|$ where $|T_A|$ is the $|A|$-dimensional volume of the projection of $T$ onto the subspace spanned by the axes in $A$? As it is more convenient to take logarithms we denote by $\psi_n$ the set of all vectors $x$ for which there is a body $T$ such that $x_A=\log |T_A|$ for all $A$. Bollob\'as and Thomason showed that $\psi_n$ is contained in the polyhedral cone defined by the class of `uniform cover inequalities'. Tan and Zeng conjectured that the convex hull $\DeclareMathOperator{\conv}{conv}$ $\conv(\psi_n)$ is equal to the cone given by the uniform cover inequalities. We prove that this conjecture is `nearly' right: the closed convex hull $\overline{\conv}(\psi_n)$ is equal to the cone given by the uniform cover inequalities. However, perhaps surprisingly, we also show that $\conv (\psi_n)$ is not closed for $n\ge 4$, thus disproving the conjecture.