14 papers
No--in-line problem for
Anubhab Ghosal, Ritesh Goenka, Alexandr Grebennikov +3
What is the maximum number of points one can place in an grid such that every Euclidean line contains at most points? For , this is the notorious no-three-i…
On the largest sum-free subset of the lattice cube
Peter Keevash, Jeck Lim
We determine the limiting density of the largest sum-free subset of the lattice cube for all , thus resolving the natural conjecture that it is constructed…
A very robust Ramsey theorem for matchings
Peter Keevash, Peleg Michaeli
Our main result is a robust generalisation of the Cockayne-Lorimer theorem on the multicolour Ramsey number of matchings. It is moreover a generalisation of the transference genera…
Source localisation in simple random walks
Ritesh Goenka, Peter Keevash, Tomasz Przybyłowski
We consider the problem of locating the source (starting vertex) of a simple random walk, given a snapshot of the set of edges (or vertices) visited in the first steps. Conside…
A generalised Ramsey--Turán problem for matchings
Peter Keevash, Peleg Michaeli
We prove a generalised Ramsey--Turán theorem for matchings, which (a) simultaneously generalises the Cockayne--Lorimer Theorem (Ramsey for matchings) and the Erdős--Gallai Theorem…
On subsets of lattice cubes avoiding affine and spherical degeneracies
Anubhab Ghosal, Ritesh Goenka, Peter Keevash
For integers and , we establish new lower bounds on the maximum number of points in such that no lie in a -dimensional affine (or linear) su…
Cyclic subsets in regular Dirac graphs
Nemanja Draganić, Peter Keevash, Alp Müyesser
In 1996, in his last paper, Erdős asked the following question that he formulated together with Faudree: is there a positive such that any -regular graph on ver…
Pósa rotation through a random permutation
Nemanja Draganić, Peter Keevash
What minimum degree of a graph on vertices guarantees that the union of and a random -factor (or permutation) is with high probability Hamiltonian? Girão and Espuny…
A short proof of the existence of designs
Peter Keevash
We give a new proof of the existence of designs, which is much shorter and gives better bounds.
The structure of sets with cube-avoiding sumsets
Thomas Karam, Peter Keevash
We prove that if is an integer, is a finite abelian group, is a subset of not contained in any strict coset in , and are dense subsets of…
Additive Bases: Change of Domain
Boris Bukh, Peter van Hintum, Peter Keevash
We consider two questions of Ruzsa on how the minimum size of an additive basis of a given set depends on the domain of . To state these questions, for an abelian group…
Robot Positioning Using Torus Packing for Multisets
Chung Shue Chen, Peter Keevash, Sean Kennedy +2
We consider the design of a positioning system where a robot determines its position from local observations. This is a well-studied problem of considerable practical importance an…
Dissipative particle systems on expanders
John Haslegrave, Peter Keevash
We consider a general framework for multi-type interacting particle systems on graphs, where particles move one at a time by random walk steps, different types may have different s…
Balanced two-type annihilation: mean-field asymptotics
John Haslegrave, Peter Keevash
We consider an interacting particle system where equal-sized populations of two types of particles move by random walk steps on a graph, the two types may have different speeds, an…