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]

We say a family of subsets of { 1 , 2 , … , n } is antipodal if it is closed under taking complements. We prove a best-possible isoperimetric inequality for antipodal families of subsets of { 1 , 2 , … , n } (of any size). Our inequality implies that for any k ∈ N , among all such families of size 2 k , a family consisting of the union of two antipodal ( k − 1 ) -dimensional subcubes has the smallest possible edge boundary. [ABSTRACT FROM AUTHOR]

Let f r ( n ) be the minimum number of complete r -partite r -graphs needed to partition the edge set of the complete r -uniform hypergraph on n vertices. Graham and Pollak showed that f 2 ( n ) = n − 1 . An easy construction shows that f r ( n ) ≤ ( 1 − o ( 1 ) ) ( n ⌊ r / 2 ⌋ ) and it has been unknown if this upper bound is asymptotically sharp. In this paper we show that f r ( n ) ≤ ( 14 15 + o ( 1 ) ) ( n r / 2 ) for each even r ≥ 4 . [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]

Abstract: A k-signed r-set on is an ordered pair , where A is an r-subset of and f is a function from A to . Families are said to be cross-intersecting if any set in any family intersects any set in any other family . Hilton proved a sharp bound for the sum of sizes of cross-intersecting families of r-subsets of . Our aim is to generalise Hilton''s bound to one for families of k-signed r-sets on . The main tool developed is an extension of Katona''s cyclic permutation argument. [Copyright &y& Elsevier]

Abstract: A matrix A is said to be partition regular (PR) over a subset S of the positive integers if whenever S is finitely coloured, there exists a vector x, with all elements in the same colour class in S, which satisfies . We also say that S is PR for A. Many of the classical theorems of Ramsey Theory, such as van der Waerden''s theorem and Schur''s theorem, may naturally be interpreted as statements about partition regularity. Those matrices which are partition regular over the positive integers were completely characterised by Rado in 1933. Given matrices A and B, we say that A Rado-dominates B if any set which is PR for A is also PR for B. One trivial way for this to happen is if every solution to actually contains a solution to . Bergelson, Hindman and Leader conjectured that this is the only way in which one matrix can Rado-dominate another. In this paper, we prove this conjecture for the first interesting case, namely for matrices. We also show that, surprisingly, the conjecture is not true in general. [Copyright &y& Elsevier]

Abstract: Let G be an abelian group of order k. How is the problem of minimizing the number of sums from a sequence of given length in G related to the problem of minimizing the number of k-sums? In this paper we show that the minimum number of k-sums for a sequence that does not have 0 as a k-sum is attained at the sequence , where is chosen to minimise the number of sums without 0 being a sum. Equivalently, to minimise the number of k-sums one should repeat some value times. This proves a conjecture of Bollobás and Leader, and extends results of Gao and of Bollobás and Leader. [Copyright &y& Elsevier]

Abstract: Our main aim in this paper is to show that, in Conway''s Angel and Devil game, an Angel of sufficient speed can always escape in three dimensions. We also prove some related results and make some conjectures. [Copyright &y& Elsevier]

We show that for any k,m,p,c, if G is a Kk-free graph on N then there is an independent set of vertices in G that contains an (m,p,c)-set. Hence if G is a Kk-free graph on N, then one can solve any partition regular system of equations in an independent set. This is a common generalization of partition regularity theorems of Rado (who characterized systems of linear equations Ax=0 a solution of which can be found monochromatic under any finite coloring of N) and Deuber (who provided another characterization in terms of (m,p,c)-sets and a partition theorem for them), and of Ramsey''s theorem itself. [Copyright &y& Elsevier]

In this note we investigate correlation inequalities for 'up-sets' of permutations, in the spirit of the Harris–Kleitman inequality. We focus on two well-studied partial orders on S n , giving rise to differing notions of up-sets. Our first result shows that, under the strong Bruhat order on S n , up-sets are positively correlated (in the Harris–Kleitman sense). Thus, for example, for a (uniformly) random permutation π , the event that no point is displaced by more than a fixed distance d and the event that π is the product of at most k adjacent transpositions are positively correlated. In contrast, under the weak Bruhat order we show that this completely fails: surprisingly, there are two up-sets each of measure 1/2 whose intersection has arbitrarily small measure. We also prove analogous correlation results for a class of non-uniform measures, which includes the Mallows measures. Some applications and open problems are discussed. [ABSTRACT FROM AUTHOR]

In this paper, we study product-free subsets of the free semigroup over a finite alphabet A. We prove that the maximum density of a product-free subset of the free semigroup over A , with respect to the natural measure that assigns a weight of | A | − n to each word of length n , is precisely 1 ∕ 2. [ABSTRACT FROM AUTHOR]

How large an antichain can we find inside a given downset in the Boolean lattice B (n) ? Sperner's theorem asserts that the largest antichain in the whole of B (n) has size n ⌊ n ∕ 2 ⌋ ; what happens for general downsets? Our main results are a Dilworth-type decomposition theorem for downsets, and a new proof of a result of Engel and Leck that determines the largest possible antichain size over all downsets of a given size. We also prove some related results, such as determining the maximum size of an antichain inside the downset that we conjecture minimizes this quantity among downsets of a given size. [ABSTRACT FROM AUTHOR]

A system of linear equations with integer coefficients is partition regular over a subset S of the reals if, whenever S ∖ { 0 } is finitely coloured, there is a solution to the system contained in one colour class. It has been known for some time that there is an infinite system of linear equations that is partition regular over R but not over Q , and it was recently shown (answering a long-standing open question) that one can also distinguish Q from Z in this way. Our aim is to show that the transition from Z to Q is not sharp: there is an infinite chain of subgroups of Q , each of which has a system that is partition regular over it but not over its predecessors. We actually prove something stronger: our main result is that if R and S are subrings of Q with R not contained in S , then there is a system that is partition regular over R but not over S . This implies, for example, that the chain above may be taken to be uncountable. [ABSTRACT FROM AUTHOR]

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]

Abstract: The cop-number of a graph is the minimum number of cops needed to catch a robber on the graph, where the cops and the robber alternate moving from a vertex to a neighbouring vertex. It is conjectured by Meyniel that for a graph on n vertices cops suffice. The aim of this paper is to investigate the cop-number of a random graph. We prove that for sparse random graphs the cop-number has order of magnitude . The best known strategy for general graphs is the area-defending strategy, where each cop ‘controls’ one region by himself. We show that, for general graphs, this strategy cannot be too effective: there are graphs that need at least cops for this strategy. [Copyright &y& Elsevier]