Infinite trees of matroids

Welcome back to this series of posts about infinite matroids. Up to this point we’ve seen what infinite matroids are, and we’ve started to understand the notion a little by looking at a variety of examples. Next we will look at how to stick together infinite matroids to build bigger ones. We’ll see that it is possible to stick infinitely many matroids together at once, and this will give us a flexible way to build new infinite matroids by sticking together infinitely many finite matroids.

Let’s start with a familiar way to stick matroids together: via 2-sums. Suppose that we have matroids $M_1$ and $M_2$ with ground sets $E_1$ and $E_2$, and suppose that these ground sets meet in only a single edge $e$. For the sake of simplicity, we’ll assume that $e$ isn’t a loop or a coloop in either matroid. Now we can build a new matroid $M_1 \oplus_2 M_2$ on the ground set $E_1 \triangle E_2$, by taking the circuits to be sets of the following 3 kinds:

  • circuits of $M_1$ not containing $e$
  • circuits of $M_2$ not containing $e$
  • sets of the form $C_1 \cup C_2 -e$, where $C_1$ and $C_2$ are circuits of $M_1$ and $M_2$ respectively, both containing $e$.

These three kinds of circuit are illustrated below:

circuits

This operation is associative, in the sense we might expect: suppose we have 3 matroids $M_1$, $M_2$ and $M_3$ on ground sets $E_1$, $E_2$ and $E_3$. Suppose that $E_1 \cap E_2$ and $E_2 \cap E_3$ each contain just a single edge, and that $E_1 \cap E_3$ is empty. Then the two matroids $M_1 \oplus_2 (M_2 \oplus_2 M_3)$ and $(M_1 \oplus_2 M_2) \oplus_2 M_3$ are equal. This is easy to see by considering the six kinds of circuits which can arise in the sum, as shown here:

associative

Usually associativity means that it doesn’t matter how we bracket a list of things that we want to add together, but in the case of 2-sums the geometry is a little different. The kind of configuration we might want to stick together with 2-sums in general is not a list of matroids, but rather a tree of matroids. More precisely, suppose we have a finite tree $T$, and that for each node $t$ of $T$ we have a matroid $M_t$ with ground set $E_t$. Suppose further that for distinct nodes $t$ and $t’$ of $T$ the intersection $E_t \cap E_{t’}$ either consists of a single edge $e_{tt’}$, if $t$ and $t’$ are neighbours in $T$, or else is empty. Let’s call a structure like this a finite tree of matroids. Then there is an unambiguously defined 2-sum of our tree of matroids, whose ground set is the union of all the sets $E_t$ but without the `gluing edges’ $e_{tt’}$. A typical circuit in such a 2-sum of a tree is shown here:

asstree

More precisely, each circuit of the 2-sum is supported on some subtree $S$ of $T$. It is determined by a choice, for each node $t$ of $S$, of a circuit $C_t$ of $M_t$. This circuit $C_t$ should contain precisely those gluing edges $e_{tt’}$ of $M_t$ such that $t’$ is also in $S$. Given such a subtree $S$ and such a family of circuits $C_t$, we get a circuit of the 2-sum whose edges are the non-gluing edges of the circuits $C_t$.

All of this works just as well for sticking together infinite matroids as for finite ones. But the real power of this technique for building new infinite matroids comes when we consider 2-sums of infinitely many matroids at once.

So what happens if we try to stick together an infinite tree of matroids in the way outlined above? To understand the kinds of difficulty which can arise, let’s first of all consider the simplest possible infinite tree: an infinite ray. We certainly want to allow circuits of the following kind:

fincirc

 

But what about ones which go all the way to the end of the ray:

infcirc

Should we allow them?

It turns out that if we allow them, then we get an infinite matroid. But we also get a different infinite matroid by banning them: by only allowing those circuits whose underlying tree $S$ is finite. So we have two different options for how to build a matroid by sticking together an infinite ray of matroids. We say that the circuits are allowed to use the end of the ray in the first of these matroids, but not in the second.

We could just decide to fix one of these two as the `correct’ 2-sum of the ray of matroids, but it turns out that that would be a bad idea. To see why, we should consider the interaction of 2-sums with duality. If we take the dual of the 2-sum of 2 matroids, then it turns out to be the same as the 2-sum of their duals. It follows that the same is true for finite trees of matroids: the dual of the 2-sum of a tree of matroids is the 2-sum of the duals of those matroids. This is certainly a property which we would like to keep for infinite 2-sums.

Now suppose that we have a ray of matroids, and we take the variant of the 2-sum where the circuits are not allowed to use the end, then take the dual of that 2-sum. What we get is the 2-sum of the duals of the matroids, but this time in the version where the circuits are allowed to use the end. So these two different constructions of the 2-sum of a ray are dual to each other, and we shouldn’t privilege either of them.

Formally, we take the decision about whether the circuits should be allowed to use the end of the ray to be part of the data used to specify the sum, in addition to the choices of the matroids lying along the ray. More generally, suppose that we have an infinite tree of matroids. Then in order to specify a 2-sum for this tree of matroids, we must decide, for each end of the tree, whether the circuits are allowed to use that end. Here the ends of the tree can be identified with the rays from a fixed root.

More precisely, suppose that we have a (possibly infinite) tree $T$, and that for each node $t$ of $T$ we have a matroid $M_t$ with ground set $E_t$. Suppose further that for distinct nodes $t$ and $t’$ of $T$ the intersection $E_t \cap E_t’$ either consists of a single edge $e_{tt’}$, if $t$ and $t’$ are neighbours in $T$, or else is empty. Suppose further that we have a subset $\Psi$ of the set of ends of $T$, which we intend to be the set of ends which we will allow circuits to use. Then we might hope to define the 2-sum of this tree of matroids as follows:

Each circuit of the 2-sum will be supported on some subtree $S$ of $T$, such that all rays in $S$ go to ends in $\Psi$. The circuit is determined by a choice, for each node $t$ of $S$, of a circuit $C_t$ of $M_t$. This circuit $C_t$ should contain precisely those gluing edges $e_tt’$ of $M_t$ such that $t’$ is also in $S$. Given such a subtree $S$ and such a family of circuits $C_t$, we get a circuit of the 2-sum whose edges are the non-gluing edges of the circuits $C_t$.

So the circuits would look something like this:

inftree

Unfortunately, this construction does not always give a matroid. The reason why not is related to some tricky set-theoretical issues, so we will not discuss it here. But due to a very deep and beautiful set-theoretic result called Borel Determinacy, we know that this construction will give a matroid if the set $\Psi$ is topologically nice enough (if it is a Borel set) [BC15].

