Discrete Mathematics, Volume 344, Issue 3, March 2021, 112256 https://doi.org/10.1016/j.disc.2020.112256 arXiv I’ve previously written about the Namer-Claimer game. I can now prove that the length of the game is with optimal play from each side, matching the greedy lower bound. The upper bound makes use of randomness, but in a very controlled way. Analysing a truly …
Tag: ramsey
Partition regularity and other combinatorial problems
This is the imaginative title of my PhD thesis. It contains four unrelated pieces of work. (I was warned off using this phrasing in the thesis itself, where the chapters are instead described as “self-contained”.) The first and most substantial concerns partition regularity. It is a coherent presentation of all of the material from Partition …
Distinguishing subgroups of the rationals by their Ramsey properties
Ben Barber, , Neil Hindman, Imre Leader and Dona Strauss, Journal of Combinatorial Theory, Series A, Volume 129, January 2015, Pages 93–104 PDF In Partition regularity in the rationals we (Barber, Hindman and Leader) showed that there are systems of equations that are partition regular over but not over . Here we show that this separation is …
Partition regularity without the columns property
Ben Barber, Neil Hindman, Imre Leader and Dona Strauss, Proc. Amer. Math. Soc. 143 (2015), 3387-3399 PDF Rado’s theorem states that a finite matrix is partition regular if and only if it has the “columns property”. It is easy to write down infinite matrices with the columns property that are not partition regular, but all known …
Partition regularity with congruence conditions
Ben Barber and Imre Leader, Journal of Combinatorics, Volume 4 (2013), Number 3 PDF Does a partition regular system remain partition regular if we ask that each variable is divisible by ? Not necessarily. This answers several open questions from Hindman, Leader and Strauss’s 2003 survey. The proof of Proposition 5 in the journal version is …
Partition regularity in the rationals
Ben Barber, Neil Hindman, Imre Leader, Journal of Combinatorial Theory, Series A, Volume 120, Issue 7, September 2013, Pages 1590–1599 PDF A system of linear equations is partition regular if, whenever the natural numbers are finitely coloured, the system of equations has a monochromatic solution. Partition regularity can also be defined over the rationals, and …
Piecewise syndetic and van der Waerden
Joel Moreira has just proved that whenever the natural numbers are finitely coloured we can find and such that , and are all the same colour. He actually proves a much more general result via links to topological dynamics, but he includes a direct proof of this special case assuming only a consequence of van der Waerden’s …