Ramsey numbers for matroids, which mimic properties of Ramsey numbers for graphs, have been denned as follows. Let k and l be positive integers. Then n(k, l) is the least positive integer n such that every connected matroid with n elements contains either a circuit with at least k elements or a cocircuit with at least l elements. We determine the largest known value of these numbers in the sense of maximizing both k and l. We also find extremal matroids with small circuits and cocircuits. Results on matroid connectivity, geometry, and extremal matroid theory are used here.

The conditional independences within a system of four discrete random variables are studied simultaneously. The problem of where independences can occur at the same time, called the problem of probabilistic representability, is attacked by an analysis of cones of polymatroids. New results on the cone of all polymatroids satisfying Ingleton inequalities imply a substantial reduction of the problem and an explicit description of the remaining open cases.†

Numerous new properties of stochastic conditional independence are introduced. They are aimed, together with two surprisingly trivial examples, at a further reduction of the problem of probabilistic representability for four-element sets, i.e. of the problem which conditional independences within a system of four random variables can occur simultaneously. Proofs are based on fundamental properties of conditional independence and, in the discrete case, on the use of I-divergence and algebraic manipulations with marginal probabilities. A duality question is answered in the negative.

Suppose X1, X2,… is a sequence of independent and identically distributed random elements whose values are taken in a finite set S of size |S| ≥ 2 with probability distribution ℙ(X = s) = p(s) > 0 for s ∈ S. Pevzner has conjectured that for every probability distribution ℙ there exists an N > 0 such that for every word A with letters in S whose length is at least N, there exists a second word B of the same length as A, such that the event that B appears before A in the sequence X1, X2,… has greater probability than that of A appearing before B. In this paper it is shown that a distribution ℙ satisfies Pevzner's conclusion if and only if the maximum value of ℙ, p, and the secondary maximum c satisfy the inequality . For |S| = 2 or |S| = 3, the inequality is true and the conjecture holds. If , then the conjecture is true when A is not allowed to consist of pure repetitions of that unique element for which the distribution takes on its mode.

This paper gives precise isoperimetric inequalities for infinite graphs on which a group acts with finite quotient. Decay estimates are obtained for the iterated kernels of the associated random walks.

Let G be a minimally n-edge-connected finite simple graph with vertex number |G| ≥ 2n + 2 + [3/n] and let n ≥ 3 be odd. It is proved that the number of vertices of degree n in G is at least ((n − 1 − ∈n)/(2n + 1))|G| + 2 + 2∈n, where ∈n = (3n + 3)/(2n2 − 3n − 3), and that for every n ≡ 3 (mod 4) this lower bound is attained by infinitely many minimally n-edge-connected finite simple graphs.

This paper presents a constructive proof that for any planar digraph G on p vertices, there exists a subset S of the transitive closure of G such that the number of arcs in S is less than or equal to the number of arcs in G, and such that the diameter of G∪S is O(α(p, p)(log p)2). Here the diameter refers to the maximum distance from a vertex υ to a vertex w where (υ, w) is from the transitive closure of G – which is also the transitive closure of G ∪ S. This result provides support for the author's previous conjecture that such a set S achieving a diameter polylogarithmic in the number of vertices exists for any digraph. The result also adresses an open question of Chazelle, who did some related work on trees, and suggested the generalization to the planar cases.