Search

Abstract Let P be a poset of size 2 k that has a greatest and a least element. We prove that, for sufficiently large n , the Boolean lattice 2 [ n ] can be partitioned into copies of P. This resolves a conjecture of Lonc. [ABSTRACT FROM AUTHOR]

Abstract: A finite set X in some Euclidean space is called Ramsey if for any k there is a d such that whenever is k-coloured it contains a monochromatic set congruent to X. This notion was introduced by Erdős, Graham, Montgomery, Rothschild, Spencer and Straus, who asked if a set is Ramsey if and only if it is spherical, meaning that it lies on the surface of a sphere. This question (made into a conjecture by Graham) has dominated subsequent work in Euclidean Ramsey theory. In this paper we introduce a new conjecture regarding which sets are Ramsey; this is the first ever ‘rival’ conjecture to the conjecture above. Calling a finite set transitive if its symmetry group acts transitively—in other words, if all points of the set look the same—our conjecture is that the Ramsey sets are precisely the transitive sets, together with their subsets. One appealing feature of this conjecture is that it reduces (in one direction) to a purely combinatorial statement. We give this statement as well as several other related conjectures. We also prove the first non-trivial cases of the statement. Curiously, it is far from obvious that our new conjecture is genuinely different from the old. We show that they are indeed different by proving that not every spherical set embeds in a transitive set. This result may be of independent interest. [Copyright &y& Elsevier]

It is proved that a connected infinite graph has a normal spanning tree (the infinite analogue of a depth-first search tree) if and only if it has no minor obtained canonically from either an (50, 51)-regular bipartite graph or an order-theoretic Aronszajn tree. This disproves Halin's conjecture that only the first of these obstructions was needed to characterize the graphs with normal spanning trees. As a corollary Halin's further conjecture is deduced, that a connected graph has a normal spanning tree if and only if all its minors have countable colouring number.The precise classification of the (50, 51)-regular bipartite graphs remains an open problem. One such class turns out to contain obvious infinite minor-antichains, so as an unexpected corollary Thomas's result that the infinite graphs are not well-quasi-ordered as minors is reobtained. [ABSTRACT FROM AUTHOR]

Abstract: Let be a finite matrix with rational entries. We say that is doubly image partition regular if whenever the set of positive integers is finitely coloured, there exists such that the entries of are all the same colour (or monochromatic) and also, the entries of are monochromatic. Which matrices are doubly image partition regular? More generally, we say that a pair of matrices , where and have the same number of rows, is doubly kernel partition regular if whenever is finitely coloured, there exist vectors and , each monochromatic, such that . (So the case above is the case when is the negative of the identity matrix.) There is an obvious sufficient condition for the pair to be doubly kernel partition regular, namely that there exists a positive rational such that the matrix is kernel partition regular. (That is, whenever is finitely coloured, there exists monochromatic such that .) Our aim in this paper is to show that this sufficient condition is also necessary. As a consequence we have that a matrix is doubly image partition regular if and only if there is a positive rational such that the matrix is kernel partition regular, where is the identity matrix of the appropriate size. We also prove extensions to the case of several matrices. [Copyright &y& Elsevier]

Abstract: A system of homogeneous linear equations with integer coefficients is partition regular if, whenever the natural numbers are finitely coloured, the system has a monochromatic solution. The Finite Sums theorem provided the first example of an infinite partition regular system of equations. Since then, other such systems of equations have been found, but each can be viewed as a modification of the Finite Sums theorem. We present here a new infinite partition regular system of equations that appears to arise in a genuinely different way. This is the first example of a partition regular system in which a variable occurs with unbounded coefficients. A modification of the system provides an example of a system that is partition regular over but not , settling another open problem. [Copyright &y& Elsevier]