There are also certain infinite trees of matroids such that the above construction will give a matroid for any set $\Psi$ of ends. This has the immediate consequence that there are a lot of infinite matroids – as many as there could possibly be. A matroid is determined by a set of subsets of its ground set, so there could be no more than $2^{2^{\aleph_0}}$ matroids on a countable set. And in fact, there are that many non-isomorphic matroids on a countable set, because there are that many possibilities for the set $\Psi$.

This means that when an infinite matroid is constructed from a tree of matroids together with a set $\Psi$ of ends, most of the information is encoded in the set $\Psi$ – if the matroids in the tree are finite, then there are only $2^{\aleph_0}$ possibilities for the tree of matroids, but there are $2^{2^{\aleph_0}}$ possibilities for $\Psi$. This huge reservoir of extra information hidden at the ends means that countable matroids behave in many ways like uncountable graphs. For example, the constructions which show that infinite graphs in general are not well-quasi-ordered under the minor relation already work for countable matroids, even though they do not work for countable graphs [BC15].

The construction we are considering also plays a key role for the reconstruction of infinite matroids from their decompositions into 3-connected parts. It is known that any finite matroid is canonically expressible as a 2-sum of a finite tree of matroids, each of which is either 3-connected or else consists of a single circuit or cocircuit [CE80, S80]. This result extends directly to infinite matroids: any matroid can be canonically expressed as a 2-sum (in the above sense) of a tree of matroids, each of which is either 3-connected or else consists of a single circuit or cocircuit [ADP15, BC16]. As with the finite result, this implies that it often suffices to prove a result only for 3-connected matroids in order to be able to deduce it for all matroids.

The construction we have considered was based on the 2-sum, one of the simplest possible ways to stick matroids together. Next time, we shall see that similar ideas work to give infinitary versions of other more complicated ways of sticking matroids together, and the surprisingly close connections between these infinitary sums and the matroids naturally arising in infinite graphs.

[ADP15] E. Aigner-Horev, R. Diestel, L. Postle. The structure of 2-separations of infinite matroids, to appear in JCTB, available here.
[BC15] N. Bowler and J. Carmesin, Infinite Matroids and Determinacy of Games, submitted to LMS, available here.
[BC16] N. Bowler and J. Carmesin, The ubiquity of Psi-matroids, preprint, available here.
[CE80] W. H. Cunningham and J. Edmonds, A combinatorial decomposition theory, Canad. J. Math. 32 (1980), no. 3, 734–765.
[S80] P. D. Seymour, Decomposition of regular matroids, J. Combin. Theory Ser. B 28 (1980), no. 3, 305–359.

The complexity of the matching polytope and ear-decompositions of matroids

Guest post by Yohann Benchetrit.

Introduction

The topic of this post is to introduce a new parameter $\beta$ measuring the complexity of the facets of the matching polytope of a graph, which also extends to binary matroids. We give a simple efficient algorithm deciding whether a binary matroid satisfies $\beta\leq 1$. This is the first non-trivial case after bipartiteness, which is equivalent to $\beta=0$. The results presented here are joint work with András Sebő, and appeared in [1].

The matching polytope of a graph plays an important role in Graph Theory and Combinatorial Optimization. The methods involved in the study of its structure and properties initiated many relations between polyhedra, min-max theorems and polynomial-time algorithms.

A matching of a graph is a set of pairwise non-incident edges. The incidence vector of a matching $M$ of a graph $G$ is the 0-1 vector $\chi^{M}$ of $\mathbb{R}^{E(G)}$ defined for every $e\in E(G)$ by: $\chi^{M}(e)=1$ if and only if $e\in M$. The matching polytope of $G$, denoted by $\mathsf{MATCH}(G)$, is the convex hull of the incidence vectors of the matchings of $G$. As a polyhedron, it is the set of solutions of a finite number of linear inequalities over $\mathbb{R}^{E(G)}$. Basically, information on the inequalities describing this polytope is useful as it allows applying linear programming tools (for example the duality theorem, the Ellipsoid method, etc.).

The following result, due to Edmonds and Pulleyblank [5], gives a complete description of the matching polytope using linear inequalities. A graph $H$ is factor-critical if for every $v\in V(H)$, the graph obtained from $H$ by deleting $v$ and every edge incident to $v$ has a perfect matching (a matching covering every vertex).

Theorem 1.  For every graph $G$:
\begin{equation*}\label{fonda-eqn-MATCH}
\mathsf{MATCH}(G):=\left\{x\in\mathbb{R}^{E(G)}\colon\begin{array}{cc}
x\geq 0, & \\
\displaystyle \sum_{\text{e incident to $v$}}x_e\leq 1 & \forall v\in V(G), \\
\displaystyle \sum_{e\in E(H)}x_e\leq \frac{|V(H)|-1}{2} & \text{$\forall H$ 2-connected factor-critical } \\
& \text{induced subgraph of $G$}
\end{array}\right\}.
\end{equation*}

Furthermore, Edmonds [4] shows that each inequality associated with a 2-connected factor-critical induced subgraph $H$ appears in every description of $ \mathsf{MATCH}(G)$.

An ear-decomposition of a graph $G$ is a sequence $(P_0,\ldots,P_k)$ of a circuit $P_0$ and paths (with two distinct ends) $P_1,\ldots,P_k$ of $G$ such that $E(G)=E(P_0)\cup\ldots\cup E(P_k)$ and for every $i\in\left\{
1,\ldots,k\right\}$, $P_i$ meets $P_0\cup\ldots\cup P_{i-1}$ exactly on its two ends; the $P_i$ are the ears of the decomposition (notice that we do not allow an ear to attach on a single vertex). The decomposition is odd if all ears have an odd number of edges. Lovász proved:

Theorem 2.  A graph is 2-connected and factor-critical if and only if it has an odd ear-decomposition.

It follows from Menger’s theorem that a graph admits an ear-decomposition if and only if it is 2-connected. In addition, all ear-decompositions of a 2-connected graph $G$ have the same number $|E(G)|-|V(G)|+1$ of ears (indeed, deleting a single edge from each ear of an arbitrary ear-decomposition yields a spanning tree), hence the number of ears of $G$ is well-defined.

This and Lovász’s result suggest the following measure of complexity of the matching polytope:

Definition 3.  For each graph $G$, let $\beta(G)$ denote the largest number of ears of a 2-connected factor-critical subgraph of $G$.

