A cocircuit C* in a matroid M is said to be non-separating if and only if M[setmn ]C*, the deletion of C* from M, is connected. A vertex-triad in a matroid is a three-element non-separating cocircuit. Non-separating cocircuits in binary matroids correspond to vertices in graphs. Let C be a circuit of a 3-connected binary matroid M such that [mid ]E(M)[mid ][ges ]4 and, for all elements x of C, the deletion of x from M is not 3-connected. We prove that C meets at least two vertex-triads of M. This gives direct binary matroid generalizations of certain graph results of Halin, Lemos, and Mader. For binary matroids, it also generalizes a result of Oxley. We also prove that a minimally 3-connected binary matroid M which has at least four elements has at least ½r*(M)+1 vertex-triads, where r*(M) is the corank of the matroid M. An immediate consequence of this result is the following result of Halin: a minimally 3-connected graph with n vertices has at least 2n+6/5 vertices of degree three. We also generalize Tutte's Triangle Lemma for general matroids.

We show distributional results for the length of the longest matching consecutive subsequence between two independent sequences A1, A2, …, Am and B1, B2, …, Bn whose letters are taken from a finite alphabet. We assume that A1, A2, … are i.i.d. with distribution μ and B1, B2, … are i.i.d. with distribution ν. It is known that if μ and v are not too different, the Chen–Stein method for Poisson approximation can be used to establish distributional results. We extend these results beyond the region where the Chen–Stein method was previously successful. We use a combination of ‘matching by patterns’ results obtained by Arratia and Waterman [1], and the Chen–Stein method to show that the Poisson approximation can be extended. Our method explains how the matching is achieved. This provides an explanation for the formulas in Arratia and Waterman [1] and thus answers one of the questions posed in comment F19 in Aldous [2]. Furthermore, in the case where the alphabet consists of only two letters, the phase transition observed by Arratia and Waterman [1] for the strong law of large numbers extends to the distributional result. We conjecture that this phase transition on the distributional level holds for any finite alphabet.

