Search

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]

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]

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]

Our aim in this note is to make some conjectures about extremal densities of daisy-free families, where a ‘daisy’ is a certain hypergraph. These questions turn out to be related to some Turán problems in the hypercube, but they are also natural in their own right. We start by giving the daisy conjectures, and some related problems, and shall then go on to describe the connection with vertex-Turán problems in the hypercube. [ABSTRACT FROM PUBLISHER]

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]

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]

Abstract: We prove that the set of vertex-transitive graphs of finite degree is uncountably large. [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]