For example, $\beta(G)=0$ if and only if $G$ is a bipartite graph, and $\beta(G)\leq 1$ if and only if $G$ does not contain three pairwise internally-disjoint paths with the same ends, such that exactly two of them have an odd number of edges.

The Parity Minor Algorithm [6] implies that for each fixed $k$, determining whether a graph $G$ satisfies $\beta(G)\geq k$ can be done in polynomial-time.  However, the proof in [6] is built upon elaborate techniques of the Graph Minor Project, and is oriented towards generality. This suggests searching for more adapted algorithms. In this direction, Bruhn and Schaudt [2] provided a direct solution to test $\beta\leq 1$ efficiently for graphs with maximum degree 3.

In the rest of this post, we extend $\beta$ to binary matroids and characterize those which satisfy $\beta\leq 1$. As a consequence, we obtain an elementary polynomial-time algorithm for testing whether a binary matroid $M$ satisfies $\beta(M)\leq 1$ or finding an obstruction, only using ear-decompositions and basic computations in the cycle space (mod 2). This completely avoids Graph Minors and implies a rather simple algorithm deciding $\beta\leq 1$ in graphs, with no restriction on the degree.

Also, applying our result to the co-graphic case yields an unexpected consequence: determining whether a graph has two odd bonds meeting on an even number of edges can be carried out efficiently.

Our motivation in studying $\beta$ comes from the recognition problem for $h$-perfect graphs. A graph is $h$-perfect if the convex hull of the incidence vectors of its stable sets (sets of pairwise non-adjacent vertices) is completely described by non-negativity and rank-inequalities of cliques and odd circuits.  The class of $h$-perfect graphs are a superclass of perfect graphs, and share a number of similar properties with the latter (see the second volume of Schrijver’s Combinatorial Optimization for further details).

Whereas perfection can be checked in polynomial-time, it is still open whether the same holds for $h$-perfection. Testing the $h$-perfection of a line graph $L(G)$ is essentially equivalent to checking $\beta(G)\leq 1$, and thus our results on $\beta$ directly imply a simple algorithm recognizing $h$-perfect line graphs.

Testing $\beta\leq 1$ in Binary Matroids

An ear-decomposition of a matroid $M$ is a sequence $(C_1,\ldots,C_k)$ of circuits of $M$ such that: $C_1\cup \ldots \cup C_k=E(M)$ and for each $i\in\left\{2,\ldots,k \right\}$, $C_i$ meets both $\cup_{j<i}C_j$ and its complement, and $C_i\setminus (\cup_{j<i}C_j)\neq\emptyset$ is a circuit of the contraction $M/(\cup_{j<i}C_j)$. The ear-decomposition is odd if the sets $C_i\setminus (\cup_{j<i}C_j)$ (the ears) all have odd cardinality (for $i\in\left\{1,\ldots,k\right\}$).

A matroid is factor-critical if it has an odd ear-decomposition.  It is easy to check that a matroid has an ear-decomposition if and only if it is connected, and that all the ear-decompositions of a connected binary matroid have the same number $|E(M)|-\mathsf{rk}(M)$ of ears. Hence, for each binary matroid $M$,  we may define $\beta(M)$ as the largest number of ears of a factor-critical restriction of $M$. It is straightforward to check that the values of $\beta$ for a graph and its circuit matroid are equal.

For algorithmic considerations, we assume that binary matroids are given by a linear representation or an independence oracle; complexity refers to the number of required calls to this oracle.

The first important observation is the following (see [1] for a proof).

Lemma 4.  A connected binary matroid $M$ satisfies $\beta(M)\geq 2$ if and only if it has two odd circuits which meet in an even number of elements.  Furthermore, a factor-critical restriction of $M$ with two ears can be constructed from two such odd circuits in polynomial-time.

This states that we have to check the parity of the intersection of every pair of odd circuits of $M$ to certify that $\beta(M)\leq 1$. In fact, we need only to check it for pairs of a certain basis of the cycle space of $M$.

A cycle of a matroid is a union of disjoint circuits, and it is odd if it has odd cardinality.  The set of (incidence vectors of) cycles of a binary matroid $M$ is a subspace of $\mathbb{F}_2^{E(M)}$ (this characterizes binary matroids), called the cycle space of $M$ and denoted by $\mathcal{C}(M)$. Clearly, $\mathcal{C}(M)$ is spanned by the circuits of $M$ and $\dim \mathcal{C}(M)=|E(M)|-\mathsf{rk}(M)$ (consider the set of fundamental circuits of a basis). A set $S$ of cycles of $M$ is a cycle basis of $M$ if the incidence vectors of the elements of $S$ form a basis of $\mathcal{C}(M)$.
A cycle basis $B$ is odd if all its cycles are odd, and it is totally odd if moreover all the cycles of $B$ pairwise-intersect on an odd number of elements.

We now prove the main ingredient of our characterization. The fact that we have only circuits in the basis obtained is crucial.

Lemma 5.  Each connected non-bipartite binary matroid has an odd cycle basis formed by circuits only. It can be constructed in polynomial time.

Proof. Let $M$ be a connected and non-bipartite binary matroid. Let $M_p$ be the binary matroid obtained by adding successively an all-0 column and an all-1 line to a matrix representation of $M$, and let $p$ be the new element of $M_p$.
Lehman’s matroid-port theorem easily implies that each element of $M$ belongs to an odd circuit (see [8]). It follows straightforwardly that $M_p$ is a connected matroid.
Furthermore, a theorem of Coullard and Hellerstein states that for each connected matroid $N$ and every $e\in E(N)$, there exists an ear-decomposition of $N$ whose circuits all contain $e$ and which can be found in polynomial-time [3].

Now, consider an ear-decomposition $\left\{C_1,\ldots,C_k \right\}$ of $M_p$ such that all the $C_i$ contain $p$. It is easy to check that $\left\{C_1\setminus \left\{p\right\},\ldots,C_k\setminus \left\{p\right\}\right\}$ is an odd cycle basis of $M$, formed by circuits only. $\blacksquare$

The following statement is a direct consequence of the well-known fact that, for two subsets $S_1,S_2$ of a set $S$: the sum of the incidence vectors of $S_1$ and $S_2$ in $\mathbb{F}_2^{S}$ is the incidence vector of $S_1\Delta S_2$ and their product is the parity of $ |S_1\cap S_2|$ (with respect to the standard bilinear form on $\mathbb{F}_2^{S}$).

Lemma 6. If a binary matroid has a totally odd cycle basis, then all its odd cycles pairwise-intersect in an odd number of elements.

