Tutte proved that if e is an element of a 3-connected matroid M such that neither M\e nor M/e is 3-connected, then e is in a 3-circuit or a 3-cocircuit. In this paper, we prove a broad generalization of this result. Among the consequences of this generalization are that if X is an (n − 1)-element subset of an n-connected matroid M such that neither M\X nor M/X is connected, then, provided |E(M)| ≥ 2(n − 1)≥ 4, X is in both an n-element circuit and an n-element cocircuit. When n = 3, we describe the structure of M more closely using Δ − Y exchanges. Several related results are proved and we also show that, for all fields F other than GF(2), the set of excluded minors for F-representability is closed under both Δ − Y and Y − Δ exchanges.

The perceptron learning algorithm quite naturally yields an algorithm for finding a linearly separable boolean function consistent with a sample of such a function. Using the idea of a specifying sample, we give a simple proof that, in general, this algorithm is not efficient.

A graph G is Ramsey size linear if there is a constant C such that for any graph H with n edges and no isolated vertices, the Ramsey number r(G, H) ≤ Cn. It will be shown that any graph G with p vertices and q ≥ 2p − 2 edges is not Ramsey size linear, and this bound is sharp. Also, if G is connected and q ≤ p + 1, then G is Ramsey size linear, and this bound is sharp also. Special classes of graphs will be shown to be Ramsey size linear, and bounds on the Ramsey numbers will be determined.

For any positive integer k and ε > 0, there exist nk,ε, ck, e > 0 with the following property. Given any system of n > nk,ε points in the plane with minimal distance at least 1 and any t1, t2…, tk ≥ 1, the number of those pairs of points whose distance is between ti and for some 1 ≤ i ≤ k, is at most (n2/2) (1 − 1/(k+1)+ε). This bound is asymptotically tight.

To partition the edges of a chordal graph on n vertices into cliques may require as many as n2/6 cliques; there is an example requiring this many, which is also a threshold graph and a split graph. It is unknown whether this many cliques will always suffice. We are able to show that (1 − c)n2/4 cliques will suffice for some c > 0.

A graph G is called n-minimizable if it can be reduced, by deleting a set of its edges, to a minimally n-connected graph. It is shown that, if n-connected graphs G and H differ only by finitely many vertices and edges, then G is n-minimizable if and only if H is n-minimizable (Theorem 4.12). In the main result, conditions are given that a tree decomposition of an n-connected graph G must satisfy in order to guarantee that the n-minimizability of each of the members of this decomposition implies the n-minimizability of the graph G (Theorem 6.5).

Many of the classical results of Ramsey Theory, including those of Hilbert, Schur, and van der Waerden, are naturally stated as instances of the following problem: given a u × ν matrix A with rational entries, is it true, that whenever the set ℕ of positive integers is finitely coloured, there must exist some x∈ℕν such that all entries of Ax are the same colour? While the theorems cited are all consequences of Rado's theorem, the general problem had remained open. We provide here several solutions for the alternate problem, which asks that x∈ℕν. Based on this, we solve the general problem, giving various equivalent characterizations.

In this paper we consider the following problem, given a graph H, what is the structure of a typical, i.e. random, H-free graph? We completely solve this problem for all graphs H containing a critical vertex. While this result subsumes a sequence of known results, its short proof is self contained.

The main result of this paper gives a structure of a triangle-free graph of order n with minimal degree greater than 10n/29. This extends results given by Andrásfai et al. [1] and Häggkvist [6].

This is a survey of a number of recent papers dealing with graphs from a geometric perspective. The main theme of these studies is the relationship between graph properties that are local in nature, and global graph parameters. Connections with the theory of distributed computing are pointed out and many open problems are presented.

We prove that the probability i(n, k) that a random permutation of an n element set has an invariant subset of precisely k elements decreases as a power of k, for k ≤ n/2. Using this fact, we prove that the fraction of elements of Sn belong to transitive subgroups other than Sn or An tends to 0 when n → ∞, as conjectured by Cameron. Finally, we show that for every ∈ > 0 there exists a constant C such that C elements of the symmetric group Sn, chosen randomly and independently, generate invariably Sn with probability at least 1 − ∈. This confirms a conjecture of McKay.

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.

Two natural classes of polymatroids can be associated with hypergraphs: the so-called Boolean and hypergraphic polymatroids. Boolean polymatroids carry virtually all the structure of hypergraphs; hypergraphic polymatroids generalize graphic matroids. This paper considers algorithmic problems associated with recognizing members of these classes. Let k be a fixed positive integer and assume that the k-polymatroid ρ is presented via a rank oracle. We present an algorithm that determines in polynomial time whether ρ is Boolean, and if it is, finds the hypergraph. We also give an algorithm that decides in polynomial time whether ρ is the hypergraphic polymatroid associated with a given hypergraph. Other structure-theoretic results are also given.