A graph H is called common if the sum of the number of copies of H in a graph G and the number in the complement of G is asymptotically minimized by taking G to be a random graph. Extending a conjecture of Erdős, Burr and Rosta conjectured that every graph is common. Thomason disproved both conjectures by showing that K4 is not common. It is now known that in fact the common graphs are very rare. Answering a question of Sidorenko and of Jagger, Št'ovíček and Thomason from 1996 we show that the 5-wheel is common. This provides the first example of a common graph that is not three-colourable.

In this paper we study random linear systems with $k > 3$ variables per equation over the finite field GF(2), or equivalently k-XOR-CNF formulas. In a previous paper Creignou and Daudé proved that there exists a phase transition exhibiting a sharp threshold, for the consistency (satisfiability) of such systems (formulas). The control parameter for this transition is the ratio of the number of equations to the number of variables, and the scale for which the transition occurs remains somewhat elusive. In this paper we establish, for any $k > 3$, non-trivial lower and upper estimates of the value of the control ratio for which the phase transition occurs. For $k=3$ we get 0.89 and 0.93, respectively. Moreover, we give experimental results for $k=3$ suggesting that the critical ratio is about 0.92. Our estimates are clearly close to the critical ratio.

A lattice basis bi,…,bm is called block reduced with block size β if for every β consecutive vectors bi,…,bi+β−1, the orthogonal projections of bi,…,bi+β−1 in span(bi,…,bi−1)⊥ are reduced in the sense of Hermite and Korkin–Zolotarev. Let λi denote the successive minima of lattice L, and let b1,…,bm be a basis of L that is block reduced with block size β. We prove that for i = 1,…, m

where γβ is the Hermite constant for dimension β. For block size β = 3 and odd rank m ≥ 3, we show that

where the maximum is taken over all block reduced bases of all lattices L. We present critical block reduced bases achieving this maximum. Using block reduced bases, we improve Babai's construction of a nearby lattice point. Given a block reduced basis with block size β of the lattice L, and given a point x in the span of L, a lattice point υ can be found in time βO(β) satisfying

These results also give improvements on the method of solving integer programming problems via basis reduction.

A perfect H-tiling in a graph G is a collection of vertex-disjoint copies of a graph H in G that together cover all the vertices in G. In this paper we investigate perfect H-tilings in a random graph model introduced by Bohman, Frieze and Martin [6] in which one starts with a dense graph and then adds m random edges to it. Specifically, for any fixed graph H, we determine the number of random edges required to add to an arbitrary graph of linear minimum degree in order to ensure the resulting graph contains a perfect H-tiling with high probability. Our proof utilizes Szemerédi's Regularity Lemma [29] as well as a special case of a result of Komlós [18] concerning almost perfect H-tilings in dense graphs.

Let ${\cal H}$ be a 3-uniform hypergraph on an $n$-element vertex set $V$. The neighbourhood of $a,b\in V$ is $N(ab):= \{x: abx\in E({\cal H})\} $. Such a 3-graph has independent neighbourhoods if no $N(ab)$ contains an edge of ${\cal H}$. This is equivalent to ${\cal H}$ not containing a copy of $\mathbb{F} :=\{ abx$, $aby$, $abz$, $xyz\}$.

In this paper we prove an analogue of the Andrásfai–Erdös–Sós theorem for triangle-free graphs with minimum degree exceeding $2n/5$. It is shown that any $\mathbb{F}$-free 3-graph with minimum degree exceeding $(\frac{4}{9}-\frac{1}{125})\binom{n}{2}$ is bipartite, (for $n> n_0$), i.e., the vertices of ${\cal H}$ can be split into two parts so that every triple meets both parts.

This is, in fact, a Turán-type result. It solves a problem of Erdös and T.Sós, and answers a question of Mubayi and Rödl that

\[\ex(n,\mathbb{F}_{3,2})=\max\limits_{\alpha}(n-\alpha)\left({\alpha\atop2}\right)\].

Here the right-hand side is $\frac{4}{9}\binom{n}{3}+O(n^2)$. Moreover $e({\cal H})={\rm ex}(n,\mathbb{F})$ is possible only if $V({\cal H})$ can be partitioned into two sets $A$ and $B$ so that each triple of ${\cal H}$ intersects $A$ in exactly two vertices and $B$ in one.

The study of asymptotics of random permutations was initiated by Erdős and Turáan, in a series of papers from 1965 to 1968, and has been much studied since. Recent developments in permutation group theory make it reasonable to ask questions with a more group-theoretic flavour. Two examples considered here are membership in a proper transitive subgroup, and the intersection of a subgroup with a random conjugate. These both arise from other topics (quasigroups, bases for permutation groups, and design constructions).