We can finally prove our characterization.

Theorem 7.  Let $M$ be a connected non-bipartite binary matroid. The following statements are equivalent.

  1. $\beta(M)\leq 1$,
  2. $M$ has a totally odd cycle basis formed by circuits only,
  3. each odd cycle basis of $M$ is totally odd.

Proof.  We first prove that $ (1)\Rightarrow (2) $. Since $\beta(M)\leq 1$ and as $M$ is connected and non-bipartite, Lemma 5 shows that $M$ has an odd cycle basis $B$ whose elements are circuits. Lemma 4 implies that the elements of $B$ pairwise-intersect in an odd number of elements. That is, $B$ is totally odd.

The implication $ (2)\Rightarrow (3) $ straightforwardly follows from Lemma 6.

We finally prove $ (3)\Rightarrow (1) $. Suppose that each odd cycle basis of $M$ is totally odd.  Since $M$ is connected and non-bipartite, Lemma 5 shows that $M$ has an odd cycle basis $B$. Since $B$ is totally odd, Lemma 6 implies that all odd cycles, and in particular all odd circuits of $M$, pairwise-intersect in an odd number of elements. By Lemma 4, we get $\beta(M)\leq 1$. $\blacksquare$

Now, testing whether a connected non-bipartite binary matroid $M$ satisfies $\beta(M)\leq 1$ can be done as follows: build an odd cycle basis $B$ of $M$ formed by circuits only (with Lemma 5), and compute the parities of the intersections of pairs of elements of $B$; there is only a polynomial number of such pairs, since $|B|=\dim \mathcal{C}(M)=|E(M)|-\mathsf{rk}(M)$.
If two elements of $B$ meet in an even number of elements, then Lemma 4 shows $\beta(M)\geq 2$ and a factor-critical restriction of $M$ with exactly two ears. Otherwise, $B$ is totally odd and Theorem 7 implies that $\beta(M)\leq 1$.

Clearly, a binary matroid $M$ satisfies $\beta(M)\leq 1$ if and only if every non-bipartite block of $M$ satisfies this condition. The blocks of $M$ can be easily found in polynomial-time, and hence we need only one more subroutine to finish the algorithm: deciding in polynomial-time whether a connected binary matroid is bipartite. This can be carried out using the following straightforward proposition, which generalizes the bipartiteness test of graphs.

Proposition 8.  Let $M$ be a connected binary matroid. The following statements are equivalent.

  1.  $M$ is bipartite,
  2. There exists a cycle basis of $M$ containing only even circuits,
  3. Each cycle basis of $M$ contains only even cycles.

Hence, testing bipartiteness only requires building a cycle basis formed by circuits (from the fundamental circuits of a basis of $M$, for example) and checking whether all its circuits are even. If so, the matroid is bipartite and otherwise we find an odd circuit.

Open Problems

$\beta$ can be used as a parameter to separate on, for properties of the matching polytope (for example, the integer decomposition property [1]).  The complexity of computing $\beta$ for graphs is apparently not known.

Clearly, the property $\beta(G)\geq k$ is in $\mathsf{NP}$ (as factor-criticality can be tested using a maximum-matching algorithm), but we do not know if it belongs to $\mathsf{co}$-$\mathsf{NP}$. Also, it is not clear whether the Parity Minor algorithm can be circumvented to check efficiently, for fixed $k\geq 3$, whether a graph $G$ satisfies $\beta(G)\geq k$.

For binary matroids, the situation is even less clear: results of Szegedy and Szegedy [9] show that testing whether a binary matroid is factor-critical can be done in randomized polynomial-time, but a deterministic algorithm is still missing, even for co-graphic matroids. Finally, it is not clear whether $\beta\leq 1$ can be decided efficiently for other interesting classes of matroids (our approach does not directly extend to anything else).

References

[1] Y. Benchetrit and A. Sebő. Ear-decompositions and the complexity of the matching polytope. arXiv preprint, 2015.

[2] H. Bruhn and O. Schaudt. Claw-free t-perfect graphs can be recognised in polynomial time. In Jon Lee and Jens Vygen, editors, IPCO, volume 8494 of LNCS, pages 404–415. 2014.

[3] C. Coullard and L. Hellerstein. Independence and port oracles for matroids, with an application to computational learning theory. Combinatorica, 16(2):189–208, 1996.

[4] J. Edmonds. Maximum matching and a polyhedron with 0, 1 vertices. J. of Res. the Nat. Bureau of Standards, 69 B:125–130, 1965.

[5] J. Edmonds and W. Pulleyblank. Facets of 1-matching polyhedra. In Hypergraph Seminar of Columbus, 1974.

[6] K. Kawarabayashi, B. Reed, and P. Wollan. The graph minor algorithm with parity conditions. In FOCS, 2011 IEEE 52nd Annual Symposium, pages 27–36. IEEE, 2011.

[7] L. Lovász. A note on factor-critical graphs. Studia Sci. Math. Hungar., 7:279–280, 1972.

[8] James Oxley. Matroid Theory. 1992.

[9] B. Szegedy and C. Szegedy. Symplectic spaces and ear-decomposition of matroids. Combinatorica, 26(3):353–377, 2006.

Counting Matroids by Entropy

Guest post by Rudi Pendavingh and Jorn van der Pol

Introduction

Bounding the entropy of a random variable often gives surprisingly strong bounds on the cardinality of its support. With Nikhil Bansal [BPvdP15], we gave a short entropy argument to obtain a bound on the number of matroids on groundset $\{1,2,\ldots,n\}$ that is quite close to the best known upper bound.

Roughly, the method works by bounding the number of matroids of rank 2, and using an entropy argument to derive a bound for the number of matroids of rank $r$. The same methods works for a number of other minor-closed classes, possibly after bounding the number of matroids of rank 3 (rather than 2) in the class under consideration.

In this blog post, we show how entropy can be used for counting problems in general and for counting matroids in particular, and we give a new proof for the following theorem from [PvdP15].

Theorem. If $N=U_{2,k}$ or $N=U_{3,6}$, then asymptotically almost all matroids have an $N$-minor.

Entropy

Let $X$ be a random variable taking its values in a set $\mathcal{X}$ (we will always assume that $\mathcal{X}$ is a finite set). For $x \in \mathcal{X}$, let us write $P(x) = \mathbb{P}(X=x)$ for the probability that $X=x$. The entropy of $X$ is defined as
$$\mathcal{H}(X) = -\sum_{x \in \mathcal{X}} P(x) \log P(x),$$
where $\log$ denotes the binary logarithm, and for convenience we write $0\log 0 = 0$.

