Search

A (finite or infinite) graph is called constructible if it may be obtained recursively from the one-point graph by repeatedly adding dominated vertices. In the finite case, the constructible graphs are precisely the cop-win graphs, but for infinite graphs the situation is not well understood. One of our aims in this paper is to give a graph that is cop-win but not constructible. This is the first known such example. We also show that every countable ordinal arises as the rank of some constructible graph, answering a question of Evron, Solomon and Stahl. In addition, we give a finite constructible graph for which there is no construction order whose associated domination map is a homomorphism, answering a question of Chastand, Laviolette and Polat. Lehner showed that every constructible graph is a weak cop win (meaning that the cop can eventually force the robber out of any finite set). Our other main aim is to investigate how this notion relates to the notion of 'locally constructible' (every finite graph is contained in a finite constructible subgraph). We show that, under mild extra conditions, every locally constructible graph is a weak cop win. But we also give an example to show that, in general, a locally constructible graph need not be a weak cop win. Surprisingly, this graph may even be chosen to be locally finite. We also give some open problems. [ABSTRACT FROM AUTHOR]

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 short note is to give a 'directed' version of this result; we show that a family of oriented graphs such that any two have strongly-connected intersection has size at most 1 / 3 n of all oriented graphs. We also show that a family of graphs such that any two have Hamiltonian intersection has size at most 1 / 2 n of all graphs, verifying a conjecture of the above authors. [ABSTRACT FROM AUTHOR]

In this paper we study the following geometric problem: given $2^n-1$ real numbers $x_A$ indexed by the nonempty subsets $A\subset \{1,\dots,n\}$, is it possible to construct a body $T\subset \mathbb{R}^n$ such that $x_A=|T_A|$, where $|T_A|$ is the $|A|$-dimensional volume of the projection of $T$ onto the subspace spanned by the axes in $A$? As it is more convenient to take logarithms, we denote by $\psi_n$ the set of all vectors $x$ for which there is a body $T$ such that $x_A=\log |T_A|$ for all $A$. Bollobás and Thomason showed that $\psi_n$ is contained in the polyhedral cone defined by the class of "uniform cover inequalities." Tan and Zeng conjectured that the convex hull $\operatorname{conv}(\psi_n)$ is equal to the cone given by the uniform cover inequalities. We prove that this conjecture is "nearly" right: the closed convex hull $\overline{\operatorname{conv}}(\psi_n)$ is equal to the cone given by the uniform cover inequalities. However, perhaps surprisingly, we also show that $\operatorname{conv}(\psi_n)$ is not closed for $n\ge 4$, thus disproving the conjecture. [ABSTRACT FROM AUTHOR]

We show that there is a rational vector space V such that, whenever V is finitely coloured, there is an infinite set X whose sumset X + X is monochromatic. Our example is the rational vector space of dimension sup{..., ...). This complements a result of Hindman, Leader and Strauss, who showed that the result does not hold for dimension below ...w. So our result is best possible under GCH. [ABSTRACT FROM AUTHOR]

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]

Gallai's colouring theorem states that if the edges of a complete graph are 3-coloured, with each colour class forming a connected (spanning) subgraph, then there is a triangle that has all three colours. What happens for more colours: if we $$k$$ -colour the edges of the complete graph, with each colour class connected, how many of the $$\left( {\begin{array}{c}k\\ 3\end{array}}\right) $$ triples of colours must appear as triangles? In this note we show that the 'obvious' conjecture, namely that there are always at least $$\left( {\begin{array}{c}k-1\\ 2\end{array}}\right) $$ triples, is not correct. We determine the minimum asymptotically. This answers a question of Johnson. We also give some results about the analogous problem for hypergraphs, and we make a conjecture that we believe is the 'right' generalisation of Gallai's theorem to hypergraphs. [ABSTRACT FROM AUTHOR]

How many random transpositions (meaning that we swap given pairs of elements with given probabilities independently) are needed to ensure that each element of [n] is uniformly distributed--in the sense that the probability that i is mapped to j is 1/n for all i and j And what if we insist that each pair is uniformly distributed In this paper we show that the minimum for the first problem is about 1 2nlog2 n, with this being exact when n is a power of 2. For the second problem, we show that, rather surprisingly, the answer is not quadratic: O(nlog2 n) random transpositions suffice. We also show that if we ask only that the pair (1, 2) is uniformly distributed, then the answer is 2n 3. This proves a conjecture of Groenland, Johnston, Radcliffe, and Scott. [ABSTRACT FROM AUTHOR]

An oriented 3-graph consists of a family of triples (3-sets), each of which is given one of its two possible cyclic orientations. A cycle in an oriented 3-graph is a positive sum of some of the triples that gives weight zero to each 2-set. Our aim in this paper is to consider the following question: how large can the girth of an oriented 3-graph be? We show that there exist oriented 3-graphs whose shortest cycle has length $$\frac{n^2}{2}(1+o(1))$$ : this is asymptotically best possible. We also show that there exist 3-tournaments whose shortest cycle has length $$\frac{n^2}{3}(1+o(1))$$ , in complete contrast to the case of 2-tournaments. [ABSTRACT FROM AUTHOR]

