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, October 2011, 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

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.

Guest post by Cameron Marcott

The goal of this post is to introduce flag manifolds and common decompositions of them, and to explain how matroids serve as combinatorial models for these geometric objects. We illustrate how decompositions of flag manifolds can provide examples of interesting classes of Coxeter matroids. We shall also make effort to point out several matroidal facts which are direct translations of geometric facts. Over the course of this post, we will explain the following correspondences between geometric and matriodal objects.
$$\begin{array}{c|c}
\mathbf{geometry} & \mathbf{matroids} \\ \hline\hline
\mbox{points in } \mathrm{Gr}(k,n) & \mbox{rank-$k$, $\mathbb{R}$-representable matroids} \\\hline
\mbox{Schubert cells} & \mbox{nested matroids} \\\hline
\mbox{Richardson cells} & \mbox{lattice path matroids} \\\hline
\mbox{positroid cells} & \mbox{positroids} \\\hline
\mbox{points in } \mathrm{F}\ell(n) & \mbox{$\mathbb{R}$-representable full flag matroids}
\end{array}$$

1. The Grassmannian

The Grassmannian $\mathrm{Gr}(k,n)$ is the geometric object whose points are $k$-dimensional vector subspaces of $\mathbb{R}^n$. Any $k$-dimensional subspace of $\mathbb{R}^n$ may be interpreted as the row space of a full rank $k \times n$ matrix. Such a matrix represents a matroid in the usual fashion. Hence, any point in $\mathrm{Gr}(k,n)$ naturally represents a rank-$k$ matroid (two $k \times n$ matrices have the same row span if and only if they are related by elementary row operations, and elementary row operations preserve the matroid represented by a matrix, so this correspondence is well defined).

A common technique to study the geometry of $\mathrm{Gr}(k,n)$ is to decompose it into simpler geometric spaces. One may think of all these decompositions fancy versions of the familiar decomposition of the projective line into a line and a point at infinity. The most common of these decompositions is the Schubert decomposition. Of all of the matrices representing a given point in $\mathrm{Gr}(k,n)$, there is a unique representative in reduced row echelon form. A Schubert cell consists of all of the points in $\mathrm{Gr}(k,n)$ whose reduced row echelon representative has a fixed shape.

Definition 1. Given a set $S \in \binom{[n]}{k}$, the Schubert cell $X_{S}$ consists of all $V \in \mathrm{Gr}(k,n)$ which are the row space of a $k \times n$ matrix whose set of pivot columns is $S$ when written in reduced row echelon form.

Choosing a generic point in a Schubert cell $X_{S}$ and asking what matroid it represents, one always expects to see the same matroid (more rigorously, a dense open subset of $X_{S}$ represents the same matroid). To see what this matroid is, consider the partial order on $\binom{[n]}{k}$ where if $S = \{s_1 < s_2 < \cdots < s_k\}$ and $T = \{t_1 < t_2 < \cdots < t_k\}$, then $S \leq T$ if and only if $s_i \leq t_i$ for each $i$. Looking at a matrix representing a point in $X_{S}$, any set of columns indexed by $T$ with $S \nleq T$ will certainly be linearly dependent. Any other set of columns, we expect to be linearly independent (the vanishing of the square determinant indexed by a set of columns carves out a subset of the Schubert cell of dimension strictly lower than that of the Schubert cell, the compliment of this lower dimensional set is dense in the Schubert cell and is hence “generic”, the set of columns under consideration is thus linearly independent at a generic point). Hence, the matroid associated to a generic point in $X_{S}$ has basis set $\left\{ B \in \binom{[n]}{k} : S \leq B \right\}$. These matroids have been studied under the names “shifted matroids” or “nested matroids.”

Example 2. Let $n = 6$, $k = 3$, and $S = \{1,2,4\}$. Then, $X_{S}$ consists of all matrices of the form $$\left( \begin{array}{cccccc}
1 & 0 & \ast & 0 & \ast & \ast \\
0 & 1 & \ast & 0 & \ast & \ast \\
0 & 0 & 0 & 1 & \ast & \ast
\end{array}\right),$$ where the asterisks may be filled in with any real number. Filling in the asterisks randomly, we expect any set of three columns aside from $\{1,2,3\}$ to be linearly independent. Hence, a generic point in $X_{S}$ represents the matroid whose bases are all three element subsets of $[6]$ which are $\geq \{1,2,4\}$.

A common refinement of the Schubert decomposition is the Richardson decomposition. The opposite reduced row echelon form of a matrix is the matrix one gets by performing Gaussian elimination starting at the rightmost column and working their way left, as a left handed person, or Hebrew speaker might be tempted to do. The opposite Schubert cell $X^{T}$ consists of the points in $\mathrm{Gr}(k,n)$ whose unique opposite reduced row echelon representative has pivot columns indexed by the set $T$. Finally, the Richardson cell $X^{T}_{S}$ is defined to be the intersection $X^T \cap X_S$.

Just as generic points in Schubert cells defined a class of matroids, generic points in Richardson cells define their own class of matroids. The matroid associated to a generic point in $X^{T}_{S}$ has basis set $\left\{ B \in \binom{[n]}{k} : S \leq B \leq T \right\}$. These matroids were introduced and studied independent of this geometric motivation under the name of lattice path matroids.