As an example, let us consider the case where $X$ takes the values 0 and 1 with probability $1-p$ and $p$, respectively. The entropy of $X$ is given by the binary entropy function,
$$\mathcal{H}(X) = H(p) := -p \log p – (1-p) \log (1-p).$$
If $p=1/2$, $X$ is a purely random bit of information, and we have $\mathcal{H}(X) = 1$. If $p=0$ or $p=1$, there is no randomness involved, and $\mathcal{H}(X) = 0$.

More generally, the entropy of $X$ measures the amount of information that is gained by learning the value of $X$. This may provide some intuition for the following properties of $\mathcal{H}(X)$.

  • Boundedness: $\mathcal{H}(X) \le \log |\mathcal{X}|$.
  • Subadditivity: $\mathcal{H}(X,Y) \le \mathcal{H}(X) + \mathcal{H}(Y)$.

Boundedness holds with equality if and only if $X$ has the uniform distribution on $\mathcal{X}$, i.e. $P(x) = 1/|\mathcal{X}|$ for all $x$. This makes entropy very useful for counting problems. If the random variable $X$ has the uniform distribution over $\mathcal{X}$, then $|\mathcal{X}| = 2^{\mathcal{H}(X)}$. So, bounds on the entropy of $X$ translate directly to bounds on $|\mathcal{X}|$.

In our applications, the space $\mathcal{X}$ consists of binary vectors, indexed by some set $J$. This allows us to define projections $X_T = (X_j : j \in T)$ for $T\subseteq J$.

Our main tool is the following result, which was first obtained in [CFGS86] in a different form. A proof and further discussion can also be found in [AS08].

Shearer’s Entropy Lemma. If $X$ is a random variable taking values in $\mathcal{X} \subseteq \{0,1\}^J$, and $T_1, T_2, \ldots, T_m$ is a collection of subsets of $J$ such that each $x \in \mathcal{X}$ is contained in at least $k$ of the $T_i$, then
$$\mathcal{H}(X) \le \frac{1}{k} \sum_{i=1}^m \mathcal{H}(X_{T_i}).$$

Intuitively, the lemma asserts that if every bit of information is contained in at least $k$ of the projected random variables, then the total amount of information contained in the projections is at least $k$ times the amount of information in $X$. Note that subadditivity follows as a special case of Shearer’s Lemma.

Matroid counting

In what follows, we will write $\mathbb{M}$ for the class of all matroids, $\mathbb{M}(E,r)$ for the class of matroids on groundset $E$ of rank $r$, and so on. $\mathcal{M}$ will be a subclass of matroids that is always closed under isomorphism, and possibly satisfies some additional properties.

As $\mathcal{M}$ is closed under isomorphism, $|\mathcal{M}\cap\mathbb{M}(E,r)|$ depends on $E$ only through its cardinality, and we will write $m_\mathcal{M}(n,r) = |\mathcal{M}\cap\mathbb{M}([n],r)|$.

The following result illustrates Shearer’s Entropy Lemma. As its proof is short, we will include it here.

Lemma. If $\mathcal{M}$ is closed under taking submatroids, then $$\frac{\log\left(1+m_{\mathcal{M}}(n,r)\right)}{  \binom{n}{r}} \leq \frac{\log \left(1+m_{\mathcal{M}}(n-1,r)\right)}{  \binom{n-1}{r}}.$$

Proof: If $M$ is a matroid with set of bases $\mathcal{B}$, and $e\in E(M)$ is not a coloop of $M$, then $\{B \in \mathcal{B} : e\not\in\mathcal{B}\}$ is the set of bases of $M\backslash e$. We will apply Shearer’s Entropy Lemma in such a way that its projections correspond to deletions.

Let $E$ be a set of cardinality $n$. We encode $M\in\mathcal{M}\cap\mathbb{M}(E,r)$ by the incidence vector of its bases. This is the binary vector $\chi$, indexed by the $r$-subsets of $[n]$, such that $\chi(B) = 1$ if and only if $B$ is a basis of $M$. Our space $\mathcal{X} \equiv \mathcal{X}(E,r)$ consists of all incidence vectors corresponding to $M\in\mathcal{M}\cap\mathbb{M}(E,r)$, as well as the all-zero vector. Thus, $|\mathcal{X}| = 1+m_\mathcal{M}(n,r) $, and if $X$ has the uniform distribution on $\mathcal{X}$, then $\mathcal{H}(X) = \log\left(1+ m_\mathcal{M}(n,r) \right)$.

If $e$ is not a coloop of $M$, then the incidence vector of $M\backslash e$ is obtained from $\chi$ by restricting $\chi$ to the entries avoiding $e$. (If $e$ is a coloop, this operation yields the all-zero vector, which is the reason that we need to include the all-zero vector in $\mathcal{X}$.)

We make two observations.

  • For $e \in E$, let $T_e = \binom{E-e}{r}$. It follows from the previous paragraph, that if $X \in \mathcal{X}(E,r)$, the projection $X_{T_e}\in\mathcal{X}(E-e,r)$.
  • Each $r$-subset of $E$ is contained in $|E|-r$ different $T_e$.

An application of Shearer’s Entropy Lemma, followed by an application of the Boundedness Property shows
$$\mathcal{H}(X) \le \frac{1}{n-r} \sum_{e \in E} \mathcal{H}(X_{T_e}) \le \frac{n}{n-r} \log \left(1+ |\mathcal{M}\cap\mathbb{M}(n-1,r)| \right),$$
which concludes the proof. $\square$

Repeated application of the statement dual to Lemma 1 yields the following variant:

Matroid Entropy Lemma. If $\mathcal{M}$ is closed under contraction, then for all $t \le r$
$$\frac{\log\left(1+m_{\mathcal{M}}(n,r)\right)}{\binom{n}{r}} \le \frac{\log\left(1+m_{\mathcal{M}}(n-t,r-t) \right)}{\binom{n-t}{r-t}}.$$

This variant enables us to lift upper bounds on the number of matroids of a fixed rank $s$  to upper bounds on the number of matroids in any rank $r\geq s$.

The first natural application of this scheme is counting matroids in general, so the case $\mathcal{M}=\mathbb{M}$. We will abbreviate $m(n,r):=m_{\mathbb{M}}(n,r)$, and consider the matroids of fixed rank $s=2$. Since each matroid of rank 2 on $n$ elements determines a nontrivial partition of $n+1$ elements, we have $1+m(n,2)\leq (n+1)^n$. Hence, $$\frac{\log (1+m(n,r))}{  \binom{n}{r}} \leq \frac{\log (1+m(n-r+2,2))}{\binom{n-r+2}{2}}\leq \frac{2\log(n-r+3)}{n-r+1}.$$ It then is straightforward to derive the following for $m(n):=\sum_r m(n,r)$.

