Search

Suppose that we have a finite colouring of $$\mathbb R$$ . What sumset-type structures can we hope to find in some colour class? One of our aims is to show that there is such a colouring for which no uncountable set has all of its pairwise sums monochromatic. We also show that there is such a colouring such that there is no infinite set X with $$X+X$$ (the pairwise sums from X, allowing repetition) monochromatic. These results assume CH. In the other direction, we show that if each colour class is measurable, or each colour class is Baire, then there is an infinite set X (and even an uncountable X, of size the reals) with $$X+X$$ monochromatic. We also give versions for all of these results for k-wise sums in place of pairwise sums. [ABSTRACT FROM AUTHOR]

Suppose that d ≥ 2 and m are fixed. For which n is it the case that any n angles can be realised by placing m points in R? A simple degrees of freedom argument shows that m points in R cannot realise more than 2 m - 4 general angles. We give a construction to show that this bound is sharp when m ≥ 5. In d dimensions the degrees of freedom argument gives an upper bound of $$dm - \left( {_2^{d + 1}} \right) - 1$$ general angles. However, the above result does not generalise to this case; surprisingly, the bound of 2 m-4 from two dimensions cannot be improved at all. Indeed, our main result is that there are sets of 2 m - 3 angles that cannot be realised by m points in any dimension. [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]

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]

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]

Our aim in this paper is to address the following question: of the 22 n Boolean functions on n variables, how many are expressible as 2-SAT formulae? In other words, we wish to count the number of different instances of 2-SAT, counting two instances as equivalent if they have the same set of satisfying assignments. Viewed geometrically, we are asking for the number of subsets of the n-dimensional discrete cube that are unions of ( n-2)-dimensional subcubes. There is a trivial upper bound of 24(n/2), the number of 2-SAT formulae. There is also an obvious lower bound of 2(n/2), corresponding to the monotone 2-SAT formulae. Our main result is that, rather surprisingly, this lower bound gives the correct speed: the number of 2-SAT functions is 2(1+0(1)) n 2 2. [ABSTRACT FROM AUTHOR]

Our aim in this note is to present a transitive graph that we conjecture is not quasi-isometric to any Cayley graph. No such graph is currently known. Our graph arises both as an abstract limit in a suitable space of graphs and in a concrete way as a subset of a product of trees. [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]

An infinite graph is called bounded if for every labelling of its vertices with natural numbers there exists a sequence of natural numbers which eventually exceeds the labelling along any ray in the graph. We prove an old conjecture of Halin, which characterizes the bounded graphs in terms of four forbidden topological subgraphs. [ABSTRACT FROM AUTHOR]

We consider infinite matrices with entries fromℤ (and only finitely many nonzero entries on any row). A matrix A is partition regular overℕ provided that, whenever the setℕ of positive integers is partitioned into finitely many classes there is a vector $$\overrightarrow x$$ with entries inℤ such that all entries of A $$A\overrightarrow x$$ lie in the same cell of the partition. We show that, in marked contrast with the situation for finite matrices, there exists a finite partition ofℕ no cell of which contains solutions for all partition regular matrices and determine which of our pairs of matrices must always have solutions in the same cell of a partition. [ABSTRACT FROM AUTHOR]

The grid graph is the graph on [ k]={0,..., k−1} in which x=( x) is joined to y=( y) if for some i we have | x −y|=1 and x= y for all j≠ i. In this paper we give a lower bound for the number of edges between a subset of [ k] of given cardinality and its complement. The bound we obtain is essentially best possible. In particular, we show that if A⊂[ k] satisfies k/4≤| A|≤3 k/4 then there are at least k edges between A and its complement. Our result is apparently the first example of an isoperimetric inequality for which the extremal sets do not form a nested family. We also give a best possible upper bound for the number of edges spanned by a subset of [ k] of given cardinality. In particular, for r=1,..., k we show that if A⊂[ k] satisfies | A|≤ r then the subgraph of [ k] induced by A has average degree at most 2 n(1−1/ r). [ABSTRACT FROM AUTHOR]