Example 3. Let $n = 6$, $k = 3$, $S = \{1,2,4\}$, and $T = \{4,5,6\}$. Then, the matroid defined by a generic point in $X^{T}_{S}$ has bases
$$\left\{ B \in \binom{[n]}{k} : \{1,2,4\} \leq B \leq \{4,5,6\} \right\}.$$ This matroid is exactly the same as the matroid from Example 2. In general, all shifted matroids are also lattice path matroids. This fact mirrors the geometric fact that all Schubert varieties are also Richardson varieties (Schubert and Richardson varieties are the closure of Schubert and Richardson cells respectively).

At this point, it might be tempting to try to decompose the Grassmannian into cells where each cell consists all of the points representing a given matroid. This decomposition is known as the “thin Schubert decomposition,” or “GGMS decomposition” (after Gelfand, Goresky, MacPherson, and Serganova). While the idea is appealing, this decomposition turns out to be a geometric nightmare. Mnev’s universality theorem says roughly that these cells can be as poorly behaved as any real semialgebraic set (a set carved out of $\mathbb{R}^n$ by a set of polynomial equations and inequalities). This universality theorem has inspired, among other things, “Murphy’s law” results by Vakil, the name of which should give a sense of how poorly behaved GGMS cells can be.

Our final example of a class of matroids associated to a decomposition of the Grassmannian are positroids, which provide a geometrically tractable, but still matroidal, refinement of both the Schubert and Richardson decompositions. Though it is not perspective we take, we mention that the name positroid comes from the fact positroids are exactly the matroids representable by a $k \times n$ real matrix where every $k \times k$ minor is non-negative. To define a positroid cell, one starts by specifying which reduced row echelon shape a matrix representing a point in the positroid cell should have, just as with defining a Schubert cell. Then, one cyclically rotates the columns so they are now ordered $2,3,\dots, n,1$ instead of $1,2, \dots, n$ and specifics which reduced row echelon shape the matrix should have with this new basis ordering. One repeats this process, specifying a reduced row echelon shape for every cyclic rotation of $1,2,\dots,n$. The set of points in $\mathrm{Gr}(k,n)$ obeying these restrictions is called a positroid cell. Positroid cells are indexed by families of $n$ sets $(S_1, S_2, \dots, S_n)$ obeying a set of restrictions coming from the fact that it must be possible for a $k \times n$ matrix to have pivot columns $S_i$ after applying the $i$th cyclic rotation to its columns for every $i$ ($n$-tuples of sets obeying these restrictions are called Grassmann necklaces). Positroids may then be defined to be the matroids represented by generic points in positroid cells.

Example 4. Let $n = 6$. We write sets without curly brackets or commas to save on space. Consider the 6-tuple of sets
$$\mathcal{S} = (124,234,346,456,562,612).$$ Consider a matrix representing a generic point in postroid variety defined by $\mathcal{S}$. Since it has pivot columns 124 in the standard basis ordering, we expect every set aside from 123 to be independent, as in Example 2. Cyclically rotating the columns of our matrix and writing it in reduced row echelon form, the pivot columns are now 234 (the first, second and third columns in our new ordering). From this data, we have no reason to believe any set of three columns should be dependent. Rotating again, the pivot columns are now 346 (the first, second, and fourth columns). From this data, we see that 345 joins 124 as a dependent set, and we still have no reason to believe any other three element subset is dependent. Continuing in this way, we see that the 3-element dependent sets of the matroid defined by a generic point in this positroid variety are exactly $\{123,345,561\}$. So, the positroid is the rank-3 whirl, $\mathcal{W}^3$. It can be checked that this matroid is not a lattice path matroid. It is an interesting exercise to show that all lattice path matroids are positroids (mirroring the geometric fact that Richardson varieties are positroid varieties). As this example demonstrates, the converse does not hold.

2. The full flag manifold

The Grassmannian is the simplest example of a class of manifolds known as flag manifolds. Given a construction on the Grassmannian, one of the first questions asked by a geometer working in this area is “Does this construction generalize to other flag manifolds?” For the sake of this post, we will focus on generalizing the constructions from the previous section to the full flag manifold $\mathrm{F}\ell(n)$. Just as matroids served as a combinatorial model for points in $\mathrm{Gr}(k,n)$, full flag matroids will serve as a combinatorial model for points in $\mathrm{F}\ell(n)$. In general, the combinatorial model for points in other flag varieties are Coxeter matroids. Other flag manifolds come with Schubert and Richardson stratifications similar to the one described above, and tractable classes of Coxeter matroids could be obtained by studying the Coxeter matroids associated to these stratifications. For now, we play this game just for $\mathrm{F}\ell(n)$ and full flag matroids. However, it should be possible to find well behaved classes of Lagrangian matroids by considering Schubert cells in Lagrangian Grassmannians, classes of orthogonal matroids by considering Schubert cells in orthogonal Grassmannians, etc..

Flag manifolds generalize Grassmannians. The full flag manifold $\mathrm{F}\ell(n)$ is the space whose points are flags of subspaces $\{0\} = V_0 \subset V_1 \subset \cdots \subset V_n = \mathbb{R}^n$. This space may profitably be thought of as the subspace of $$\mathrm{Gr}(0,n) \times \mathrm{Gr}(1,n) \times \cdots \times \mathrm{Gr}(n,n)$$ consisting of points $(V_0, V_1, \dots, V_n)$ such that $V_i$ is a subspace of $V_j$ for all $i \leq j$. Just as points in $\mathrm{Gr}(k,n)$ were represented by $k \times n$ matrices, points in $\mathrm{F}\ell(n)$ may be represented by full rank $n \times n$ matrices where $V_1$ is the span of the first row, $V_2$ span of the first two rows, and so on. Just as two $k \times n$ matrices represent the same point in $\mathrm{Gr}(k,n)$ if and only if they are related by elementary row operations, two $n \times n$ matrices represent the same point in $\mathrm{F}\ell(n)$ if and only if they are related by the action of an upper triangular matrix. There is a natural projection from $\mathrm{F}\ell(n)$ to $\mathrm{Gr}(k,n)$ which sends a flag to its $k$-dimensional component.