Theorem (Bansal, Pendavingh, Van der Pol 2014).

$$\log m(n) \leq O\left(\binom{n}{n/2}\frac{\log(n)}{n}\right)\text{ as }n\rightarrow\infty$$

For comparison, we state the following lower bound.

Theorem (Knuth 1974;  Graham, Sloane 1980). $\log m(n) \geq \binom{n}{n/2}/n$.

So our entropy bound on $\log m(n)$ is off by a factor $\log n$, which is not too bad given the simplicity of the argument. The $\log n$ factor will not go away if we use a fixed rank $s>2$ for the base case. The following paraphrases a result due to Bennett and Bohman (see [Kee15]).

Theorem For any fixed $s\geq 3$, we have  $$\frac{\log m(n,s)}{\binom{n}{s}}\geq \frac{\log(e^{1-s}(n-s+1))}{n-s+1}\text{ as }n\rightarrow\infty$$

We defer the details of these lower bounds to a later post.

Further applications

To show that asymptotically almost all matroids have certain fixed matroid $N$  as a minor, it suffices to find an upper bound on the number of matroids without such a minor which is vanishing compared to the above lower bound on $m(n)$. We next show how entropy counting gives a sufficient upper bound in case $N=U_{2,k}$ or $N=U_{3,6}$. Let $$Ex(N):= \{M \in \mathbb{M}: M\not \geq N\}|.$$ We first consider a fixed $N=U_{2,k}$, and bound $m'(n,r):=m_{Ex(U_{2,k})}(n,r)$.

Each matroid of rank 2 on $n$ elements without $U_{2,k}$-minor corresponds 1-1 to a partition of $n+1$ items into at most $k$ parts, so that  $1+m'(n,2)=k^{n+1}$. This gives $$\frac{\log (1+m'(n,r))}{  \binom{n}{r}} \leq \frac{\log (1+m'(n-r+2,2))}{\binom{n-r+2}{2}}\leq \frac{2\log(k)}{n}(1+o(1)),$$ which does not suffice to push the upper bound on $m_{Ex(U_{2,k})}(n):=\sum_r m'(n, r)$ below the lower bound on $m(n)$.

At the time of writing of [PvdP15], we made this same calculation and then gave up on using the matroid entropy lemma to produce the upper bound. Instead, we developed cover complexity to do the job. But recently we noted that we were wrong to give up on entropy so soon, which works beautifully if we proceed from matroids of fixed rank $s=3$ rather than $2$.

It is easy to show that a simple matroid of rank 3 without $U_{2,k}$ as a minor has at most $1+(k-1)(k-2)$ points (fix a point and consider that all other points are on a line through that point). Hence, there is a global upper bound $c_k$ on the number of such (simple) matroids. Since each matroid is fully determined by its simplification and the assignment of its non-loop elements to parallel classes, we obtain the upper bound $1+m'(n,3)\leq c_k (k^2)^n$. It follows that $$\frac{\log (1+m'(n,r))}{  \binom{n}{r}} \leq \frac{\log (1+m(n-r+3,3))}{\binom{n-r+3}{3}}\leq \frac{12\log(k)}{n^2}(1+o(1)).$$ That bound does suffice:

Theorem (Pendavingh, Van der Pol 2015).  For any fixed $k$, we have $$\log m_{Ex(U_{2,k})}(n) \leq O\left(\binom{n}{n/2}/n^2\right)\text{ as } n\rightarrow \infty$$

Hence $\log m_{Ex(U_{2,k})}(n)\leq o(\log m(n))$, and it follows that asymptotically almost all matroids on $n$ elements have $U_{2,k}$ as a minor.

To bound the matroids without $U_{3,6}$ as a minor, it will also suffice to consider simple matroids in base rank 3.

Lemma. There is a constant $n_0$ so that if $M$ is a simple matroid of rank 3 on $E$ without a $U_{3,6}$-minor, and $|E|\geq n_0$, then there are lines $\ell_1$ and $\ell_2$ and a point $p$ of $M$ so that $E= \ell_1\cup\ell_2\cup\{p\}$.

Our shortest argument works for $n_0=56$. You may enjoy improving that constant.

The structural description of the lemma implies a bound on the number of simple matroids without $U_{3,6}$ in rank 3, which again is enough to prove that asymptotically almost all matroids on $n$ elements have $U_{3,6}$ as a minor.

Conjectures

When applying the matroid entropy lemma, a key issue  seems to be the choice of fixed rank $s$ for the base case. The lower we pick $s$, the easier work we have proving the base case, but higher $s$ will give better bounds. And as we found out to our embarrassment, we sometimes need to go to a sufficiently high $s$ before our bounds are any good.

So far we have not ventured beyond base rank $s=3$, which of course comes with an attractive arena of points-and-lines-with-your-favourite-property. We think this perhaps means that the entropy counting lemma has not been used to its full potential. To illustrate,  we offer the following conjectures.

Matroids without the 3-whirl

Conjecture. Asymptotically almost all matroids have the 3-whirl $W^3$ as a minor.

