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.

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).

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.

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.

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].

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.

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 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$.

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 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})$.

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 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.

We consider random graphs with a fixed degree sequence. Molloy and Reed [11, 12] studied how the size of the giant component changes according to degree conditions. They showed that there is a phase transition and investigated the order of components before and after the critical phase. In this paper we study more closely the order of components at the critical phase, using singularity analysis of a generating function for a branching process which models the random graph with a given degree sequence.

The famous Erdős–Gallai theorem on the Turán number of paths states that every graph with n vertices and m edges contains a path with at least (2m)/n edges. In this note, we first establish a simple but novel extension of the Erdős–Gallai theorem by proving that every graph G contains a path with at least

$${{(s + 1){N_{s + 1}}(G)} \over {{N_s}(G)}} + s - 1$$

The game colouring number gcol(G) of a graph G is the least k such that, if two players take turns choosing the vertices of a graph, then either of them can ensure that every vertex has fewer than k neighbours chosen before it, regardless of what choices the other player makes. Clearly gcol(G) ≤ Δ(G)+1. Sauer and Spencer [20] proved that if two graphs G1 and G2 on n vertices satisfy 2Δ(G1)Δ(G2) < n then they pack, i.e., there is an embedding of G1 into the complement of G2. We improve this by showing that if (gcol(G1)−1)Δ(G2)+(gcol(G2)−1)Δ(G1) < n then G1 and G2 pack. To our knowledge this is the first application of colouring games to a non-game problem.

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.

For every integer N, we explicitly construct a subset of residues mod N of size(log N)o(1) which is nearly uniformly distributed in every arithmetic progression modulo N.

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$.

Let G be a string graph (an intersection graph of continuous arcs in the plane) with m edges. Fox and Pach proved that G has a separator consisting of $O(m^{3/4}\sqrt{\log m})$ vertices, and they conjectured that the bound of $O(\sqrt m)$ actually holds. We obtain separators with $O(\sqrt m \,\log m)$ vertices.