Now, we wish to find a combinatorial object which plays the same role for $\mathrm{F}\ell(n)$ that matroids play for $\mathrm{Gr}(k,n)$. Since $$\mathrm{F}\ell(n) \subseteq \mathrm{Gr}(0,n) \times \mathrm{Gr}(1,n) \times \cdots \times \mathrm{Gr}(n,n),$$ our combinatorial object should consist of a subset of tuples $(\mathcal{M}_0, \mathcal{M}_1, \dots, \mathcal{M}_n)$ where $\mathcal{M}_i$ is a rank $i$ matroid for each $i$. Consider the restriction that for all $i < j$ that $V_i$ is a subspace of $V_j$. Given a linearly dependent set of points in $V_j$, we may project it to $V_i$. The set of points remains linearly dependent after preforming this projection. On the matriodal level, this fact tells us that any cycle of $\mathcal{M}_j$ should also be a cycle of $\mathcal{M}_i$. That is, $\mathcal{M}_i$ is a quotient of $\mathcal{M}_j$. This observation inspires the definition of a full flag matroid. Definition 5. A full flag matroid is a collection $(\mathcal{M}_0, \mathcal{M}_1, \dots, \mathcal{M}_n)$ such that for any $0 \leq i \leq n$ and any $j > i$, $\mathcal{M}_i$ is a rank $i$ matroid on the ground set $[n]$ and $\mathcal{M}_i$ is a quotient of $\mathcal{M}_j$.

When working with flag matroids, rather than thinking of bases, we think of flags of sets $\emptyset = B_0 \subset B_1 \subset \cdots \subset B_n = [n]$ such that $B_k$ is a basis of $\mathcal{M}_k$ for each $i$. We use the short hand $B_{\bullet}$ to denote a flag of sets. By a minor abuse of language, we call these flags $B_{\bullet}$ the bases of the flag matroid. Flags of sets will be represented by permutations by the map (for example): $$214365 \mapsto \emptyset \subset \{2\} \subset \{1,2\} \subset \{1,2,4\} \subset \cdots \subset \{1,2,3,4,5,6\}.$$ Any flag matroid $(\mathcal{M}_0, \mathcal{M}_1, \dots, \mathcal{M}_n)$ may be projected to the rank-$k$ matroid $\mathcal{M}_k$. Thinking in terms of bases, one may verify that the bases of $\mathcal{M}_k$ are exactly the $k$-element sets that occur as the $k$ element component of some basis of the flag matroid $B_{\bullet}$.

Points in $\mathrm{F}\ell(n)$ represent full flag matroids in a way analogous to the way that points in $\mathrm{Gr}(k,n)$ represent matroids. So, any point in $\mathrm{F}\ell(n)$ represents the full flag matroid, whose elements are flags of sets $B_{\bullet}$ such that $B_i$ is a basis of the matroid defined by $F_i$ for each $i$.

Just like the Grassmannian, $\mathrm{F}\ell(n)$ comes with Schubert and Richardson stratifications. The descriptions of Schubert and Richardson cells in $\mathrm{F}\ell(n)$, while not terribly difficult, is a little hard to absorb for a blog post. So, we just define the flag matroids associated to generic points in these spaces. The interested reader may find descriptions of the geometric spaces in [KLS13].

Let $\sigma$ be a permutation representing the flag $S_{\bullet}$. Just as the matroids associated to Schubert varieties in $\mathrm{Gr}(k,n)$ were given by taking all sets larger than a certain set in a given partial order, the flag matroid associated to the Schubert variety $X_{\sigma}$ in $\mathrm{F}\ell(n)$ will consist of all flags larger than $S_{\bullet}$ in a certain partial order. Specifically, we say that $B_{\bullet} \geq_{\bullet} S_{\bullet}$ if and only if $B_j \geq S_j$ in the partial order on sets for each $0 \leq j \leq n$. On permutations, this partial order is known as the Bruhat order.

Definition 6. Let $\sigma$ be a permutation representing a flag $S_{\bullet}$. The Schubert flag matroid $\mathcal{M}_{\sigma}$ associated to $\sigma$ has basis set $\left\{B_{\bullet}: S_{\bullet} \leq_{\bullet} B_{\bullet}\right\}$.

Example 7. Let $\sigma = 214365$. Then, $\mathcal{M}_{\sigma} = \left\{B_{\bullet}: 214365 \leq_{\bullet} B_{\bullet}\right\}$. For instance, $431652 \in \mathcal{M}_{\sigma}$ because $\{4\} \geq \{2\},$ $\{3,4\} \geq \{1,2\}$, $\{1,3,4\} \geq \{1,2,3\}$, etc.. However, $324516 \notin \mathcal{M}_{\sigma}$ because $\{1,2,3,4,5\} \ngeq \{1,2,3,4,6\}$. It is a simple exercise to check that the projection of $\mathcal{M}_{\sigma}$ onto its rank-3 component is exactly the shifted matroid from Example 3. In general, projections of Schubert flag matroids are always shifted matroids and all shifted matroids are obtained in this way. This fact is a shadow of the geometric fact that projections of Schubert varieties in $\mathrm{F}\ell(n)$ are Schubert varieties in $\mathrm{Gr}(k,n)$.