It is a theorem that almost all matroids are 3-connected [OSWW13], and we hazard the guess that most of those 3-connected matroids will have $M(K_4)$ or $W^3$ as a minor. Having $M(K_4)$ as a minor seems strictly more of a `coincidence’ than having $W^3$ as a minor, because $M(K_4)$ has all the hyperplanes of $W^3$, plus one extra. So if at least one of $W^3$ and $M(K_4)$ is a minor of almost all matroids, and the former is more likely than the latter, our conjecture becomes quite believable.

We could not make any sufficient upper bounds on $m_{Ex(W^3)}(n,s)$ in fixed rank $s=3$, but $s=4$ is open.

Matroids without a fixed uniform minor

We have very recently established the following [PvdP16].

Theorem Let $N$ be a uniform matroid. Asymptotically almost all matroids have $N$ as a minor.

The technique we used for this is much more involved than the above entropy method, and its does not give good bounds in fixed rank. The following is open.

Conjecture. Let $N$ be a uniform matroid. For any $c$ there exists an $s$ so that $$\log\left(1+m_{Ex(N)}(n,s)\right) / \binom{n}{s} \leq \frac{c}{n}$$ for all sufficiently large $n$.

If this conjecture is true for any $c<1/2$, this would yield an alternative proof of our theorem.

Oriented matroids

Conjecture Asymptotically almost all matroids are not orientable.

This conjecture may not appeal to all of you. An enumeration of small matroids reveals that the majority is in fact, orientable [MMIB12].

Let $\bar{m}(n,r)$ denote the number of oriented matroids on $E=\{1,\ldots, n\}$ and of rank $r$. There is a perfect analogue of the matroid entropy lemma for oriented matroids, with an entirely analogous proof (you use chirotopes rather than incidence vectors of base sets, otherwise the proof is identical).

Oriented Matroid Entropy Lemma. For all $t \le r$
$$\frac{\log\left(1+\bar{m}(n,r)\right)}{\binom{n}{r}} \le \frac{\log\left(1+\bar{m}(n-t,r-t) \right)}{\binom{n-t}{r-t}}.$$

If $\log \bar{m}(n)\leq (1-\epsilon)\log m(n)$ for sufficiently large $n$, then the number of oriented and hence the number of orientable matroids will be vanishing compared to the number of matroids, which would prove the conjecture. It would suffice to establish:

Conjecture. There is an $s$ and an $c<1/2$ such that $$\frac{\log\left(1+\bar{m}(n,s)\right)}{ \binom{n}{s}} \leq \frac{c}{n}$$ for all sufficiently large $n$.

Except for the constant $c<1/2$, that does not seem too much to ask, given the following theorem [ERS86].

Theorem. For each $s$ there is a $c$ such that $$\frac{\log \bar{m}(n,s)} { \binom{n}{s} }\leq \frac{c}{n}$$ for all sufficiently large $n$.

Note that this theorem already implies that for any fixed $s$, we have $$\log \bar{m}(n,s)\leq o(\log m(n,s))$$ for $n\rightarrow\infty$, since $\log m(n,s)/\binom{n}{s}\sim \log (n)/n$ as $n\rightarrow\infty$.

Finally, a construction due to Felsner and Valtr [FV11] shows that $$\log \bar{m}(n,3)\geq 0.1887 n^2,$$ i.e.  $\log \bar{m}(n,3)/ \binom{n}{3} \geq 1.32/n.$ So base rank $s=3$ will not do, but $s=4$ is open…

References

[AS08] Noga Alon and Joel Spencer, The probabilistic method, 3rd edition.

[BPvdP14] N. Bansal, R.A. Pendavingh, and J.G. van der Pol. An entropy argument for counting matroids. Journal of Combinatorial Theory B, 109:258-262, 2014.

[CFGS86] F. R. K. Chung, R. L. Graham, P. Frankl, and J. B. Shearer. Some intersection theorems for ordered sets and graphs. Journal of Combinatorial Theory A, 43(1):23-37, 1986.

[ERS86] H. Edelsbrunner, J. O’Rourke, and R. Seidel. Constructing arrangements of lines and hyperplanes with applications. SIAM Journal on Computing 15 (2): 341–363, 1986 doi:10.1137/0215024.

[FV11] S. Felsner and P. Valtr. Coding and Counting Arrangements of Pseudolines. Discrete & Computational Geometry, 46:405

[Kee15] P. Keevash. Counting designs.  Arxiv preprint 1504.02909

[MMIB12] Y. Matsumoto, S. Moriyama, H. Imai and D. Bremner. Matroid enumeration for incidence geometry. Discrete and Computational Geometry. Vol. 47, issue 1, pp. 17-43, 2012.

[OSWW13] J. Oxley, C. Semple, L. Warshauer, and D. Welsh. On properties of almost all matroids. Adv. Appl. Math., 50(1):115–124, 2013.

[PvdP15] R.A. Pendavingh and J.G. van der Pol. Counting matroids in minor-closed classes. Journal of Combinatorial Theory B, 111:126–147, 2015.

[PvdP16] R.A. Pendavingh and J.G. van der Pol. On the number of bases in almost all matroids. Arxiv preprint 1602.04763

Matroid Prophet Inequalities and Mechanism Design

Guest post by Bart de Keijzer.

This blog post is about a result in optimal stopping theory that relates to matroids, and an application of this result to mechanism design (a field of game theory).

The Classical Prophet Inequality

In the theory of optimal stopping, we deal with problems where a gambler observes a sequence of unknown and possibly random values, and has to decide when to take a particular action in order to optimize some objective value.  In a previous post, we have already seen the secretary problem, which is an example of a problem studied in optimal stopping theory. In that problem, we face a finite sequence of $n$ numbers, and each time a new number arrives we have to decide irrevocably whether we want to choose that number or not.

I will discuss in this post a slightly different problem from optimal stopping theory, where the permutation is not random, but the numbers are. We are given a sequence $X_1, \ldots, X_n$ of independent non-negative random variables, and the gambler observes this sequence. When he observes a number, he has to make an irrevocable decision about whether or not to stop. If he decides to stop, he receives a payoff equal to the number on which he chose to stop. If he decides not to stop, then the gambler simply moves on to the next number in the sequence. The classical prophet inequality of Krengel, Sucheston, and Garling [4] tells us that the gambler can get a payoff that is half of the expected maximum.

Theorem 1.  If $X_1, \ldots, X_n$ are independent non-negative distributions, then there exists a stopping rule $R$ such that $\mathbf{E}[R(X_1,\ldots,X_n)] \geq \mathbf{E}[\max\{X_i : 1 \leq i \leq n\}]/2$.

The stopping rule $R$ that achieves this particular guarantee is simple: stop at the first value that is at least half of the expected maximum. The name prophet inequality is because it shows that a gambler can achieve a payoff that is at least half of the value that would be picked by a prophet who is completely foresighted. Many variations and generalizations on this result have appeared in the literature. See [2] for an (old) survey.

Sequential Posted Price Mechanisms

We now move to a related scenario that is studied in mechanism design. Suppose that multiple identical products are being sold to a set of $n$ interested buyers. Each buyer is interested in obtaining at most one copy of the item, and each buyer has a valuation for the item that is for sale. The valuation of a buyer $i$ is expressed in terms of a real number which we denote by $v_i$, and is drawn from an independent probability distribution $D_i$. The valuations are privately held by the buyers and the auctioneer does not know them. However, the auctioneer does know the distributions $D_1, \ldots, D_n$.

The auctioneer wants to sell the item through a very simple process called a sequential posted price (SPP) mechanism. This means that the auctioneer has to make take-it-or-leave it offers to the buyers one by one. When a buyer $i$ receives an offer of $p_i$ he can choose to accept it or reject it. If he accepts, the buyer pays price $p_i$ and gets an item. The utility of buyer $i$ is then $v_i – p_i$. If the buyer rejects, he pays nothing, gets no item, and the auctioneer proceeds to the next buyer. The auctioneer makes at most one offer to each buyer and the buyers are assumed to optimize their utility, so that a buyer will accept an offer if and only if his valuation exceeds the price of the offer.

SPP mechanisms are studied because they are an abstraction of a sales mechanism that is frequently encountered in the real world. The popularity of posted price mechanisms is due to its simplicity, its transparency toward the participating buyers, and the efficiency with which it can be implemented.

The question that we are interested in is how well we can approximate the optimal social welfare by means of an SPP mechanism. The social welfare of an allocation is defined as the sum of valuations of all the buyers who get an item. In case there is only one unit for sale, this setting is very similar to the prophet inequality setting, and in fact we can use the prophet inequality to obtain a good approximation to the social welfare. The optimum social welfare is $\mathbf{E}[\max\{v_i : 1 \leq i \leq n\}]$, and the prophet inequality tells us that the auctioneer is able to achieve half of that by offering every buyer a price of $\mathbf{E}[\max\{v_i : 1 \leq i \leq n\}]/2$.

If there is an infinite supply or multiple copies of the item for sale, the original prophet inequality cannot be applied anymore.  Having multiple copies or infinite supply essentially means that we have a different allocation constraint on the set of buyers that we may allocate an item. In these cases the family of sets of buyers that we may allocate is a uniform matroid. Let us be even more ambitious, and assume that we have an arbitrary matroid constraint on the set of buyers that may get an item.

  • Chawla, Hartline, Malec and Sivan [1] prove that in this case there still exists an SPP mechanism $M$ that achieves a $1/2$-approximation to the optimal social welfare. The mechanism they propose assumes that the order in which to make offers to the buyers can be controlled. The way in which $M$ works is as follows.
  • For every bidder $i$ let $r_i$ be the probability that buyer $i$ gets an item in the social-welfare-optimizing allocation. (Note that this allocation is random, because the valuations are random: for every vector of valuations of the buyers there is a (possibly distinct) optimal allocation.) For buyer $i$, set $p_i$ to be the price such that $\mathbf{Pr}[v_i \geq p_i] = r_i$.
  • Iteratively offer the next buyer $i$ a take-it-or-leave it price $p_i$. Make the offers in order of non-increasing $p_i$, and only make $i$ an offer in case allocating them an item will yield an independent set in the matroid.

The following can then be proved.

Theorem 2.  The expected social welfare of $M$ is at least half of the expected optimum social felware.

The above can be seen as a prophet-inequality-type result for a setting where the gambler/auctioneer can select an independent set in a given matroid, instead of only a single item. However, the result requires that the gambler can choose the order of the random variables in advance.

Matroid Prophet Inequalities

Kleinberg and Weinberg [3] strengthen the above result by proving that it is not needed to have control over the order in which to offer the prices to the buyers.
This yields a true generalization of the original prophet inequality and strengthens the above result on SPP mechanisms.

Theorem 3.  Suppose that $X_1, \ldots, X_n$ is a sequence of nonnegative real values, arriving one by one, drawn from independent and non-negative distributions. If there is a matroid constraint $\mathcal{M}$ over the index set of values that may be selected, then there exists a selection rule such that
$\mathbf{E}[\text{ Total value of the selected elements }] \geq \mathbf{E}[\max\{\sum_{i \in I} X_i : I \in \mathcal{M}\}]/2$.

The selection rule that achieves this sets a specific threshold value for each number that arrives, and selects the arriving element if and only if its value exceeds the threshold and the element can be added without violating the matroid constraint. The threshold at iteration $i$ may depend on the numbers that have arrived in previous iterations. The authors prove the existence of the desired threshold values in three steps.

  • They first define the notion of $\alpha$-balancedness, which is a property that a threshold-based selection rule may posess. Let $T_1, \ldots, T_n$ be a set of thresholds, where $T_i$ is the threshold value that is used in the $i$th iteration. Let $A$ be the set of elements that would be selected when using these thresholds, and let $B$ be the random set that a prophet selects (i.e., a basis of the matroid that maximizes the total value after observing the values). Let $R(A)$ be the (also random) subset of $B \subset A$ of maximum total value such that $A \cup R(A)$ is a basis. The threshold rule is $\alpha$-balanced iff: (i.) For every realization of $T_1, \ldots, T_n$, the total threshold corresponding to the values in $A$ is at least $1/\alpha$ times the expected total value of the elements in $B \setminus R(A)$. Informally this means that the value of the set of elements that a foresighted prophet selects instead of $A$ is within a $1/\alpha$ factor of the set selected by the threshold selection rule.
    (ii.) For every realization of $T_1, \ldots, T_n$, let $V$ be any set disjoint from $A$ such that $A \cup V$ is a matroid basis. Then the total threshold corresponding to the values in $V$ must be at most $(1 – 1/\alpha)$ times the expected total value of $R(A)$. Informally, this means that the total weight of the elements rejected by the threshold rule is small (not more than a $(1 – 1/\alpha)$ times the value of the set $R(A)$ that a prophet would add in expectation).
  • They then prove that using $\alpha$-balanced thresholds yields a selection rule that achieves an expected value within $1/\alpha$ times the expected optimum value.
  • Finally they prove that there exists $2$-balanced thresholds. The threshold for the $i$th value $T_i$ is set to $\frac{1}{2}\mathbf{E}[w(R(A_{i-1})) – w(R(A_{i-1} \cup \{i\}))]$. Note that these thresholds are actually adaptive: the way $T_i$ is set depends on the set that was selected among the first $i-1$ elements.

References

[1] Shuchi Chawla, Jason D. Hartline, David L. Malec, and Balasubramanian Sivan. Multi-parameter mechanism design and sequential posted pricing. In Proceedings of the Forty-second ACM Symposium on Theory of Computing (STOC), pages 311–320. ACM, 2010.

[2] Theodore P. Hill and Robert P. Kertz. A survey of prophet inequalities in optimal stopping theory. Contemporary Mathematics, 125, 1992.

[3] Robert Kleinberg and Seth Matthew Weinberg. Matroid prophet inequalities. In Proceedings of the Forty-fourth ACM Symposium on Theory of Computing (STOC), pages 123–136. ACM.

[4] Ulrich Krengel and Louis Sucheston. On semiamarts, amarts, and processes with finite value. Advances in Probability Related Topics.