We consider the problem of minimizing the number of triangles in a graph of given order and size, and describe the asymptotic structure of extremal graphs. This is achieved by characterizing the set of flag algebra homomorphisms that minimize the triangle density.

We prove that the chromatic polynomial of a finite graph of maximal degree Δ is free of zeros for |q| ≥ C*(Δ) with This improves results by Sokal and Borgs. Furthermore, we present a strengthening of this condition for graphs with no triangle-free vertices.

Let H be a graph on h vertices, and G be a graph on n vertices. An H-factor of G is a spanning subgraph of G consisting of n/h vertex disjoint copies of H. The fractional arboricity of H is , where the maximum is taken over all subgraphs (V′, E′) of H with |V′| > 1. Let δ(H) denote the minimum degree of a vertex of H. It is shown that if δ(H) < a(H), then n−1/a(H) is a sharp threshold function for the property that the random graph G(n, p) contains an H-factor. That is, there are two positive constants c and C so that for p(n) = cn−1/a(H) almost surely G(n, p(n)) does not have an H-factor, whereas for p(n) = Cn−1/a(H), almost surely G(n, p(n)) contains an H-factor (provided h divides n). A special case of this answers a problem of Erdős.

We give results for the age-dependent distribution of vertex degree and number of vertices of given degree in the undirected web-graph process, a discrete random graph process introduced in [8]. For such processes we show that as $k \rightarrow \infty$, the expected proportion of vertices of degree $k$ has power law parameter $1+1/\eta$ where $\eta$ is the limiting ratio of the expected number of edge endpoints inserted by preferential attachment to the expected total degree. The proof for the undirected process generalizes naturally to give similar results for the directed hub-authority process, and an undirected hypergraph process.

A perfect Kt-matching in a graph G is a spanning subgraph consisting of vertex-disjoint copies of Kt. A classic theorem of Hajnal and Szemerédi states that if G is a graph of order n with minimum degree δ(G) ≥ (t − 1)n/t and t|n, then G contains a perfect Kt-matching. Let G be a t-partite graph with vertex classes V1, …, Vt each of size n. We show that, for any γ > 0, if every vertex x ∈ Vi is joined to at least $\bigl ((t-1)/t + \gamma \bigr )n$ vertices of Vj for each j ≠ i, then G contains a perfect Kt-matching, provided n is large enough. Thus, we verify a conjecture of Fischer [6] asymptotically. Furthermore, we consider a generalization to hypergraphs in terms of the codegree.

We look at a model of random graphs suggested by Gilbert: given an integer $n$ and $\delta > 0$, scatter $n$ vertices independently and uniformly on a metric space, and then add edges connecting pairs of vertices of distance less than $\delta$ apart.

We consider the asymptotics when the metric space is the interval [0, 1], and $\delta = \delta(n)$ is a function of $n$, for $n \to \infty$. We prove that every upwards closed property of (ordered) graphs has at least a weak threshold in this model on this metric space. (But we do find a metric space on which some upwards closed properties do not even have weak thresholds in this model.) We also prove that every upwards closed property with a threshold much above connectivity's threshold has a strong threshold. (But we also find a sequence of upwards closed properties with lower thresholds that are strictly weak.)

A zigzag in a plane graph is a circuit of edges, such that any two, but not three, consecutive edges belong to the same face. A railroad in a plane graph is a circuit of hexagonal faces, such that any hexagon is adjacent to its neighbours on opposite edges. A graph without a railroad is called tight. We consider the zigzag and railroad structures of general 3-valent plane graph and, especially, of simple two-faced polyhedra, i.e., 3-valent 3-polytopes with only $a$-gonal and $b$-gonal faces, where $3 \leq a < b \leq 6$; the main cases are $(a,b)=(3,6), (4,6)$ and $(5,6)$ (the fullerenes).

We completely describe the zigzag structure for the case $(a,b)\,{=}\,(3,6)$. For the case $(a,b)\,{=}\,(4,6)$ we describe symmetry groups, classify all tight graphs with simple zigzags and give the upper bound 9 for the number of zigzags in general tight graphs. For the remaining case $(a,b)\,{=}\,(5,6)$ we give a construction realizing a prescribed zigzag structure.

In this paper, we present several probabilistic transforms related to classical urn models. These transforms render the dependent random variables describing the urn occupancies into independent random variables with appropriate distributions. This simplifies the analysis of a large number of problems for which a function under investigation depends on the urn occupancies. The approach used for constructing the transforms involves generating functions of combinatorial numbers characterizing the urn distributions. We also show, by using Tauberian theorems derived in this paper, that under certain simple conditions the asymptotic expressions of target functions in the transform domain and in the inverse–transform domain are identical. Therefore, asymptotic information about certain statistics can be obtained without evaluating the inverse transform.

We consider analogues of van der Waerden's theorem and Szemerédi's theorem, where arithmetic progressions are replaced by binary trees with a fixed distance between successive vertices. The proofs are based on some novel recurrence properties for Markov processes.

We prove several results from different areas of extremal combinatorics, giving complete or partial solutions to a number of open problems. These results, coming from areas such as extremal graph theory, Ramsey theory and additive combinatorics, have been collected together because in each case the relevant proofs are quite short.

Let G be a simple graph on n vertices. A conjecture of Bollobás and Eldridge [5] asserts that if then G contains any n vertex graph H with Δ(H) = k. We prove a strengthened version of this conjecture for bipartite, bounded degree H, for sufficiently large n. This is the first result on this conjecture for expander graphs of arbitrary (but bounded) degree. An important tool for the proof is a new version of the Blow-Up Lemma.