Abstract: We show that any subgraph of the hypercube of average degree contains a geodesic of length , where by geodesic we mean a shortest path in . This result, which is best possible, strengthens a theorem of Feder and Subi. It is also related to the ‘antipodal colourings’ conjecture of Norine. [Copyright &y& Elsevier]

Abstract: How large can a family be if it does not contain with ? Our aim in this paper is to show that any such family has size at most . This is tight up to a multiplicative constant of 2. We also obtain similar results for families with , showing that they satisfy , where is a constant depending only on . [Copyright &y& Elsevier]

Abstract: Let be a family of subsets of an -set such that does not contain distinct sets and with . How large can be? Our aim in this note is to determine the maximum size of such an . This answers a question of Kalai. We also give some related results and conjectures. [Copyright &y& Elsevier]

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: It is easy to deduce from Ramsey''s theorem that given positive integers and a finite colouring of the set of positive integers, there exists an injective sequence with all sums of the form () lying in the same colour class. The consistency version of this result, namely that given positive integers and , and a finite colouring of , there exist injective sequences and with all sums of the form and all sums of the form () in the same colour class, was open for some time, being recently proved by Hindman, Leader and Strauss. The proof is long and relies heavily on the structure of the semigroup of ultrafilters on . Our aim in this note is to present a short proof of this result which does not use properties of . Our proof also gives various results not obtainable by the previous method of proof. [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]

Our aim in this note is to show that if A is a family of (k/3) 3-sets then there are at least (k/4) 3-sets then there are at least (k/4) 4-sets that may be written as unions of two 2-sets in the shadow of A. This is the first non-trivial case of a more general conjecture about unions of shadows. [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]

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]

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 fc primes such that no infinite set has all of its finite sums and products monochromatic. We actually prove a 'uniform' form of this: there is a finite colouring of the rationals with the property that no infinite set whose denominators contain only finitely many primes has all of its finite sums and products monochromatic. We also give various other results, including a new short proof of the old result that there is a finite colouring of the naturals such that no infinite set has all of its pairwise sums and products monochromatic. [ABSTRACT FROM AUTHOR]

The set 0+ of ultrafilters on (0,1) that converge to 0 is a semigroup under the restriction of the usual operation + on &BetaR[subd] the Stone-Çech compactification of the discrete semigroup (R[subd], +). It is also a subsemigroup of Β((0, 1)[subd]). The interaction of these operations has recently yielded some strong results in Ramsey Theory. Since (0[sup+],.) is an ideal of &Beta((0, 1)[subd],.), much is known about the structure of (0[sup+],.). On the other hand, (0[sup+],+) is far from being an ideal of (ΒR[subd],+) so little about its algebraic structure follows from known results. We characterize here the smallest ideal of (0[sup+],+), its closure, and those sets "central" in (0[sup+],+), that is, those sets which are members of minimal idempotents in (0[sup+],+). We derive new combinatorial applications of those sets that are central in (0[sup+],+). [ABSTRACT FROM AUTHOR]

Abstract: A function f from to is said to be feebly continuous at a point if there exist sequences and with . Dales asked if every function has a point of feeble continuity. Our aim in this short note is to show that (assuming the Continuum Hypothesis) the answer is ‘no’. Dales also asked what happens for functions taking only two values: we show that in this case the answer is ‘yes’. [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]

Abstract: We prove that the set of vertex-transitive graphs of finite degree is uncountably large. [Copyright &y& Elsevier]

A finite or infinite matrix A with rational entries is called partition regular if whenever the natural numbers are finitely coloured there is a monochromatic vector x with Ax = 0. Many of the classical theorems of Ramsey Theory may naturally be interpreted as assertions that particular matrices are partition regular. In the finite case, Rado proved that a matrix is partition regular if and only it satisfies a computable condition known as the columns property. The first requirement of the columns property is that some set of columns sums to zero. In the infinite case, much less is known. There are many examples of matrices with the columns property that are not partition regular, but until now all known examples of partition regular matrices did have the columns property. Our main aim in this paper is to show that, perhaps surprisingly, there are infinite partition regular matrices without the columns property -- in fact, having no set of columns summing to zero. We also make a conjecture that if a partition regular matrix (say with integer coefficients) has bounded row sums then it must have the columns property, and prove a first step towards this. [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: 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]

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]

Given a countable dense subset S of a finite-dimensional normed space X, and 0 < p < 1, we form a random graph on S by joining, independently and with probability p, each pair of points at distance less than 1. We say that S is Rado if any two such random graphs are (almost surely) isomorphic. Bonato and Janssen showed that in ℓ∞d almost all S are Rado. Our main aim in this paper is to show that ℓ∞d is the unique normed space with this property: indeed, in every other space almost all sets S are non-Rado. We also determine which spaces admit some Rado set: this turns out to be the spaces that have an ℓ∞ direct summand. These results answer questions of Bonato and Janssen. A key role is played by the determination of which finite-dimensional normed spaces have the property that every bijective step-isometry (meaning that the integer part of distances is preserved) is in fact an isometry. This result may be of independent interest. [ABSTRACT FROM AUTHOR]

It is shown that the maximum number of patterns that can occur in a permutation of length n is asymptotically 2 n . This significantly improves a previous result of Coleman. [ABSTRACT FROM AUTHOR]