We derive improved isoperimetric inequalities for discrete product measures on the n-dimensional cube. As a consequence, a general theorem on the threshold behaviour of monotone properties is obtained. This is then applied to coding theory when we study the probability of error after decoding.

Li, Nikiforov and Schelp [13] conjectured that any 2-edge coloured graph G with order n and minimum degree δ(G) > 3n/4 contains a monochromatic cycle of length ℓ, for all ℓ ∈ [4, ⌈n/2⌉]. We prove this conjecture for sufficiently large n and also find all 2-edge coloured graphs with δ(G)=3n/4 that do not contain all such cycles. Finally, we show that, for all δ>0 and n>n0(δ), if G is a 2-edge coloured graph of order n with δ(G) ≥ 3n/4, then one colour class either contains a monochromatic cycle of length at least (2/3+δ/2)n, or contains monochromatic cycles of all lengths ℓ ∈ [3, (2/3−δ)n].

We give a characterization for isoperimetric invariants, including the Cheeger constant and the isoperimetric number of a graph. This leads to an isoperimetric inequality for the Cartesian products of graphs.

We derive new results for the performance of a simple greedy algorithm for finding large independent sets and matchings in constant-degree regular graphs. We show that for r-regular graphs with n nodes and girth at least g, the algorithm finds an independent set of expected cardinality where f(r) is a function which we explicitly compute. A similar result is established for matchings. Our results imply improved bounds for the size of the largest independent set in these graphs, and provide the first results of this type for matchings. As an implication we show that the greedy algorithm returns a nearly perfect matching when both the degree r and girth g are large. Furthermore, we show that the cardinality of independent sets and matchings produced by the greedy algorithm in arbitrary bounded-degree graphs is concentrated around the mean. Finally, we analyse the performance of the greedy algorithm for the case of random i.i.d. weighted independent sets and matchings, and obtain a remarkably simple expression for the limiting expected values produced by the algorithm. In fact, all the other results are obtained as straightforward corollaries from the results for the weighted case.

Consider an electrical network on n nodes with resistors rij between nodes i and j. Let Rij denote the effective resistance between the nodes. Then Foster's Theorem [5] asserts that

where i ∼ j denotes i and j are connected by a finite rij. In [10] this theorem is proved by making use of random walks. The classical connection between electrical networks and reversible random walks implies a corresponding statement for reversible Markov chains. In this paper we prove an elementary identity for ergodic Markov chains, and show that this yields Foster's theorem when the chain is time-reversible.

We also prove a generalization of a resistive inverse identity. This identity was known for resistive networks, but we prove a more general identity for ergodic Markov chains. We show that time-reversibility, once again, yields the known identity. Among other results, this identity also yields an alternative characterization of reversibility of Markov chains (see Remarks 1 and 2 below). This characterization, when interpreted in terms of electrical currents, implies the reciprocity theorem in single-source resistive networks, thus allowing us to establish the equivalence of reversibility in Markov chains and reciprocity in electrical networks.

The Ramsey number, , of a graph G is the minimum integer N such that, in every 2-colouring of the edges of the complete graph on N vertices, there is a monochromatic copy of G. In 1975, Burr and Erdős posed a problem on Ramsey numbers of d-degenerate graphs, i.e., graphs in which every subgraph has a vertex of degree at most d. They conjectured that for every d there exists a constant c(d) such that for any d-degenerate graph G of order n.

In this paper we prove that for each such G. In fact, we show that, for every , sufficiently large n, and any graph H of order , either H or its complement contains a (d,n)-common graph, that is, a graph in which every set of d vertices has at least n common neighbours. It is easy to see that any (d,n)-common graph contains every d-degenerate graph G of order n. We further show that, for every constant C, there is an n and a graph H of order such that neither H nor its complement contains a -common graph.

Given a family of r-uniform hypergraphs ${\cal F}$ (or r-graphs for brevity), the Turán number ex(n,${\cal F})$ of ${\cal F}$ is the maximum number of edges in an r-graph on n vertices that does not contain any member of ${\cal F}$. A pair {u,v} is covered in a hypergraph G if some edge of G contains {u, v}. Given an r-graph F and a positive integer p ⩾ n(F), where n(F) denotes the number of vertices in F, let HFp denote the r-graph obtained as follows. Label the vertices of F as v1,. . .,vn(F). Add new vertices vn(F)+1,. . .,vp. For each pair of vertices vi, vj not covered in F, add a set Bi,j of r − 2 new vertices and the edge {vi, vj} ∪ Bi,j, where the Bi,j are pairwise disjoint over all such pairs {i, j}. We call HFp the expanded p-clique with an embedded F. For a relatively large family of F, we show that for all sufficiently large n, ex(n,HFp) = |Tr(n, p − 1)|, where Tr(n, p − 1) is the balanced complete (p − 1)-partite r-graph on n vertices. We also establish structural stability of near-extremal graphs. Our results generalize or strengthen several earlier results and provide a class of hypergraphs for which the Turán number is exactly determined (for large n).

