Associate to a finite labeled graph G(V, E) its multiset of neighborhoods (G) = {N(υ): υ ∈ V}. We discuss the question of when a list is realizable by a graph, and to what extent G is determined by (G). The main results are: the decision problem is NP-complete; for bipartite graphs the decision problem is polynomially equivalent to Graph Isomorphism; forests G are determined up to isomorphism by (G); and if G is connected bipartite and (H) = (G), then H is completely described.

We present a method for obtaining upper bounds for the connective constant of self-avoiding walks. The method works for a large class of lattices, including all that have been studied in connection with self-avoiding walks. The bound is obtained as the largest eigenvalue of a certain matrix. Numerical application of the method has given improved bounds for all lattices studied, e.g. μ < 2.696 for the square lattice, μ < 4.278 for the triangular lattice and μ < 4.756 for the simple cubic lattice.

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.

The number, , of rooted plane binary trees of height ≤ h with n internal nodes is shown to satisfy

uniformly for δ−1(log n)−1/2 ≤ β ≤ δ(log n)1/2, where and δ is a positive constant. An asymptotic formula for is derived for h = cn, where 0 < c < 1. Bounds for are also derived for large and small heights. The methods apply to any simple family of trees, and the general asymptotic results are stated.

For T ∈ GLn (Fq), let Ωn (t, T) be the number of irreducible factors of degree less than or equal to nt in the characteristic polynomial of T. Let

and suppose T is chosen from G Ln(Fq) at random uniformly. We prove that the stochastic process ≺Zn(t)≻t∈[0, 1] converges to the standard Brownian motion process W(t), as n → ∞.

A theorem of Makarov states that the harmonic measure of a connected subset of ℝ2 is supported on a set of Hausdorff dimension one. This paper gives an analogue of this theorem for discrete harmonic measure, i.e., the hitting measure of simple random walk. It is proved that for any 1/2 < α < 1, β < α − 1/2, there is a constant k such that for any connected subset A ⊂ ℤ2 of radius n,

where HA denotes discrete harmonic measure.

Let G be a connected graph with n vertices and m edges (multiple edges allowed), and let k ≥ 2 be an integer. There is an algorithm with (optimal) running time of O(m) that finds

(i) a bipartite subgraph of G with ≥ m/2 + (n − 1)/4 edges,

(ii) a bipartite subgraph of G with ≥ m/2 + 3(n−1)/8 edges if G is triangle-free,

(iii) a k-colourable subgraph of G with ≥ m − m/k + (n−1)/k + (k − 3)/2 edges if k ≥ 3 and G is not k-colorable.

Infinite families of graphs show that each of those lower bounds on the worst-case performance are best possible (for every algorithm). Moreover, even if short cycles are excluded, the general lower bound of m − m/k cannot be replaced by m − m/k + εm for any fixed ε > 0; and it is NP-complete to decide whether a graph with m edges contains a k-colorable subgraph with more than m − m/k + εm edges, for any k ≥ 2 and ε> 0, ε < 1/k.