Let Per f(n) denote the set of all perfect graphs on n vertices and let Berge(n) denote the set of all Berge graphs on n vertices. The strong perfect graph conjecture states that Per f(n) = Berge(n) for all n. In this paper we prove that this conjecture is at least asymptotically true, i.e. we show that

By the complexity of a graph we mean the minimum number of union and intersection operations needed to obtain the whole set of its edges starting from stars. This measure of graphs is related to the circuit complexity of boolean functions.

We prove some lower bounds on the complexity of explicitly given graphs. This yields some new lower bounds for boolean functions, as well as new proofs of some known lower bounds in the graph-theoretic framework. We also formulate several combinatorial problems whose solution would have intriguing consequences in computational complexity.

We give a quantitative proof that, for sufficiently large $N$, every subset of $[N]^2$ of size at least $\delta N^2$ contains a square, i.e., four points with coordinates $\{(a,b),(a+d,b),(a,b+d),(a+d,b+d)\}$.

Let ⊂ 2[n] be a family of subsets of {1, 2,. . ., n}. For any poset H, we say is H-free if does not contain any subposet isomorphic to H. Katona and others have investigated the behaviour of La(n, H), which denotes the maximum size of H-free families ⊂ 2[n]. Here we use a new approach, which is to apply methods from extremal graph theory and probability theory to identify new classes of posets H, for which La(n, H) can be determined asymptotically as n → ∞ for various posets H, including two-end-forks, up-down trees, and cycles C4k on two levels.

In this paper, we give sharp upper bounds on the maximum number of edges in very unbalanced bipartite graphs not containing any cycle of length 6. To prove this, we estimate roughly the sum of the sizes of the hyperedges in triangle-free multi-hypergraphs.

A family of subsets of {1, . . ., n} is called a j-junta if there exists J ⊆ {1, . . ., n}, with |J| = j, such that the membership of a set S in depends only on S ∩ J.

In this paper we provide a simple description of intersecting families of sets. Let n and k be positive integers with k < n/2, and let be a family of pairwise intersecting subsets of {1, . . ., n}, all of size k. We show that such a family is essentially contained in a j-junta , where j does not depend on n but only on the ratio k/n and on the interpretation of ‘essentially’.

When k = o(n) we prove that every intersecting family of k-sets is almost contained in a dictatorship, a 1-junta (which by the Erdős–Ko–Rado theorem is a maximal intersecting family): for any such intersecting family there exists an element i ∈ {1, . . ., n} such that the number of sets in that do not contain i is of order (which is approximately times the size of a maximal intersecting family).

Our methods combine traditional combinatorics with results stemming from the theory of Boolean functions and discrete Fourier analysis.

We are given a graph G with n vertices, where a random subset of k vertices has been made into a clique, and the remaining edges are chosen independently with probability $\frac12$. This random graph model is denoted $G(n,\frac12,k)$. The hidden clique problem is to design an algorithm that finds the k-clique in polynomial time with high probability. An algorithm due to Alon, Krivelevich and Sudakov [3] uses spectral techniques to find the hidden clique with high probability when $k = c \sqrt{n}$ for a sufficiently large constant c > 0. Recently, an algorithm that solves the same problem was proposed by Feige and Ron [12]. It has the advantages of being simpler and more intuitive, and of an improved running time of O(n2). However, the analysis in [12] gives a success probability of only 2/3. In this paper we present a new algorithm for finding hidden cliques that both runs in time O(n2) (that is, linear in the size of the input) and has a failure probability that tends to 0 as n tends to ∞. We develop this algorithm in the more general setting where the clique is replaced by a dense random graph.

We introduce the notion of a stable instance for a discrete optimization problem, and argue that in many practical situations only sufficiently stable instances are of interest. The question then arises whether stable instances of NP-hard problems are easier to solve, and in particular, whether there exist algorithms that solve in polynomial time all sufficiently stable instances of some NP-hard problem. The paper focuses on the Max-Cut problem, for which we show that this is indeed the case.