We study the complexity of computing the coefficients of three classical polynomials, namely the chromatic, flow and reliability polynomials of a graph. Each of these is a specialization of the Tutte polynomial Σtijxiyj. It is shown that, unless NP = RP, many of the relevant coefficients do not even have good randomized approximation schemes. We consider the quasi-order induced by approximation reducibility and highlight the pivotal position of the coefficient t10 = t01, otherwise known as the beta invariant.

Our nonapproximability results are obtained by showing that various decision problems based on the coefficients are NP-hard. A study of such predicates shows a significant difference between the case of graphs, where, by Robertson–Seymour theory, they are computable in polynomial time, and the case of matrices over finite fields, where they are shown to be NP-hard.

A dominating set $\cal D$ of a graph $G$ is a subset of $V(G)$ such that, for every vertex $v\in V(G)$, either in $v\in {\cal D}$ or there exists a vertex $u \in {\cal D}$ that is adjacent to $v$. We are interested in finding dominating sets of small cardinality. A dominating set $\cal I$ of a graph $G$ is said to be independent if no two vertices of ${\cal I}$ are connected by an edge of $G$. The size of a smallest independent dominating set of a graph $G$ is the independent domination number of $G$. In this paper we present upper bounds on the independent domination number of random regular graphs. This is achieved by analysing the performance of a randomized greedy algorithm on random regular graphs using differential equations.

We study the conflict-free chromatic number χCF of graphs from extremal and probabilistic points of view. We resolve a question of Pach and Tardos about the maximum conflict-free chromatic number an n-vertex graph can have. Our construction is randomized. In relation to this we study the evolution of the conflict-free chromatic number of the Erdős–Rényi random graph G(n,p) and give the asymptotics for p = ω(1/n). We also show that for p ≥ 1/2 the conflict-free chromatic number differs from the domination number by at most 3.

Let it(G) be the number of independent sets of size t in a graph G. Engbers and Galvin asked how large it(G) could be in graphs with minimum degree at least δ. They further conjectured that when n ⩾ 2δ and t ⩾ 3, it(G) is maximized by the complete bipartite graph Kδ,n−δ. This conjecture has recently drawn the attention of many researchers. In this short note, we prove this conjecture.

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.

R. H. Schelp conjectured that if G is a graph with |V(G)| = R(Pn, Pn) such that δ(G) > , then in every 2-colouring of the edges of G there is a monochromatic Pn. In other words, the Ramsey number of a path does not change if the graph to be coloured is not complete but has large minimum degree.

Here we prove Ramsey-type results that imply the conjecture in a weakened form, first replacing the path by a matching, showing that the star-matching–matching Ramsey number satisfying R(Sn, nK2, nK2) = 3n − 1. This extends R(nK2, nK2) = 3n − 1, an old result of Cockayne and Lorimer. Then we extend this further from matchings to connected matchings, and outline how this implies Schelp's conjecture in an asymptotic sense through a standard application of the Regularity Lemma.

It is sad that we are unable to hear Dick Schelp's reaction to our work generated by his conjecture.

A graph may be regarded as an electrical network in which each edge has unit resistance. We obtain explicit formulae for the effective resistance of the network when a current enters at one vertex and leaves at another in the distance-regular case. A well-known link with random walks motivates a conjecture about the maximum effective resistance. Arguments are given that point to the truth of the conjecture for all known distance-regular graphs.

A forest ℱ(n, M) chosen uniformly from the family of all labelled unrooted forests with n vertices and M edges is studied. We show that, like the Érdős-Rényi random graph G(n, M), the random forest exhibits three modes of asymptotic behaviour: subcritical, nearcritical and supercritical, with the phase transition at the point M = n/2. For each of the phases, we determine the limit distribution of the size of the k-th largest component of ℱ(n, M). The similarity to the random graph is far from being complete. For instance, in the supercritical phase, the giant tree in ℱ(n, M) grows roughly two times slower than the largest component of G(n, M) and the second largest tree in ℱ(n, M) is of the order n⅔ for every M = n/2 +s, provided that s3n−2 → ∞ and s = o(n), while its counterpart in G(n, M) is of the order n2s−2 log(s3n−2) ≪ n⅔.

