ILImre Leader

Imre Leader

*This is an algorithmically generated author record based on publicly available information.

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


Imre Leader has a total of 44 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Large sumsets from small subsets

    by Béla Bollobás, Imre Leader, Marius Tiba

    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

    Layered Subgraphs of the Hypercube

    by Natalie Behague, Imre Leader, Natasha Morrison, Kada Williams

    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

    by Imre Leader, Ta Sheng Tan

    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

    by Natalie Behague, Imre Leader, Natasha Morrison, Kada Williams

    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

    by Paul Balister, Bela Bollobas, Imre Leader, Marius Tiba

    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

    by Neil Hindman, Maria-Romina Ivan, Imre Leader

    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

    by Maria-Romina Ivan, Imre Leader, Luca Q. Zamboni

    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

    by Bela Bollobas, Imre Leader, Marius Tiba

    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

    by Peter Keevash, Imre Leader, Jason Long, Adam Zsolt Wagner

    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

    by Imre Leader, Žarko Ranđelović, Eero Räty

    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.