We prove an Erdős–Ko–Rado-type theorem for intersecting k-chains of subspaces of a finite vector space. This is the q-generalization of earlier results of Erdős, Seress and Székely for intersecting k-chains of subsets of an underlying set. The proof hinges on the author's proper generalization of the shift technique from extremal set theory to finite vector spaces, which uses a linear map to define the generalized shift operation. The theorem is the following.

For c = 0, 1, consider k-chains of subspaces of an n-dimensional vector space over GF(q), such that the smallest subspace in any chain has dimension at least c, and the largest subspace in any chain has dimension at most n − c. The largest number of such k-chains under the condition that any two share at least one subspace as an element of the chain, is achieved by the following constructions:

(1) fix a subspace of dimension c and take all k-chains containing it,

(2) fix a subspace of dimension n − c and take all k-chains containing it.

It has been conjectured that a connected matroid with largest circuit size c [ges ] 2 and largest cocircuit size c* [ges ] 2 has at most ½cc* elements. Pou-Lin Wu has shown that this conjecture holds for graphic matroids. We prove two special cases of the conjecture, not restricted to graphic matroids, thereby providing the first nontrivial evidence that the conjecture is true for non-graphic matroids. Specifically, we prove the special case of the conjecture in which c = 4 or c* = 4. We also prove the special case for binary matroids with c = 5 or c* = 5.

We show that, if M is a connected binary matroid of cogirth at least five which does not have both an F7-minor and an F*7-minor, then M has a circuit C such that M − C is connected and r(M − C) = r(M).

For a graph G on vertex set V = {1, …, n} let k = (k1, …, kn) be an integral vector such that 1 [les ] ki [les ] di for i ∈ V, where di is the degree of the vertex i in G. A k-dominating set is a set Dk ⊆ V such that every vertex i ∈ V[setmn ]Dk has at least ki neighbours in Dk. The k-domination number γk(G) of G is the cardinality of a smallest k-dominating set of G.

For k1 = · · · = kn = 1, k-domination corresponds to the usual concept of domination. Our approach yields an improvement of an upper bound for the domination number found by N. Alon and J. H. Spencer.

If ki = di for i = 1, …, n, then the notion of k-dominating set corresponds to the complement of an independent set. A function fk(p) is defined, and it will be proved that γk(G) = min fk(p), where the minimum is taken over the n-dimensional cube Cn = {p = (p1, …, pn) [mid ] pi ∈ ℝ, 0 [les ] pi [les ] 1, i = 1, …, n}. An [Oscr ](Δ22Δn-algorithm is presented, where Δ is the maximum degree of G, with INPUT: p ∈ Cn and OUTPUT: a k-dominating set Dk of G with [mid ]Dk[mid ][les ]fk(p).

Each edge of the standard rooted binary tree is equipped with a random weight; weights are independent and identically distibuted. The value of a vertex is the sum of the weights on the path from the root to the vertex. We wish to search the tree to find a vertex of large weight. A very natural conjecture of Aldous states that, in the sense of stochastic domination, an obvious greedy algorithm is best possible. We show that this conjecture is false. We prove, however, that in a weaker sense there is no significantly better algorithm.

Assemblies are decomposable combinatorial objects characterized by a sequence mi that counts the number of possible components of size i. Permutations on n elements, mappings from a set containing n elements into itself, 2-regular graphs on n vertices, and set partitions on a set of size n are all assemblies with natural decompositions. Logarithmic assemblies are characterized by constants θ > 0 and κ0 > 0 such that miκi0/ (i−1)! → θ. Random mappings, permutations and 2-regular graphs are all logarithmic assemblies, but set partitions are not.

Given a logarithmic assembly, all representatives having total size n are chosen uniformly and a component counting process C(n) = (C1(n), C2(n), …, Cn(n)) is defined, where Ci(n) is the number of components of size i. Our results also apply to C(n) distributed as the Ewens sampling formula with parameter θ. Denote the component counting process up to size at most b by Cb(n) = (C1(n), C2(n), …, Cb(n)). It is natural to approximate Cb by Zb = (Z1, Z2, …, Zb), the b-dimensional process of independent Poisson variables Zi for which the ith variable has expectation [ ]Zi = miκi0 exp((1−θ)i/n)/i!. We find asymptotics for the total variation distance between Cb(n) and Zb.

In [1], recently published in Combinatorics, Probability and Computing, there was a typographical error. On p. 392, part (5) of Lemma 3.1, the formula should read as follows:

formula here

References

[1] Hadjicostas, P. (1998) The asymptotic proportion of subdivisions of a 2 × 2 table that result in Simpson's Paradox. Combinatorics, Probability and Computing7 387–396.