We model a problem about networks built from wireless devices using identifying and locating–dominating codes in unit disk graphs. It is known that minimizing the size of an identifying code is -complete even for bipartite graphs. First, we improve this result by showing that the problem remains -complete for bipartite planar unit disk graphs. Then, we address the question of the existence of an identifying code for random unit disk graphs. We derive the probability that there exists an identifying code as a function of the radius of the disks, and we find that for all interesting ranges of r this probability is bounded away from one. The results obtained are in sharp contrast to those concerning random graphs in the Erdős–Rényi model. Another well-studied class of codes is that of locating–dominating codes, which are less demanding than identifying codes. A locating–dominating code always exists, but minimizing its size is still -complete in general. We extend this result to our setting by showing that this question remains -complete for arbitrary planar unit disk graphs. Finally, we study the minimum size of such a code in random unit disk graphs, and we prove that with probability tending to one, it is of size (n/r)2/3+o(1) if r ≤ /2−ϵ is chosen such that nr2 → ∞, and of size n1+o(1) if nr2 ≪ lnn.

For k-uniform hypergraphs F and H and an integer r, let cr,F(H) denote the number of r-colourings of the set of hyperedges of H with no monochromatic copy of F, and let , where the maximum runs over all k-uniform hypergraphs on n vertices. Moreover, let ex(n,F) be the usual extremal or Turán function, i.e., the maximum number of hyperedges of an n-vertex k-uniform hypergraph which contains no copy of F.

For complete graphs F = Kℓ and r = 2, Erdős and Rothschild conjectured that c2,Kℓ(n) = 2ex(n,Kℓ). This conjecture was proved by Yuster for ℓ = 3 and by Alon, Balogh, Keevash and Sudakov for arbitrary ℓ. In this paper, we consider the question for hypergraphs and show that, in the special case when F is the Fano plane and r = 2 or 3, then cr,F(n) = rex(n,F), while cr,F(n) ≫ rex(n,F) for r ≥ 4.

We provide a framework for online conflict-free colouring of any hypergraph. We introduce the notion of a degenerate hypergraph, which characterizes hypergraphs that arise in geometry. We use our framework to obtain an efficient randomized online algorithm for conflict-free colouring of any k-degenerate hypergraph with n vertices. Our algorithm uses O(k log n) colours with high probability and this bound is asymptotically optimal. Moreover, our algorithm uses O(k log k log n) random bits with high probability. We introduce algorithms that are allowed to perform a few recolourings of already coloured points. We provide deterministic online conflict-free colouring algorithms for points on the line with respect to intervals and for points on the plane with respect to half-planes (or unit disks) that use O(log n) colours and perform a total of at most O(n) recolourings.

We define ${\mathcal B}_n$ to be the set of $n$-tuples of the form $(a_0, {\ldots}\,, a_{n-1})$ where $a_j = \pm 1$. If $A \in {\mathcal B}_n$, then we call $A$ a binary sequence and define the autocorrelations of $A$ by $c_k := \sum_{j=0}^{n-k-1} a_j a_{j+k}$ for $0 \leq k \leq n-1$. The problem of finding binary sequences with autocorrelations ‘near zero’ has arisen in communications engineering and is also relevant to conjectures of Littlewood and Erdős on ‘flat’ polynomials with $\pm 1$ coefficients. Following Turyn, we define \[ b(n) := \min_{A \in {\mathcal B}_n} \max_{1 \leq k \leq n-1} |c_k|.\] The purpose of this article is to show that, using some known techniques from discrete probability, we can improve upon the best upper bound on $b(n)$ appearing in the previous literature, and we can obtain both asymptotic and exact expressions for the expected value of $c_k^m$ if the $a_j$ are independent $\pm 1$ random variables with mean 0. We also include some brief heuristic remarks in support of the unproved conjecture that $b(n) = O(\sqrt{n})$.

The aim of this paper is to prove a Turán-type theorem for random graphs. For $\gamma >0$ and graphs $G$ and $H$, write $G\to_\gamma H$ if any $\gamma$-proportion of the edges of $G$ spans at least one copy of $H$ in $G$. We show that for every graph $H$ and every fixed real $\delta>0$, almost every graph $G$ in the binomial random graph model $\cG(n,q)$, with $q=q(n)\gg((\log n)^4/n)^{1/d(H)}$, satisfies $G\to_{(\chi(H)-2)/(\chi(H)-1)+\delta}H$, where as usual $\chi(H)$ denotes the chromatic number of $H$ and $d(H)$ is the ‘degeneracy number’ of $H$.

Since $K_l$, the complete graph on $l$ vertices, is $l$-chromatic and $(l-1)$-degenerate, we infer that for every $l\geq2$ and every fixed real $\delta>0$, almost every graph $G$ in the binomial random graph model $\cG(n,q)$, with $q=q(n)\gg((\log n)^4/n)^{1/(l-1)}$, satisfies $G\to_{(l-2)/(l-1)+\delta}K_l$.