A rational polyhedron$P\subseteq {\mathbb{R^n}}$ is a finite union of simplexes in ${\mathbb{R^n}}$ with rational vertices. P is said to be $\mathbb Z$-homeomorphic to the rational polyhedron $Q\subseteq {\mathbb{R^{\it m}}}$ if there is a piecewise linear homeomorphism η of P onto Q such that each linear piece of η and η−1 has integer coefficients. When n=m, $\mathbb Z$-homeomorphism amounts to continuous $\mathcal{G}_n$-equidissectability, where $\mathcal{G}_n=GL(n,\mathbb Z) \ltimes \mathbb Z^{n}$ is the affine group over the integers, i.e., the group of all affinities on $\mathbb{R^{n}}$ that leave the lattice $\mathbb Z^{n}$ invariant. $\mathcal{G}_n$ yields a geometry on the set of rational polyhedra. For each d=0,1,2,. . ., we define a rational measure λd on the set of rational polyhedra, and show that any two $\mathbb Z$-homeomorphic rational polyhedra $$P\subseteq {\mathbb{R^n}}$$ and $Q\subseteq {\mathbb{R^{\it m}}}$ satisfy $\lambda_d(P)=\lambda_d(Q)$. $\lambda_n(P)$ coincides with the n-dimensional Lebesgue measure of P. If 0 ≤ dim P=d < n then λd(P)>0. For rational d-simplexes T lying in the same d-dimensional affine subspace of ${\mathbb{R^{\it n}}, $\lambda_d(T)$$ is proportional to the d-dimensional Hausdorff measure of T. We characterize λd among all unimodular invariant valuations.

It has been conjectured by Alspach [2] that given integers n and m1, …, mt with 3 [les ] mi [les ] n and [sum ]ti=1mi = (n2) (n odd) or [sum ]ti=1mi = (n2) − n/2 (n even), then one can pack Kn (n odd) or Kn minus a 1-factor (n even) with cycles of lengths m1, …, mt. In this paper we show that if the cycle lengths mi are bounded by some linear function of n and n is sufficiently large then this conjecture is true.

The study of extremal problems related to independent sets in hypergraphs is a problem that has generated much interest. There are a variety of types of independent sets in hypergraphs depending on the number of vertices from an independent set allowed in an edge. We say that a subset of vertices is j-independent if its intersection with any edge has size strictly less than j. The Kruskal–Katona theorem implies that in an r-uniform hypergraph with a fixed size and order, the hypergraph with the most r-independent sets is the lexicographic hypergraph. In this paper, we use a hypergraph regularity lemma, along with a technique developed by Loh, Pikhurko and Sudakov, to give an asymptotically best possible upper bound on the number of j-independent sets in an r-uniform hypergraph.

We introduce and study the model of simply generated non-crossing partitions, which are, roughly speaking, chosen at random according to a sequence of weights. This framework encompasses the particular case of uniform non-crossing partitions with constraints on their block sizes. Our main tool is a bijection between non-crossing partitions and plane trees, which maps such simply generated non-crossing partitions into simply generated trees so that blocks of size k are in correspondence with vertices of out-degree k. This allows us to obtain limit theorems concerning the block structure of simply generated non-crossing partitions. We apply our results in free probability by giving a simple formula relating the maximum of the support of a compactly supported probability measure on the real line in terms of its free cumulants.

We show that the list chromatic number of a simple d-regular r-uniform hypergraph is at least (1/2r log(2r2) + o(1)) log d if d is large.

For fixed graphs F1,…,Fr, we prove an upper bound on the threshold function for the property that G(n, p) → (F1,…,Fr). This establishes the 1-statement of a conjecture of Kohayakawa and Kreuter.

We study three quantities that can each be viewed as the time needed for a finite irreducible Markov chain to ‘forget’ where it started. One of these is the mixing time, the minimum mean length of a stopping rule that yields the stationary distribution from the worst starting state. A second is the forget time, the minimum mean length of any stopping rule that yields the same distribution from any starting state. The third is the reset time, the minimum expected time between independent samples from the stationary distribution.

Our main results state that the mixing time of a chain is equal to the mixing time of the time-reversed chain, while the forget time of a chain is equal to the reset time of the reverse chain. In particular, the forget time and the reset time of a time-reversible chain are equal. Moreover, the mixing time lies between absolute constant multiples of the sum of the forget time and the reset time.

We also derive an explicit formula for the forget time, in terms of the 'access times' introduced in [11]. This enables us to relate the forget and reset times to other mixing measures of the chain.

Let m,n and t be positive integers. Consider [m]n as the set of sequences of length n on an m-letter alphabet. We say that two subsets A⊂[m]n and B⊂[m]n cross t-intersect if any two sequences a∈A and b∈B match in at least t positions. In this case it is shown that if $m > (1-\frac 1{\sqrt[t]2})^{-1}$ then |A||B|≤(mn−t)2. We derive this result from a weighted version of the Erdős–Ko–Rado theorem concerning cross t-intersecting families of subsets, and we also include the corresponding stability statement. One of our main tools is the eigenvalue method for intersection matrices due to Friedgut [10].

Let G be a finite graph with minimum degree r. Form a random subgraph Gp of G by taking each edge of G into Gp independently and with probability p. We prove that for any constant ε > 0, if $p=\frac{1+\epsilon}{r}$, then Gp is non-planar with probability approaching 1 as r grows. This generalizes classical results on planarity of binomial random graphs.

A class of completely symmetric simple Venn diagrams for seven sets is constructed and displayed.

We find new properties of the topological transition polynomial of embedded graphs, Q(G). We use these properties to explain the striking similarities between certain evaluations of Bollobás and Riordan's ribbon graph polynomial, R(G), and the topological Penrose polynomial, P(G). The general framework provided by Q(G) also leads to several other combinatorial interpretations these polynomials. In particular, we express P(G), R(G), and the Tutte polynomial, T(G), as sums of chromatic polynomials of graphs derived from G, show that these polynomials count k-valuations of medial graphs, show that R(G) counts edge 3-colourings, and reformulate the Four Colour Theorem in terms of R(G). We conclude with a reduction formula for the transition polynomial of the tensor product of two embedded graphs, showing that it leads to additional relations among these polynomials and to further combinatorial interpretations of P(G) and R(G).

We consider the set of polynomials of degree n over a finite field and put the uniform probability measure on this set. Any such polynomial factors uniquely into a product of its irreducible factors. To each polynomial we associate a step function on the interval [0,1] such that the size of each jump corresponds to the number of factors of a certain degree in the factorization of the random polynomial. We normalize these random functions and show that the resulting random process converges weakly to Brownian motion as n → ∞. This result complements earlier work by the author on the order statistics of the degree sequence of the factors of a random polynomial.

A classical result of Robertson and Seymour states that the set of graphs containing a fixed planar graph H as a minor has the so-called Erdős–Pósa property; namely, there exists a function f depending only on H such that, for every graph G and every positive integer k, the graph G has k vertex-disjoint subgraphs each containing H as a minor, or there exists a subset X of vertices of G with |X| ≤ f(k) such that G − X has no H-minor (see Robertson and Seymour, J. Combin. Theory Ser. B41 (1986) 92–114). While the best function f currently known is exponential in k, a O(k log k) bound is known in the special case where H is a forest. This is a consequence of a theorem of Bienstock, Robertson, Seymour and Thomas on the pathwidth of graphs with an excluded forest-minor. In this paper we show that the function f can be taken to be linear when H is a forest. This is best possible in the sense that no linear bound is possible if H has a cycle.

We model the transmission of a message on the complete graph with n vertices and limited resources. The vertices of the graph represent servers that may broadcast the message at random. Each server has a random emission capital that decreases at each emission. Quantities of interest are the number of servers that receive the information before the capital of all the informed servers is exhausted and the exhaustion time. We establish limit theorems (law of large numbers, central limit theorem and large deviation principle), as n → ∞, for the proportion of informed vertices before exhaustion and for the total duration. The analysis relies on a construction of the transmission procedure as a dynamical selection of successful nodes in a Galton–Watson tree with respect to the success epochs of the coupon collector problem.

Let graph $G=(V,E)$ and integer $b\geq 1$ be given. A set $S\subseteq V$ is said to be $b$-independent if $u,v\in S$ implies $d_G(u,v)>b$, where $d_G(u,v)$ is the shortest distance between $u$ and $v$ in $G$. The $b$-independence number $\a_b(G)$ is the size of the largest $b$-independent subset of $G$. When $b=1$ this reduces to the standard definition of independence number.

We study this parameter in relation to the random graph $G_{n,p},\,p=d/n$, in particular, when $d$ is a large constant. We show that w.h.p. if $d\geq d_{\epsilon, b}$, $$ \left| \alpha_b(G_{n,p}) - \frac{2bn}{d^b} \biggl(\log{d} - \frac{\log{\log{d}}}{b} - \frac{\log{2b}}{b} + \frac{1}{b}\biggr)\right| \leq \frac{\epsilon n}{d^b}.$$

Let m(k) denote the maximum number of edges in a non-extendable, intersecting k-graph. Erdős and Lovász proved that m(k) ≤ kk. For k ≥ 625 we prove m(k) < kk・e−k1/4/6.

In this paper we consider the influences of variables on Boolean functions in general product spaces. Unlike the case of functions on the discrete cube, where there is a clear definition of influence, in the general case several definitions have been presented in different papers. We propose a family of definitions for the influence that contains all the known definitions, as well as other natural definitions, as special cases. We show that the proofs of the BKKKL theorem and of other results can be adapted to our new definition. The adaptation leads to generalizations of these theorems, which are tight in terms of the definition of influence used in the assertion.

Let G be a connected graph that is 2-cell embedded in a surface S, and let G* be its topological dual graph. We will define and discuss several matroids whose element set is E(G), for S homeomorphic to the plane, projective plane, or torus. We will also state and prove old and new results of the type that the dual matroid of G is the matroid of the topological dual G*.