In analogy to what we expect from Grassmannians/matroids, Richardson flag matroids are obtained by taking all flags larger than a fixed flag $S_{\bullet}$ and smaller than a fixed flag $T_{\bullet}$.

Definition 8. Let $\sigma, \tau$ be a permutations representing flags $S_{\bullet}$ and $T_{\bullet}$ respectively such that $T_{\bullet} \geq_{\bullet} S_{\bullet}$. The Richardson flag matroid $\mathcal{M}^{\tau}_{\sigma}$ has basis set $\left\{B_{\bullet}: S_{\bullet} \leq_{\bullet} B_{\bullet} \leq_{\bullet} T_{\bullet} \right\}$.

Example 9. Let $\sigma = 214365$ and $\tau = 456123$. Then, $$\mathcal{M}^{\tau}_{\sigma} = \left\{B_{\bullet}: 214365 \leq_{\bullet} B_{\bullet}\leq_{\bullet} 456123\right\}.$$ For instance, $324165 \in \mathcal{M}^{\tau}_{\sigma}$. However, $324615 \notin \mathcal{M}^{\tau}_{\sigma}$ because $\{2,3,4,6\} \nleq \{1,4,5,6\}$.

Consider the projection of $\mathcal{M}^{\tau}_{\sigma}$ to its rank-3 component. Naively, one might conjecture that projections of Richardson flag matroids will be lattice path matroids. However, this example will illustrate that this is not the case. The set $\{1,2,3\}$ cannot appear as the rank-3 component of any flag in $\mathcal{M}^{\tau}_{\sigma}$ because $\{1,2,3\} \ngeq \{1,2,4\}$. Consider the set $\{3,4,5\}$. If this is to appear as the rank-3 component of a flag, the rank-4 component must be $\{1,3,4,5\}$ because the rank-4 component must be $\leq \{1,4,5,6\}$. Then, the rank-5 component must be $\{1,2,3,4,5\}$ becuase the rank-5 component must be $\leq \{1,2,4,5,6\}$. However, this contradicts the requirement that the rank-5 component be $\geq \{1,2,3,4,6\}$ and hence $\{3,4,5\}$ is not the rank-3 component of any flag in $\mathcal{M}^{\tau}_{\sigma}$. A similar exercise shows that $\{1,5,6\}$ also cannot appear as the rank-3 component of any flag in $\mathcal{M}^{\tau}_{\sigma}$. Any other 3 element subset appears as the rank-3 component of some flag in $\mathcal{M}^{\tau}_{\sigma}$ and hence the projection of $\mathcal{M}^{\tau}_{\sigma}$ to a rank-3 matroid is exactly $\mathcal{W}^3$, the positroid from Example 4.

This somewhat surprising fact is illustrative a more general theorem, which is a direct combinatorial analog of a geometric theorem appearing in [KLS13].

Theorem 10. Let $\sigma, \tau$ be a permutations representing flags $S_{\bullet}$ and $T_{\bullet}$ respectively such that $S_{\bullet} \leq_{\bullet} T_{\bullet}$. Then, the projection of $\mathcal{M}^{\tau}_{\sigma}$ to a rank-$k$ matroid is a positroid. All positroids arise in this fashion.

To recap: We saw that representable matroids can be viewed as combinatorial fingerprints of points in Grassmannians and that common stratifications of the Grassmannian are associated to well studied classes of matroids. In analogy, representable Coxeter matroids can be viewed as combinatorial fingerprints of points in flag manifolds. The Coxeter matroids associated to stratifications of these flag manifolds should represent nice classes of examples. Further, we saw that several matriodal facts can be recovered nearly for free as discrete analogs of geometric phenomena.

[KLS13] Allen Knutson, Thomas Lam, and David Speyer. Positroid Varieties: Juggling and Geometry. Composito Mathematica, 149(10):1710-1752, 2013.

Guest post by June Huh

I will write about a common algebraic structure hidden behind seemingly distant objects: convex polytopes, Kähler manifolds, projective varieties, and lastly, matroids. Let $n$ be a positive integer.

1. Polytopes

1.1

A polytope in $\mathbb{R}^n$ is the convex hull of a finite subset of $\mathbb{R}^n$. Let’s write $\Pi$ for the abelian group with generators $[P]$, one for each polytope $P \subseteq \mathbb{R}^n$, which satisfy the following relations:

1. $[P_1 \cup P_2]+[P_1 \cap P_2]=[P_1]+[P_2]$ whenever $P_1 \cup P_2$ is a polytope,
2. $[P+t]=[P]$ for every point $t$ in $\mathbb{R}^n$, and
3. $[\varnothing]=0$.

This is the polytope algebra of McMullen [McM89]. The multiplication in $\Pi$ is defined by the Minkowski sum
\[
[P_1] \cdot [P_2]=[P_1+P_2],
\]
and this makes $\Pi$ a commutative ring with $1=[\text{point}]$ and $0=[\varnothing]$.

