Imre Leader
YOU?
Author Swipe
View article: Large sumsets from small subsets
Large sumsets from small subsets Open
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), …
View article: The Maximum Number of Bases in a Family of Vectors
The Maximum Number of Bases in a Family of Vectors Open
The proportion of $d$-element subsets of $\mathbb{F}_2^d$ that are bases is asymptotic to $\prod_{j=1}^{\infty}(1-2^{-j}) \approx 0.29$ as $d \to \infty$. It is natural to ask whether there exists a (large) subset $\mathcal{F}$ of $\mathbb…
View article: Turán Densities for Small Hypercubes
Turán Densities for Small Hypercubes Open
How small can a set of vertices in the $n$-dimensional hypercube $Q_n$ be if it meets every copy of $Q_d$? The asymptotic density of such a set (for $d$ fixed and $n$ large) is denoted by $γ_d$. It is easy to see that $γ_d \leq 1/(d+1)$, a…
View article: Layered Subgraphs of the Hypercube
Layered Subgraphs of the Hypercube Open
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 …
View article: Turán densities for daisies and hypercubes
Turán densities for daisies and hypercubes Open
An ‐daisy is an ‐uniform hypergraph consisting of the six ‐sets formed by taking the union of an ‐set with each of the 2‐sets of a disjoint 4‐set. Bollobás, Leader and Malvenuto, and also Bukh, conjectured that the Turán density of the ‐da…
View article: Odd Covers of Complete Graphs and Hypergraphs
Odd Covers of Complete Graphs and Hypergraphs Open
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 od…
View article: Monochromatic Sumsets in Countable Colourings of Abelian Groups
Monochromatic Sumsets in Countable Colourings of Abelian Groups Open
Fernández-Bretón, Sarmiento and Vera showed that whenever a direct sum of sufficiently many copies of ${\mathbb Z}_4$, the cyclic group of order 4, is countably coloured there are arbitrarily large finite sets $X$ whose sumsets $X+X$ are m…
View article: Block Sizes in the Block Sets Conjecture
Block Sizes in the Block Sets Conjecture Open
A set $X$ is called Euclidean Ramsey if, for any $k$ and sufficiently large $n$, every $k$-colouring of $\mathbb{R}^n$ contains a monochromatic congruent copy of $X$. This notion was introduced by Erdős, Graham, Montgomery, Rothschild, Spe…
View article: Layered subgraphs of the hypercube
Layered subgraphs of the hypercube Open
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 …
View article: Turán Densities for Daisies and Hypercubes
Turán Densities for Daisies and Hypercubes Open
An $r$-daisy is an $r$-uniform hypergraph consisting of the six $r$-sets formed by taking the union of an $(r-2)$-set with each of the 2-sets of a disjoint 4-set. Bollobás, Leader and Malvenuto, and also Bukh, conjectured that the Turán de…
View article: A Note on Hamiltonian-Intersecting Families of Graphs
A Note on Hamiltonian-Intersecting Families of Graphs Open
How many graphs on an $n$-point set can we find such that any two have connected intersection? Berger, Berkowitz, Devlin, Doppelt, Durham, Murthy and Vemuri showed that the maximum is exactly $1/2^{n-1}$ of all graphs. Our aim in this shor…
View article: Random Translates in Minkowski Sums
Random Translates in Minkowski Sums Open
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 p…
View article: A strengthening of Freiman's 3k−4$3k-4$ theorem
A strengthening of Freiman's 3k−4$3k-4$ theorem Open
In its usual form, Freiman's theorem states that if and are subsets of of size with small sumset (of size close to ), then they are very close to arithmetic progressions. Our aim in this paper is to strengthen this by allowing only a bound…
View article: Small Sets in Union-Closed Families
Small Sets in Union-Closed Families Open
Our aim in this note is to show that, for any $\epsilon>0$, there exists a union-closed family $\mathcal F$ with (unique) smallest set $S$ such that no element of $S$ belongs to more than a fraction $\epsilon$ of the sets in $\mathcal F$. …
View article: Partial shuffles by lazy swaps
Partial shuffles by lazy swaps Open
What is the smallest number of random transpositions (meaning that we swap given pairs of elements with given probabilities) that we can make on an $n$-point set to ensure that each element is uniformly distributed -- in the sense that the…
View article: Some New Results on Monochromatic Sums and Products in the Rationals
Some New Results on Monochromatic Sums and Products in the Rationals Open
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. W…
View article: Constructible graphs and pursuit
Constructible graphs and pursuit Open
A (finite or infinite) graph is called constructible if it may be obtained\nrecursively from the one-point graph by repeatedly adding dominated vertices.\nIn the finite case, the constructible graphs are precisely the cop-win graphs,\nbut …
View article: A Ramsey characterisation of eventually periodic words
A Ramsey characterisation of eventually periodic words Open
A factorisation $x = u_1 u_2 \\cdots$ of an infinite word $x$ on alphabet $X$\nis called `monochromatic', for a given colouring of the finite words $X^*$ on\nalphabet $X$, if each $u_i$ is the same colour. Wojcik and Zamboni proved that\nt…
View article: Large sumsets from medium-sized subsets
Large sumsets from medium-sized subsets Open
The classical Cauchy--Davenport inequality gives a lower bound for the size of the sum of two subsets of ${\mathbb Z}_p$, where $p$ is a prime. Our main aim in this paper is to prove a considerable strengthening of this inequality, where w…
View article: A strengthening of Freiman's 3k-4 theorem
A strengthening of Freiman's 3k-4 theorem Open
In its usual form, Freiman's 3k-4 theorem states that if A and B are subsets of the integers of size k with small sumset (of size close to 2k) then they are very close to arithmetic progressions. Our aim in this paper is to strengthen this…
View article: Large sumsets from small subsets
Large sumsets from small subsets Open
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…
View article: Small Sets in Union-Closed Families
Small Sets in Union-Closed Families Open
Our aim in this note is to show that, for any $ε>0$, there exists a union-closed family $\mathcal F$ with (unique) smallest set $S$ such that no element of $S$ belongs to more than a fraction $ε$ of the sets in $\mathcal F$. More precisely…
View article: A Note on Transitive Union-Closed Families
A Note on Transitive Union-Closed Families Open
We show that the Union-Closed Conjecture holds for the union-closed family generated by the cyclic translates of any fixed set.
View article: A Ramsey characterisation of eventually periodic words
A Ramsey characterisation of eventually periodic words Open
A factorisation x=u1u2⋯$x = u_1 u_2 \cdots$ of an infinite word x$x$ on alphabet X$X$ is called ‘monochromatic’, for a given colouring of the finite words X∗$X^*$ on alphabet X$X$, if each ui$u_i$ is the same colour. Wojcik and Zamboni pro…
View article: Inequalities on Projected Volumes
Inequalities on Projected Volumes Open
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|$…
View article: The extremal number of Venn diagrams
The extremal number of Venn diagrams Open
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 …
View article: Inhomogeneous Partition Regularity
Inhomogeneous Partition Regularity Open
We say that the system of equations $Ax = b$, where $A$ is an integer matrix and $b$ is a (non-zero) integer vector, is partition regular if whenever the integers are finitely coloured there is a monochromatic vector $x$ with $Ax = b.$ Rad…