We present a programme of characterizing Ramsey classes of structures by a combination of the model theory and combinatorics. In particular, we relate the classification programme of countable homogeneous structures (of Lachlan and Cherlin) to the classification of Ramsey classes. As particular instances of this approach we characterize all Ramsey classes of graphs, tournaments and partial ordered sets. We fully characterize all monotone Ramsey classes of relational systems (of any type). We also carefully discuss the role of (admissible) orderings which lead to a new classification of Ramsey properties by means of classes of order-invariant objects.

For an arbitrary n-dimensional convex body, at least almost n Steiner symmetrizations are required in order to symmetrize the body into an isomorphic ellipsoid. We say that a body $T \subset \mathbb{R}^n$ is ‘quickly symmetrizable with function $c(\varepsilon)$’ if for any $\varepsilon > 0$ there exist only $\lfloor \varepsilon n \rfloor$ symmetrizations that transform T into a body which is $c(\varepsilon)$-isomorphic to an ellipsoid. In this note we ask, given a body $K \subset \mathbb{R}^n$, whether it is possible to remove a small portion of its volume and obtain a body $T \subset K$ which is quickly symmetrizable. We show that this question, for $c(\varepsilon)$ polynomially depending on $\frac{1}{\varepsilon}$, is equivalent to the slicing problem.

Hadwiger's well known conjecture (see the survey of Toft [9]) states that any graph $G$ has a $K_{\chi(G)}$ minor, where $\chi(G)$ is the chromatic number of $G$. Let $\alpha(G)$ denote the independence (or stability) number of $G$, namely the maximum number of pairwise nonadjacent vertices in $G$. It was observed in [1], [4], [10] that via the inequality $\chi(G)\ge {|V(G)|\over \alpha(G)}$, Hadwiger's conjecture implies

Conjecture 1.1.Any graph G on n vertices contains a$K_{\lceil {n\over \alpha(G)}\rceil}$as a minor.

The question of the maximum number $\mbox{ex}(m,n,C_{2k})$ of edges in an m by n bipartite graph without a cycle of length 2k is addressed in this note. For each $k \geq 2$, it is shown that $\mbox{ex}(m,n,C_{2k}) \leq \begin{cases} (2k-3)\bigl[(mn)^{\frac{k+1}{2k}} + m + n\bigr] & \mbox{ if }k \mbox{ is odd,}\\[2pt] (2k-3)\bigl[m^{\frac{k+2}{2k}}\, n^{\frac{1}{2}} + m + n\bigr] & \mbox{ if }k \mbox{ is even.}\\ \end{cases}$

We consider algorithms for group testing problems when nothing is known in advance about the number of defectives. Du and Hwang suggested measuring the quality of such algorithms by its so-called (first) competitive ratio (see the Introduction). Later, Du and Park suggested a second kind of competitive ratio. For each kind of competitiveness, we improve the best-known bounds: in the first case, from 1.65 to $1.5+\ep$, and in the second from 16 to 4.

The aim of this paper is to point to a difference between binary and hyperary structures. The modular counting functions of a class of structures defined by a sentence of second-order monadic logic with equality, based on binary relations, are ultimately periodic. However, this is not the case for sentences based on quaternary relations.

A set of n triangles sharing a common edge is called a book with n pages and is denoted by $B_{n}$. It is known that the Ramsey number $r ( B_{n} ) $ satisfies $r ( B_{n} ) = ( 4+o ( 1 ) ) n.$ We show that every red–blue edge colouring of $K_{ \lfloor ( 4-\varepsilon ) n \rfloor }$ with no monochromatic $B_{n}$ exhibits quasi-random properties when $\varepsilon$ tends to 0. This implies that there is a constant $c>0$ such that for every red–blue edge colouring of $K_{r ( B_{n} ) }$ there is a monochromatic $B_{n}$ whose vertices span at least $ \lfloor cn^{2} \rfloor $ edges of the same colour as the book.

As an application we find the Ramsey number for a class of graphs.

The dimension of a graph, that is, the dimension of its incidence poset, has become a major bridge between posets and graphs. Although allowing a nice characterization of planarity, this dimension behaves badly with respect to homomorphisms.

We introduce the universal dimension of a graph G as the maximum dimension of a graph having a homomorphism to G. The universal dimension, which is clearly homomorphism monotone, is related to the existence of some balanced bicolouration of the vertices with respect to some realizer.

Nontrivial new results related to the original graph dimension are subsequently deduced from our study of universal dimension, including chromatic properties, extremal properties and a disproof of two conjectures of Felsner and Trotter.

Let ${\cal T}(n,m)$ denote the set of all labelled triangle-free graphs with $n$ vertices and exactly $m$ edges. In this paper we give a short self-contained proof of the fact that there exists a constant $C>0$ such that, for all $m\geq Cn^{3/2}\sqrt{\log n}$, a graph chosen uniformly at random from ${\cal T}(n,m)$ is with probability $1-o(1)$ bipartite.

Randomized search heuristics like evolutionary algorithms and simulated annealing find many applications, especially in situations where no full information on the problem instance is available. In order to understand how these heuristics work, it is necessary to analyse their behaviour on classes of functions. Such an analysis is performed here for the class of monotone pseudo-Boolean polynomials. Results depending on the degree and the number of terms of the polynomial are obtained. The class of monotone polynomials is of special interest since simple functions of this kind can have an image set of exponential size, improvements can increase the Hamming distance to the optimum and, in order to find a better search point, it can be necessary to search within a large plateau of search points with the same fitness value.

A solid diagram of volume n is a packing of n unit cubes into a corner so that the heights of vertical stacks of cubes do not increase in either of two horizontal directions away from the corner. An asymptotic distribution of the dimensions – heights, depths, and widths – of the diagram chosen uniformly at random among all such diagrams is studied. For each k, the planar base of k tallest stacks is shown to be Plancherel distributed in the limit $n\to\infty$.

Building on the methods developed in joint work with Béla Bollobás and Svante Janson, we study the phase transition in four ‘scale-free’ random graph models, obtaining upper and lower bounds on the size of the giant component when there is one. In particular, we determine the extremely slow rate of growth of the giant component just above the phase transition. We greatly reduce the significant gaps between the existing upper and lower bounds, giving bounds that match to within a factor $1+o(1)$ in the exponent.

In all cases the method used is to couple the neighbourhood expansion process in the graph on n vertices with a continuous-type branching process that is independent of n. It can be shown (requiring some separate argument for each case) that with probability tending to 1 as $n\to\infty$ the size of the giant component divided by n is within $o(1)$ of the survival probability $\sigma$ of the branching process. This survival probability is given in terms of the maximal solution $\phi$ to certain non-linear integral equations, which can be written in the form $\phi={\bf F}(\phi)$ for a certain operator ${\bf F}$. Upper and lower bounds are found by constructing trial functions $\phi_0$, $\phi_1$ with ${\bf F}(\phi_0)\leq \phi_0$ and ${\bf F}(\phi_1)\geq \phi_1$ holding pointwise; basic properties of branching processes then imply that $\phi_1\leq \phi\leq \phi_0$, giving upper and lower bounds on $\sigma$.