The structure of $\Pi$ can be glimpsed through some familiar translation invariant measures on the set of polytopes. For example, the Euler characteristic shows that there is a surjective ring homomorphism
\[
\chi:\Pi \longrightarrow \mathbb{Z}, \qquad [P] \longmapsto \chi(P),
\]
and the Lebesgue measure on $\mathbb{R}^n$ shows that there is a surjective group homomorphism
\[
\text{Vol}:\Pi \longrightarrow \mathbb{R}, \qquad [P] \longmapsto \text{Vol}(P).
\]
A fundamental observation is that some power of $[P]-1$ is zero in $\Pi$ for every nonempty polytope $P$. Since every polytope can be triangulated, it is enough to check this when the polytope is a simplex. In this case, a picture drawing for $n=0,1,2,$ and if necessary $3$, will convince the reader that
\[
([P]-1)^{n+1}=0.
\]
The kernel of the Euler characteristic $\chi$ turns out to be torsion free and divisible. Thus we may speak about the logarithm of a polytope in $\Pi$ which satisfies the usual rule
\[
\text{log}[P_1+P_2]=\text{log}[P_1]
+\text{log}[P_2].
\]
The notion of logarithm leads to a remarkable identity concerning volumes of convex polytopes.

Theorem
Writing $\texttt{p}$ for the logarithm of $[P]$, we have
\[
\text{Vol}(P)=\frac{1}{n!}\text{Vol} (\texttt{p}^n).
\]

This shows that, more generally, Minkowski’s mixed volume of polytopes $P_1,\ldots,P_n$ can be expressed in terms of the product of the corresponding logarithms $\texttt{p}_1,\ldots,\texttt{p}_n$:
\[
\text{Vol}(P_1,\ldots,P_n)=\frac{1}{n!} \text{Vol}(\texttt{p}_1 \cdots \texttt{p}_n).
\]

1.2

Let’s write $P_1 \preceq P_2$ to mean that $P_1$ is a Minkowski summand of some positive multiple of $P_2$. This relation is clearly transitive. We way that $P_1$ and $P_2$ are equivalent when
\[
P_1 \preceq P_2 \preceq P_1.
\]
Let $\mathscr{K}(P)$ be the set of all polytopes equivalent to a given polytope $P$. The collection $\mathscr{K}(P)$ is a convex cone in the sense that
\[
P_1, P_2 \in \mathscr{K}(P) \Longrightarrow \lambda_1 P_1 + \lambda_2 P_2 \in \mathscr{K}(P) \ \ \text{for positive real numbers $\lambda_1, \lambda_2$.}
\]
We will meet an analogue of this convex cone in each of the following sections.

Definition
For each positive integer $q$, let $\Pi^q(P) \subseteq \Pi$ be the subgroup generated by all elements of the form
\[
\texttt{p}_1\texttt{p}_2 \cdots \texttt{p}_q,
\]
where $\texttt{p}_i$ is the logarithm of a polytope in $\mathscr{K}(P)$.

Note that any two equivalent polytopes define the same set of subgroups of $\Pi$. These subgroups are related to each other in a surprising way when $P$ is an $n$-dimensional simple polytope; this means that every vertex of the polytope is contained in exactly $n$ edges.

Theorem [McM93]
Let $\texttt{p}$ be the logarithm of a simple polytope in $\mathscr{K}(P)$, and let $1 \le q \le \frac{n}{2}$.

1. Hard Lefschetz theorem: The multiplication by $\texttt{p}^{n-2q}$ defines an isomorphism
   \[
   \Pi^{q}(P) \longrightarrow \Pi^{n-q}(P), \quad x \longmapsto \texttt{p}^{n-2q} x.
   \]
2. Hodge-Riemann relations: The multiplication by $\texttt{p}^{n-2q}$ defines a symmetric bilinear form
   \[
   \Pi^{q}(P) \times \Pi^{q}(P) \longrightarrow \mathbb{R}, \quad (x_1,x_2) \longmapsto (-1)^q \ \text{Vol}\big(\texttt{p}^{n-2q} x_1 x_2\big)
   \]
   that is positive definite when restricted to the kernel of the multiplication by $\texttt{p}^{n-2q+1}$.

In fact, the group $\Pi^q(P)$ can be equipped with the structure of a finite dimensional real vector space in a certain natural way, and the isomorphism between groups in the first part of the theorem turns out to be an isomorphism between vector spaces.

I will mention two concrete implications of geometric-combinatorial nature, one for each of the above two statements.

1. The first statement is the main ingredient in the proof of the $g$-conjecture for simple polytopes [Stan80]. This gives a numerical characterization of sequences of the form
   \[
   f_0(P),f_1(P),\ldots,f_n(P),
   \]
   where $f_i(P)$ is the number of $i$-dimensional faces of an $n$-dimensional simple polytope $P$.
2. The second statement, in the special case $q=1$, is essentially equivalent to the Aleksandrov-Fenchel inequality on mixed volumes of convex bodies:
   \[
   \text{Vol}(\texttt{p}_1\texttt{p}_1 \texttt{p}_3 \cdots \texttt{p}_n) \text{Vol}(\texttt{p}_2\texttt{p}_2 \texttt{p}_3 \cdots \texttt{p}_n) \le \text{Vol}(\texttt{p}_1\texttt{p}_2 \texttt{p}_3 \cdots \texttt{p}_n)^2.
   \]
   The inequality played a central role in the proof of the van der Waerden conjecture that the permanent of any doubly stochastic $n \times n$ nonnegative matrix is at least $n!/n^n$. An interesting account on the formulation and the solution of the conjecture can be found in [vLin82].