In the present work we prove the following conjecture of Erdős, Roth, Sárközy and T. Sós: Let $f$ be a polynomial of integer coefficients such that $2|f(z)$ for some integer $z$. Then, for any $k$-colouring of the integers, the equation $x+y=f(z)$ has a solution in which $x$ and $y$ have the same colour. A well-known special case of this conjecture referred to the case $f(z)=z^2$.

An r-uniform hypergraph is called an r-graph. A hypergraph is linear if every two edges intersect in at most one vertex. Given a linear r-graph H and a positive integer n, the linear Turán number exL(n,H) is the maximum number of edges in a linear r-graph G that does not contain H as a subgraph. For each ℓ ≥ 3, let Crℓ denote the r-uniform linear cycle of length ℓ, which is an r-graph with edges e1, . . ., eℓ such that, for all i ∈ [ℓ−1], |ei ∩ ei+1|=1, |eℓ ∩ e1|=1 and ei ∩ ej = ∅ for all other pairs {i,j}, i ≠ j. For all r ≥ 3 and ℓ ≥ 3, we show that there exists a positive constant c = cr,ℓ, depending only r and ℓ, such that exL(n,Crℓ) ≤ cn1+1/⌊ℓ/2⌋. This answers a question of Kostochka, Mubayi and Verstraëte [30]. For even ℓ, our result extends the result of Bondy and Simonovits [7] on the Turán numbers of even cycles to linear hypergraphs.

Using our results on linear Turán numbers, we also obtain bounds on the cycle-complete hypergraph Ramsey numbers. We show that there are positive constants a = am,r and b = bm,r, depending only on m and r, such that

\begin{equation} R(C^r_{2m}, K^r_t)\leq a \Bigl(\frac{t}{\ln t}\Bigr)^{{m}/{(m-1)}} \quad\text{and}\quad R(C^r_{2m+1}, K^r_t)\leq b t^{{m}/{(m-1)}}. \end{equation}

Given a family [Fscr ] of r-graphs, let ex(n, [Fscr ]) be the maximum number of edges in an n-vertex r-graph containing no member of [Fscr ]. Let C(r)4 denote the family of r-graphs with distinct edges A, B, C, D, such that A ∩ B = C ∩ D = Ø and A ∪ B = C ∪ D. For s1 [les ] … [les ] sr, let K(r) (s1,…,sr) be the complete r-partite r-graph with parts of sizes s1,…,sr.

Füredi conjectured over 15 years ago that ex(n,C(3)4) [les ] (n2) for sufficiently large n. We prove the weaker result

ex(n, {C(3)4, K(3)(1,2,4)}) [les ] (n2).

Generalizing a well-known conjecture for the Turán number of bipartite graphs, we conjecture that

ex(n, K(r)(s1,…,sr)) = Θ(nr−1/s),

where s = Πr−1i=1si. We prove this conjecture when s1 = … = sr−2 = 1 and

(i) sr−1 = 2, (ii) sr−1 = sr = 3, (iii)sr > (sr−1−1)!.

In cases (i) and (ii), we determine the asymptotic value of ex(n,K(r)(s1,…,sr)).

We also provide an explicit construction giving

ex(n,K(3)(2,2,3)) > (1/6−o(1))n8/3.

This improves upon the previous best lower bound of Ω(n29/11) obtained by probabilistic methods. Several related open problems are also presented.

Let the random graph Rn be drawn uniformly at random from the set of all simple planar graphs on n labelled vertices. We see that with high probability the maximum degree of Rn is Θ(ln n). We consider also the maximum size of a face and the maximum increase in the number of components on deleting a vertex. These results extend to graphs embeddable on any fixed surface.

We prove an analogue of Alon’s spectral gap conjecture for random bipartite, biregular graphs. We use the Ihara–Bass formula to connect the non-backtracking spectrum to that of the adjacency matrix, employing the moment method to show there exists a spectral gap for the non-backtracking matrix. A by-product of our main theorem is that random rectangular zero-one matrices with fixed row and column sums are full rank with high probability. Finally, we illustrate applications to community detection, coding theory, and deterministic matrix completion.

Two players share a connected graph with non-negative weights on the vertices. They alternately take the vertices (one in each turn) and collect their weights. The rule they have to obey is that the remaining part of the graph must be connected after each move. We conjecture that the first player can get at least half of the weight of any tree with an even number of vertices. We provide a strategy for the first player to get at least 1/4 of an even tree. Moreover, we confirm the conjecture for subdivided stars. The parity condition is necessary: Alice gets nothing on a three-vertex path with all the weight at the middle. We suspect a kind of general parity phenomenon, namely, that the first player can gather a substantial portion of the weight of any ‘simple enough’ graph with an even number of vertices.

We discuss the connection between the expansion of small sets in graphs, and the Schatten norms of their adjacency matrices. In conjunction with a variant of the Azuma inequality for uniformly smooth normed spaces, we deduce improved bounds on the small-set isoperimetry of Abelian Alon–Roichman random Cayley graphs.

We define a space of random edge-coloured graphs [Gscr ]n,m,κ which correspond naturally to edge κ-colourings of Gn,m. We show that there exist constants K0, K1 [les ] 21 such that, provided m [ges ] K0n log n and κ [ges ] K1n, then a random edge-coloured graph contains a multi-coloured Hamilton cycle with probability tending to 1 as the number of vertices n tends to infinity.

Using a group-theoretic approach, we derive some Erdős-Ko-Rado-type results for certain Sperner families of chains and antichains in partial orders. In particular, we establish Bollobás-type inequalities for arbitrary Sperner families of intersecting affine subspaces, and special intersecting Sperner families in generalized Boolean algebras.