For a graph G, let f(G) denote the maximum number of edges in a cut of G. For an integer m and for a fixed graph H, let $f(m,H)$ denote the minimum possible cardinality of $f(G)$, as G ranges over all graphs on m edges that contain no copy of H. In this paper we study this function for various graphs H. In particular we show that for any graph H obtained by connecting a single vertex to all vertices of a fixed nontrivial forest, there is a $c(H) >0$ such that $f(m,H) \geq \frac{m}{2} + c(H) m^{4/5}$, and that this is tight up to the value of $c(H)$. We also prove that for any even cycle $C_{2k}$ there is a $c(k)>0$ such that $f(m,C_{2k}) \geq \frac{m}{2} + c(k) m^{(2k+1)/(2k+2)}$, and that this is tight, up to the value of $c(k)$, for $2k\in \{4,6,10\}$. The proofs combine combinatorial, probabilistic and spectral techniques.

The square lattice site percolation model critical probability is shown to be at most .679492, improving the best previous mathematically rigorous upper bound. This bound is derived by extending the substitution method to apply to site percolation models.

We investigate the Laplacian eigenvalues of sparse random graphs Gnp. We show that in the case that the expected degree d = (n-1)p is bounded, the spectral gap of the normalized Laplacian is o(1). Nonetheless, w.h.p. G = Gnp has a large subgraph core(G) such that the spectral gap of is as large as 1-O (d−1/2). We derive similar results regarding the spectrum of the combinatorial Laplacian L(Gnp). The present paper complements the work of Chung, Lu and Vu [8] on the Laplacian spectra of random graphs with given expected degree sequences. Applied to Gnp, their results imply that in the ‘dense’ case d ≥ ln2n the spectral gap of is 1-O (d−1/2) w.h.p.

Let $C$ be a code of length $n$ over an alphabet of $q$ letters. A codeword $y$ is called a descendant of a set of $t$ codewords $\{x^1,\dots,x^t\}$ if $y_i \in \{x^1_i,\dots,x^t_i\}$ for all $i=1,\dots,n$. A code is said to have the Identifiable Parent Property of order $t$ if, for any word of length $n$ that is a descendant of at most $t$ codewords (parents), it is possible to identify at least one of them. Let $f_t(n,q)$ be the maximum possible cardinality of such a code. We prove that for any $t,n,q$, $(c_1(t)q)^{\frac{n}{s(t)}} < f_t(n,q) < c_2(t)q^{\lceil{\frac{n}{s(t)}}\rceil}$ where $s(t) = \lfloor(\frac{t}{2}+1)^2 \rfloor -1$ and $c_1(t),c_2(t)$ are some functions of $t$. We also show some bounds and constructions for $f_3(5,q)$, $f_3(6,q)$, and $f_t(n,q)$ when $n < s(t)$.

In this article we introduce combinatorial multicolour discrepancies and generalize several classical results from $2$-colour discrepancy theory to $c$ colours ($c \geq 2$). We give a recursive method that constructs $c$-colourings from approximations of $2$-colour discrepancies. This method works for a large class of theorems, such as the ‘six standard deviations’ theorem of Spencer (1985), the Beck–Fiala (1981) theorem, the results of Matoušek, Wernisch and Welzl (1994) and Matoušek (1995) for bounded VC-dimension, and Matoušek and Spencer's (1996) upper bound for the arithmetic progressions. In particular, the $c$-colour discrepancy of an arbitrary hypergraph ($n$ vertices, $m$ hyperedges) is \[ \OO\Bigl(\sqrt{\tfrac n c\,\log m}\Bigr). \] If $m = \OO(n)$, then this bound improves to \[ \OO\Bigl(\sqrt{\tfrac n c\,\log c}\Bigr). \]

On the other hand there are examples showing that discrepancy in $c$ colours can not be bounded in terms of two-colour discrepancies in general, even if $c$ is a power of 2. For the linear discrepancy version of the Beck–Fiala theorem, the recursive approach also fails.

Here we extend the method of floating colours via tensor products of matrices to multicolourings, and prove multicolour versions of the Beck–Fiala theorem and the Bárány–Grinberg theorem. Using properties of the tensor product we derive a lower bound for the $c$-colour discrepancy of general hypergraphs. For the hypergraph of arithmetic progressions in $\{1, \ldots, n\}$ this yields a lower bound of $\frac{1}{25 \sqrt c} \sqrt[4]{n}$ for the discrepancy in $c$ colours. The recursive method shows an upper bound of $\OO(c^{-0.16} \sqrt[4]{n})$

We prove χ′s(G) ≤ 1.93 Δ(G)2 for graphs of sufficiently large maximum degree where χ′s(G) is the strong chromatic index of G. This improves an old bound of Molloy and Reed. As a by-product, we present a Talagrand-type inequality where we are allowed to exclude unlikely bad outcomes that would otherwise render the inequality unusable.