With suitable modifications, the hard Lefschetz theorem and the Hodge-Riemann relations can be extended to polytopes that are not necessarily simple [Karu04].

2. Kähler manifolds

2.1

Let $\omega$ be a Kähler form on an $n$-dimensional compact complex manifold $M$. This means that $\omega$ is a smooth differential $2$-form on $M$ that can be written locally in coordinate charts as
\[
i \partial \overline{\partial} f
\]
for some smooth real functions $f$ whose complex Hessian matrix $\Big[\frac{\partial^2 f}{\partial z_i\partial \overline{z}_j}\Big]$ is positive definite; here $z_1,\ldots,z_n$ are holomorphic coordinates and $\partial$, $\overline{\partial}$ are the differential operators
\[
\partial=\sum_{k=1}^n \frac{\partial}{\partial z_k} dz_k, \qquad \overline{\partial}=\sum_{k=1}^n \frac{\partial}{\partial \overline{z}_k} d\overline{z}_k.
\]
Like all other good definitions, the Kähler condition has many other equivalent characterizations, and we have chosen the one that emphasizes the analogy with the notion of convexity.

To a Kähler form $\omega$ on $M$, we can associate a Riemannian metric $g$ on $M$ by setting
\[
g(u,v)=w(u,Iv),
\]
where $I$ is the operator on tangent vectors of $M$ that corresponds to the multiplication by $i$. Thus we may speak of the length, area, etc., on $M$ with respect to $\omega$.

Theorem
The volume of $M$ is given by the integral
\[
\text{Vol}(M)=\frac{1}{n!} \int_M w^n.
\]
More generally, the volume of a $d$-dimensional complex submanifold $N \subseteq M$ is given by
\[
\text{Vol}(N)=\frac{1}{d!} \int_N w^d.
\]

Compare the corresponding statement of the previous section that $\text{Vol}(P)=\frac{1}{n!}\text{Vol} (\texttt{p}^n)$.

2.2

Let $\mathscr{K}(M)$ be the set of all Kähler forms on $M$. The collection $\mathscr{K}(M)$ is a convex cone in the sense that
\[
\omega_1, \omega_2 \in \mathscr{K}(M) \Longrightarrow \lambda_1 \omega_1 + \lambda_2 \omega_2 \in \mathscr{K}(M) \ \ \text{for positive real numbers $\lambda_1, \lambda_2$.}
\]
This follows from the fact that the sum of two positive definite matrices is positive definite.

Definition
For each nonnegative integer $q$, let $H^{q,q}(M) \subseteq H^{2q}(M,\mathbb{C})$ be the subset of all the cohomology classes of closed differential forms that can be written in local coordinate charts as
\[
\sum f_{k_1,\ldots,k_q,l_1,\ldots,l_q} dz_{k_1} \wedge \cdots \wedge dz_{k_q} \wedge d\overline{z}_{l_1} \wedge \cdots \wedge d\overline{z}_{l_q}.
\]

Note that the cohomology class of a Kähler form $\omega$ is in $H^{1,1}(M)$, and that
\[
[\varphi] \in H^{q,q}(M) \Longrightarrow [\omega \wedge \varphi] \in H^{q+1,q+1}(M).
\]

Theorem (Classical)
Let $\omega$ be an element of $\mathscr{K}(M)$, and let $q$ be a nonnegative integer $\le \frac{n}{2}$.

1. Hard Lefschetz theorem: The wedge product with $\omega^{n-2q}$ defines an isomorphism
   \[
   H^{q,q}(M) \longrightarrow H^{n-q,n-q}(M), \quad [\varphi] \longmapsto [\omega^{n-2q} \wedge \varphi].
   \]
2. Hodge-Riemann relations: The wedge product with $\omega^{n-2q}$ defines a Hermitian form
   \[
   H^{q,q}(M) \times H^{q,q}(M) \longrightarrow \mathbb{C}, \quad (\varphi_1,\varphi_2) \longmapsto (-1)^q \int_M \omega^{n-2q} \wedge \varphi_1 \wedge \overline{\varphi_2}
   \]
   that is positive definite when restricted to the kernel of the wedge product with $\omega^{n-2q+1}$.

Analogous statements hold for $H^{q_1,q_2}(M)$ with $q_1 \neq q_2$, and these provide a way to show that certain compact complex manifolds cannot admit any Kähler form. For deeper applications, see [Voi10].

3. Projective varieties

3.1

Let $k$ be an algebraically closed field, and let $\mathbb{P}^m$ be the $m$-dimensional projective space over $k$. A projective variety over $k$ is a subset of the form
\[
X=\{h_1=h_2=\ldots=h_k=0\} \subseteq \mathbb{P}^m,
\]
where $h_i$ are homogeneous polynomials in $m+1$ variables. One can define the dimension, connectedness, and smoothness of projective varieties in a way that is compatible with our intuition when $k=\mathbb{C}$. One can also define what it means for a map between two projective varieties, each living in two possibly different ambient projective spaces, to be algebraic.

Let $K$ be another field, not necessarily algebraically closed but of characteristic zero. A Weil cohomology theory with coefficients in $K$ is an assignment
\[
X \longmapsto H^*(X)=\bigoplus_k H^k(X),
\]
where $X$ is a smooth and connected projective variety over $k$ and $H^*(X)$ is a graded-commutative algebra over $K$. This assignment is required to satisfy certain rules similar to those satisfied by the singular cohomology of compact complex manifolds, such as functoriality, finite dimensionality, Poincar&eacute duality, K&uumlnneth formula, etc. For this reason the product of two elements in $H^*(X)$ will be written
\[
\xi_1 \cup \xi_2 \in H^*(X).
\]
For algebraic geometers, the most important of the rules is that to every codimension $q$ subvariety $Y \subseteq X$ there be a corresponding cohomology class
\[
\text{cl}(Y) \in H^{2q}(X).
\]
These classes should have the property that, for example,
\[
\text{cl}(Y_1 \cap Y_2)=\text{cl}(Y_1) \cup \text{cl}(Y_2)
\]
whenever $Y_1$ and $Y_2$ are subvarieties intersecting transversely, and that
\[
\text{cl}(H_1)=\text{cl}(H_2)
\]
whenever $H_1$ and $H_2$ are two hyperplane sections of $X \subseteq \mathbb{P}^m$. Though not easy, it is possible to construct a Weil cohomology theory for any $k$ for some $K$. For example, when both $k$ and $K$ are the field of complex numbers, one can take the de Rham cohomology of smooth differential forms.

Definition
For each nonnegative integer $q$, let $A^q(X) \subseteq H^{2q}(X)$ be the set of rational linear combinations of cohomology classes of codimension $q$ subvarieties of $X$.

One of the rules for $H^*(X)$ implies that, if $n$ is the dimension of $X$, there is an isomorphism
\[
\text{deg}: A^n(X) \longrightarrow \mathbb{Q}
\]
determined by the property that
\[
\text{deg}(\text{cl}(\text{p}))=1 \ \ \text{for every} \ \ \text{p} \in X.
\]
Writing $h$ for the class in $A^1(X)$ of any hyperplane section of $X \subseteq \mathbb{P}^m$, the degree of $X \subseteq \mathbb{P}^m$ satisfies the formula
\[
\text{deg}(X \subseteq \mathbb{P}^m)=\text{deg}(h^n),
\]
the number of points in the intersection of $X$ with a sufficiently general subspace $\mathbb{P}^{m-n} \subseteq \mathbb{P}^m$. Compare the corresponding statements of the previous sections
\[
\text{Vol}(P)=\frac{1}{n!}\text{Vol} (\texttt{p}^n) \quad \text{and} \quad \text{Vol}(M)=\frac{1}{n!} \int_M w^n.
\]

3.2

Let $\mathscr{K}(X)$ be the set of cohomology classes of hyperplane sections of $X$ under all possible embeddings of $X$ into projective spaces. Classical projective geometers knew that $\mathscr{K}(X)$ is a convex cone in a certain sense; if you are curious, read about the Segre embedding and the Veronese embedding.

Conjecture (Grothendieck)
Let $h$ be an element in $\mathscr{K}(X)$, and let $q$ be a nonnegative integer $\le n/2$.

1. Lefschetz standard: The multiplication by $h^{n-2q}$ defines an isomorphism
   \[
   A^q(X) \longrightarrow A^{n-q}(X), \quad \xi \longmapsto h^{n-2q} \cup \xi.
   \]
2. Hodge standard: The multiplication by $h^{n-2q}$ defines a symmetric bilinear form
   \[
   A^q(X) \times A^q(X) \longrightarrow \mathbb{Q}, \quad (\xi_1,\xi_2) \longmapsto (-1)^q \text{deg}\big(h^{n-2q} \cup \xi_1 \cup \xi_2\big),
   \]
   that is positive definite when restricted to the kernel of the cup product with $h^{n-2q+1}$.

The above statements are at the core of Grothendieck’s approach to Weil’s conjecture on zeta functions and other important problems in algebraic geometry [Gro69].

4. Matroids

4.1

As we know, a matroid $\mathrm{M}$ is given by a closure operator defined on all subsets of a finite set $E$ satisfying the Steinitz-MacLane exchange property:

For every subset $I$ of $E$ and every element $a$ not in the closure of $I$, if $a$ is in the closure of ${I \cup\{ b\}}$, then $b$ is in the closure of $I \cup \{a\}$.

It is remarkable that this single sentence leads to an intricate algebraic structure of the kind we have seen above. This structure reveals certain properties of matroids that are not easy to see by other means.

Let’s write $S_\mathrm{M}$ for the polynomial ring with real coefficients and variables $x_F$, one for each nonempty proper flat $F$ of $\mathrm{M}$.

Definition
The Chow ring of a loopless matroid $\mathrm{M}$ is defined to be the quotient
\[
A^*(\mathrm{M}):=S_\mathrm{M}/(I_\mathrm{M}+J_\mathrm{M}),
\]
where $I_\mathrm{M}$ is the ideal generated by the quadratic monomials
\[
x_{F_1}x_{F_2}, \ \ \text{$F_1$ and $F_2$ are two incomparable nonempty proper flats of $\mathrm{M}$,}
\]
and $J_\mathrm{M}$ is the ideal generated by the linear forms
\[
\sum_{i_1 \in F} x_F – \sum_{i_2 \in F} x_F, \ \ \text{$i_1$ and $i_2$ are distinct elements of the ground set $E$.}
\]
We write $A^q(\mathrm{M}) \subseteq A^*(\mathrm{M})$ for the subspace spanned by all degree $q$ monomials.

Let $n+1$ be the rank of $\mathrm{M}$. An important step is to identify the map analogous to the volume in section $1$, the integral in section $2$, and the degree in section $3$.

Theorem
There is an isomorphism $\text{deg}: A^n(\mathrm{M}) \longrightarrow \mathbb{R}$ uniquely determined by the property
\[
\text{deg}(x_{F_1}x_{F_2}\cdots x_{F_n})=1 \ \ \text{for every flag of nonempty proper flats} \ \ F_1 \subsetneq F_2 \subsetneq \cdots \subsetneq F_n.
\]

In particular, any two monomials corresponding to a complete flag of nonempty proper flats are equal in the Chow ring of a loopless matroid.

4.2

What should be the convex cone $\mathscr{K}(\mathrm{M})$? In fact, there is a certain piecewise linear space associated to $\mathrm{M}$, the tropical linear space of $\mathrm{M}$, and one takes $\mathscr{K}(\mathrm{M})$ to be the set of all strictly convex piecewise linear functions on the tropical linear space. For known applications, the following more restrictive definition is sufficient.

Definition
A function $c$ on the set of nonempty proper subsets of $E$ is said to be strictly submodular if
\[
c_{I_1}+c_{I_2} > c_{I_1 \cap I_2} +c_{I_1 \cup I_2} \ \ \text{for any two incomparable subsets $I_1,I_2 \subseteq E$,}
\]
where we replace $c_\varnothing$ and $c_E$ by zero whenever they appear in the above inequality.

A strictly submodular function $c$ defines an element
\[
\ell(c):= \sum_F c_F x_F\in A^1(\mathrm{M}),
\]
where the sum is over all nonempty proper flats of $\mathrm{M}$; the set of all such is a convex cone in the obvious sense. Note that the rank function of any matroid on $E$ can be obtained as a limit of strictly submodular functions.

Theorem [AHK]
Let $\ell$ be an element of $A^1(\mathrm{M})$ associated to a strictly submodular function, and let $q$ be a nonnegative integer $\le \frac{n}{2}$.

1. Hard Lefschetz theorem: The multiplication by $\ell^{n-2q}$ defines an isomorphism
   \[
   A^q(\mathrm{M}) \longrightarrow A^{n-q}(\mathrm{M}), \qquad a \longmapsto \ell^{n-2q} \ a.
   \]
2. Hodge-Riemann relations: The multiplication by $\ell^{n-2q}$ defines a symmetric bilinear form
   \[
   A^q(\mathrm{M}) \times A^q(\mathrm{M}) \longrightarrow \mathbb{R}, \qquad (a_1,a_2) \longmapsto (-1)^q \ \text{deg}(\ell^{n-2q}\ a_1 a_2)
   \]
   that is positive definite when restricted to the kernel of the multiplication by
   $\ell^{n-2q+1}$.

In fact, the theorem applies more generally to elements $\ell$ in the cone $\mathscr{K}(\mathrm{M})$ mentioned above. Below are two applications presented in [AHK], which use the Hodge-Riemann relations in the special case when $q=1$.

1. Let $w_k$ be the absolute value of the coefficient of $\lambda^{n-k+1}$ in the characteristic polynomial of $\mathrm{M}$. Then the sequence $w_k$ is log-concave:
   \[
   w_{k-1} w_{k+1} \le w_k^2 \ \ \text{for all $1 \le k\le n$.}
   \]
   In particular, the sequence $w_k$ is unimodal:
   \[
   w_0 \le w_1 \le \cdots \le w_l \ge \cdots \ge w_n \ge w_{n+1} \ \ \text{for some index $l$.}
   \]
   This verifies a conjecture of Heron, Rota, and Welsh.
2. Let $f_k$ be the number of independent subsets of $E$ with cardinality $k$. Then the sequence $f_k$ is log-concave:
   \[
   f_{k-1} f_{k+1} \le f_k^2 \ \ \text{for all $1 \le k \le n$.}
   \]
   In particular, the sequence $f_k$ is unimodal:
   \[
   f_0 \le f_1 \le \cdots \le f_l \ge \cdots \ge f_n \ge f_{n+1} \ \ \text{for some index $l$.}
   \]
   This verifies a conjecture of Mason and Welsh.

These applications only use the Hodge-Riemann relations for $q=1$ and for one carefully chosen $\ell$. The general Hodge-Riemann relations for all $\ell$ in $\mathscr{K}(\mathrm{M})$ may contain more interesting information on $\mathrm{M}$.

References

[AHK] Karim Adiprasito, June Huh, and Eric Katz, Hodge theory for combinatorial geometries, arXiv:1511.02888.

[Gro69] Alexander Grothendieck, Standard conjectures on algebraic cycles, 1969 Algebraic Geometry, 193-199, Oxford University Press.

[Karu04] Kalle Karu, Hard Lefschetz theorem for nonrational polytopes, Inventiones Mathematicae 157 (2004), 419-447.

[McM89] Peter McMullen, The polytope algebra, Advances in Mathematics 78 (1989), 76-130.

[McM93] Peter McMullen, On simple polytopes, Inventiones Mathematicae 113 (1993), 419-444.

[Stan80] Richard Stanley, The number of faces of a simplicial convex polytope, Advances in Mathematics 35 (1980), 236-238.

[vLin82] Jack van Lint, The van der Waerden conjecture: two proofs in one year, The Mathematical Intelligencer 4 (1982), 72-77.

[Voi10] Claire Voisin, On the cohomology of algebraic varieties, Proceedings of the International Congress of Mathematicians I, 476-503, New Delhi, 2010.