{"id":1675,"date":"2016-04-19T15:01:01","date_gmt":"2016-04-19T19:01:01","guid":{"rendered":"http:\/\/matroidunion.org\/?p=1675"},"modified":"2016-04-19T15:23:49","modified_gmt":"2016-04-19T19:23:49","slug":"counting-matroids-by-entropy","status":"publish","type":"post","link":"https:\/\/matroidunion.org\/?p=1675","title":{"rendered":"Counting Matroids  by Entropy"},"content":{"rendered":"<p><em>Guest post\u00a0by <a href=\"http:\/\/www.win.tue.nl\/~rudi\/\">Rudi Pendavingh<\/a> and Jorn van der Pol<\/em><\/p>\n<h1>Introduction<\/h1>\n<p>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.<\/p>\n<p>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.<\/p>\n<p>In this blog post, we show how entropy can be used for counting\u00a0problems in general and for counting matroids in particular, and we give a new proof for\u00a0the following theorem from\u00a0[PvdP15].<\/p>\n<p><strong>Theorem.<\/strong> If $N=U_{2,k}$ or $N=U_{3,6}$, then asymptotically almost all matroids have an $N$-minor.<\/p>\n<h1>Entropy<\/h1>\n<p>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 <em>entropy<\/em> of $X$ is defined as<br \/>\n$$\\mathcal{H}(X) = -\\sum_{x \\in \\mathcal{X}} P(x) \\log P(x),$$<br \/>\nwhere $\\log$ denotes the binary logarithm, and for convenience we write $0\\log 0 = 0$.<\/p>\n<p>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,<br \/>\n$$\\mathcal{H}(X) = H(p) := -p \\log p &#8211; (1-p) \\log (1-p).$$<br \/>\nIf $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$.<\/p>\n<p>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)$.<\/p>\n<ul>\n<li><strong>Boundedness:<\/strong> $\\mathcal{H}(X) \\le \\log |\\mathcal{X}|$.<\/li>\n<li><strong>Subadditivity:<\/strong> $\\mathcal{H}(X,Y) \\le \\mathcal{H}(X) + \\mathcal{H}(Y)$.<\/li>\n<\/ul>\n<p>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}|$.<\/p>\n<p>In our applications, the space $\\mathcal{X}$ consists of binary vectors, indexed by some set $J$. This allows us to define <em>projections<\/em> $X_T = (X_j : j \\in T)$ for $T\\subseteq J$.<\/p>\n<p>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].<\/p>\n<p><strong>Shearer&#8217;s Entropy Lemma.\u00a0<\/strong>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<br \/>\n$$\\mathcal{H}(X) \\le \\frac{1}{k} \\sum_{i=1}^m \\mathcal{H}(X_{T_i}).$$<\/p>\n<p>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&#8217;s Lemma.<\/p>\n<h1>Matroid counting<\/h1>\n<p>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.<\/p>\n<p>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)|$.<\/p>\n<p>The following result illustrates Shearer&#8217;s Entropy Lemma. As its proof is short, we will include it here.<\/p>\n<p><strong>Lemma.\u00a0<\/strong>If $\\mathcal{M}$ is closed under taking submatroids, then $$\\frac{\\log\\left(1+m_{\\mathcal{M}}(n,r)\\right)}{ \u00a0\\binom{n}{r}} \\leq \\frac{\\log \\left(1+m_{\\mathcal{M}}(n-1,r)\\right)}{ \u00a0\\binom{n-1}{r}}.$$<\/p>\n<p><em>Proof: <\/em>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&#8217;s Entropy Lemma in such a way that its projections correspond to deletions.<\/p>\n<p>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)$.<\/p>\n<p>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}$.)<\/p>\n<p>We make two observations.<\/p>\n<ul>\n<li>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)$.<\/li>\n<li>Each $r$-subset of $E$ is contained in $|E|-r$ different $T_e$.<\/li>\n<\/ul>\n<p>An application of Shearer&#8217;s Entropy Lemma, followed by an application of the Boundedness Property shows<br \/>\n$$\\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),$$<br \/>\nwhich concludes the proof. $\\square$<\/p>\n<p>Repeated application of the statement dual to Lemma 1 yields the following variant:<\/p>\n<p><strong>Matroid Entropy Lemma.\u00a0<\/strong>If $\\mathcal{M}$ is closed under contraction, then for all $t \\le r$<br \/>\n$$\\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}}.$$<\/p>\n<p>This\u00a0variant\u00a0enables\u00a0us\u00a0to lift upper bounds on the number of matroids of a fixed rank $s$ \u00a0to upper bounds on the number of matroids in any rank $r\\geq s$.<\/p>\n<p>The first natural application of this scheme is counting matroids in general, so the case $\\mathcal{M}=\\mathbb{M}$. We will abbreviate\u00a0$m(n,r):=m_{\\mathbb{M}}(n,r)$, and consider the matroids of\u00a0fixed rank\u00a0$s=2$. Since each matroid of rank 2 on $n$ elements determines a\u00a0nontrivial partition of $n+1$ elements, we have\u00a0$1+m(n,2)\\leq (n+1)^n$. Hence,\u00a0$$\\frac{\\log (1+m(n,r))}{ \u00a0\\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\u00a0to derive the following for\u00a0$m(n):=\\sum_r\u00a0m(n,r)$.<\/p>\n<p><strong>Theorem (Bansal, Pendavingh, Van der Pol 2014).<\/strong><\/p>\n<p>$$\\log m(n)\u00a0\\leq O\\left(\\binom{n}{n\/2}\\frac{\\log(n)}{n}\\right)\\text{ as }n\\rightarrow\\infty$$<\/p>\n<p>For comparison, we state the following lower bound.<\/p>\n<p><strong>Theorem (Knuth 1974;\u00a0\u00a0Graham, Sloane 1980).<\/strong>\u00a0$\\log m(n)\u00a0\\geq \\binom{n}{n\/2}\/n$.<\/p>\n<p>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\u00a0$\\log n$ factor will not go away if we use a fixed rank $s&gt;2$ for the base case. The following paraphrases a result due to Bennett and Bohman (see [Kee15]).<\/p>\n<p><strong>Theorem\u00a0<\/strong>For any fixed $s\\geq 3$, we have \u00a0$$\\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$$<\/p>\n<p>We defer the\u00a0details of these lower bounds to a later post.<\/p>\n<h1>Further applications<\/h1>\n<p>To show that asymptotically almost all matroids have certain fixed matroid $N$\u00a0\u00a0as 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)$.<\/p>\n<p>Each matroid of rank 2 on $n$ elements without $U_{2,k}$-minor corresponds 1-1 to\u00a0a partition of $n+1$ items into at most $k$ parts, so that\u00a0 $1+m'(n,2)=k^{n+1}$.\u00a0This\u00a0gives\u00a0$$\\frac{\\log (1+m'(n,r))}{ \u00a0\\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\u00a0$m_{Ex(U_{2,k})}(n):=\\sum_r\u00a0m'(n, r)$ below the lower bound on $m(n)$.<\/p>\n<p>At the time of writing of [PvdP15], we made this same calculation and then gave up on using the matroid entropy lemma\u00a0to produce the upper bound. Instead, we developed\u00a0<em>cover complexity<\/em>\u00a0to do the job. But recently we noted that we were wrong to give up on\u00a0entropy so soon, which works beautifully if we proceed from\u00a0matroids of fixed rank $s=3$ rather than $2$.<\/p>\n<p>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\u00a0a global upper bound $c_k$ on the number of such (simple) matroids. Since each\u00a0matroid 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\u00a0$$\\frac{\\log (1+m'(n,r))}{ \u00a0\\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:<\/p>\n<p><strong>Theorem (Pendavingh, Van der Pol 2015).<\/strong>\u00a0 For any fixed $k$, we have $$\\log m_{Ex(U_{2,k})}(n)\u00a0\\leq O\\left(\\binom{n}{n\/2}\/n^2\\right)\\text{ as }\u00a0n\\rightarrow \\infty$$<\/p>\n<p>Hence $\\log m_{Ex(U_{2,k})}(n)\\leq o(\\log m(n))$, and it follows that asymptotically\u00a0almost all matroids on $n$ elements have $U_{2,k}$ as a minor.<\/p>\n<p>To bound the matroids without $U_{3,6}$ as a minor, it will also suffice to consider simple matroids in base rank 3.<\/p>\n<p><strong>Lemma.\u00a0<\/strong>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\\}$.<\/p>\n<p>Our shortest argument works for $n_0=56$. You may enjoy improving\u00a0that constant.<\/p>\n<p>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\u00a0almost all\u00a0matroids on $n$ elements have\u00a0$U_{3,6}$ as a minor.<\/p>\n<h1>Conjectures<\/h1>\n<p>When applying the matroid entropy lemma, a key issue \u00a0seems 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.\u00a0And as we found out to our embarrassment, we sometimes need to go to a sufficiently high $s$ before our bounds are any good.<\/p>\n<p>So far we have not ventured\u00a0beyond 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, \u00a0we offer the following conjectures.<\/p>\n<p><em>Matroids without the 3-whirl<\/em><\/p>\n<p><strong>Conjecture.\u00a0<\/strong>Asymptotically almost all matroids have the 3-whirl $W^3$ as a minor.<\/p>\n<p>It is a theorem that almost all matroids are 3-connected [OSWW13], and we hazard the guess\u00a0that most of those 3-connected matroids will have\u00a0$M(K_4)$ or $W^3$ as a minor. Having\u00a0<a href=\"https:\/\/matroidunion.org\/?p=139\">$M(K_4)$\u00a0as a minor<\/a> seems strictly more of a `coincidence&#8217; 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\u00a0$W^3$ and\u00a0$M(K_4)$ is a minor of almost all matroids, and the former is more likely than the latter, our conjecture becomes quite believable.<\/p>\n<p>We could not make any sufficient\u00a0upper bounds on $m_{Ex(W^3)}(n,s)$ in fixed rank $s=3$, but $s=4$ is open.<\/p>\n<p><em>Matroids without a fixed uniform minor<\/em><\/p>\n<p>We have very recently established the following [PvdP16].<\/p>\n<p><strong>Theorem<\/strong> Let $N$ be a uniform matroid.\u00a0Asymptotically almost all matroids have $N$ as a minor.<\/p>\n<p>The technique we used for this is much more involved than the\u00a0above entropy\u00a0method, and its does not give good bounds in fixed rank. The following\u00a0is open.<\/p>\n<p><strong>Conjecture.<\/strong>\u00a0Let $N$ be a uniform matroid. For any $c$ there exists an $s$ so that\u00a0$$\\log\\left(1+m_{Ex(N)}(n,s)\\right) \/ \\binom{n}{s} \\leq \\frac{c}{n}$$ for all sufficiently large $n$.<\/p>\n<p>If this conjecture is true for any\u00a0$c&lt;1\/2$, this would yield an alternative proof of\u00a0our theorem.<\/p>\n<p><em>Oriented matroids<\/em><\/p>\n<p><strong>Conjecture\u00a0<\/strong>Asymptotically almost all matroids are not orientable.<\/p>\n<p>This conjecture may not appeal to all of you. An enumeration of small matroids reveals that the majority is in fact, orientable [MMIB12].<\/p>\n<p>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\u00a0lemma for oriented matroids, with an entirely analogous proof (you\u00a0use chirotopes rather than incidence vectors of base sets, otherwise the proof is identical).<\/p>\n<p><strong>Oriented Matroid Entropy Lemma.\u00a0<\/strong>For all $t \\le r$<br \/>\n$$\\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}}.$$<\/p>\n<p>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 <em>orientable<\/em> matroids\u00a0will be vanishing compared to the number of matroids, which would prove the conjecture. It would suffice to establish:<\/p>\n<p><strong>Conjecture.<\/strong>\u00a0There is an $s$ and an $c&lt;1\/2$ such that\u00a0$$\\frac{\\log\\left(1+\\bar{m}(n,s)\\right)}{ \\binom{n}{s}} \\leq \\frac{c}{n}$$ for all sufficiently large $n$.<\/p>\n<p>Except for the constant $c&lt;1\/2$, that does not seem too much to ask, given the following theorem\u00a0[ERS86].<\/p>\n<p><strong>Theorem.\u00a0<\/strong>For each $s$ there is a $c$ such that\u00a0$$\\frac{\\log \\bar{m}(n,s)} { \\binom{n}{s} }\\leq \\frac{c}{n}$$ for all sufficiently large $n$.<\/p>\n<p>Note that this theorem already implies that for any fixed $s$, we have $$\\log\u00a0\\bar{m}(n,s)\\leq o(\\log m(n,s))$$ for $n\\rightarrow\\infty$, since\u00a0$\\log m(n,s)\/\\binom{n}{s}\\sim \\log (n)\/n$\u00a0as $n\\rightarrow\\infty$.<\/p>\n<p>Finally, a construction due to Felsner and Valtr [FV11] shows that $$\\log \\bar{m}(n,3)\\geq 0.1887 n^2,$$ i.e. \u00a0$\\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&#8230;<\/p>\n<h1>References<\/h1>\n<p>[AS08] Noga Alon and Joel Spencer, <em>The probabilistic method, 3rd edition<\/em>.<\/p>\n<p>[BPvdP14] N. Bansal, R.A. Pendavingh, and J.G. van der Pol. <em>An entropy argument for counting matroids<\/em>. Journal of Combinatorial Theory B, 109:258-262, 2014.<\/p>\n<p>[CFGS86] F. R. K. Chung, R. L. Graham, P. Frankl, and J. B. Shearer. <em>Some intersection theorems for ordered sets and\u00a0graphs<\/em>. Journal of Combinatorial Theory A, 43(1):23-37, 1986.<\/p>\n<p>[ERS86] H. Edelsbrunner, J. O&#8217;Rourke, and R. Seidel.<em> Constructing arrangements of lines and hyperplanes with applications.\u00a0<\/em>SIAM Journal on Computing\u00a015\u00a0(2): 341\u2013363, 1986\u00a0doi:<a class=\"external text\" href=\"https:\/\/dx.doi.org\/10.1137%2F0215024\" rel=\"nofollow\">10.1137\/0215024<\/a>.<\/p>\n<p>[FV11]\u00a0<span class=\"AuthorName_container\"><span class=\"AuthorName\">S. Felsner and<\/span><\/span>\u00a0P.<span class=\"AuthorName_container\"><span class=\"AuthorName\">\u00a0Valtr.\u00a0<\/span><\/span><em>Coding and Counting Arrangements of Pseudolines.\u00a0<\/em>Discrete &amp; Computational Geometry,\u00a0<span class=\"ArticleCitation_Year\"><time>October 2011<\/time>,\u00a0<\/span><span class=\"ArticleCitation_Volume\">46:405<\/span><\/p>\n<p>[Kee15] P. Keevash. <em>Counting designs.\u00a0\u00a0<\/em><a href=\"http:\/\/arxiv.org\/abs\/1504.02909\">Arxiv preprint 1504.02909<\/a><\/p>\n<p>[MMIB12]\u00a0Y. Matsumoto, S. Moriyama, H. Imai and D. Bremner. <em>Matroid enumeration for incidence geometry. <\/em>Discrete and Computational Geometry.\u00a0Vol. 47, issue 1, pp. 17-43, 2012.<\/p>\n<p>[OSWW13] J. Oxley, C. Semple, L. Warshauer, and D. Welsh. <em>On properties of almost all matroids.<\/em> Adv. Appl. Math., 50(1):115\u2013124, 2013.<\/p>\n<p>[PvdP15] R.A. Pendavingh and J.G. van der Pol.\u00a0<em>Counting matroids in minor-closed classes<\/em>. Journal of Combinatorial Theory B, 111:126\u2013147, 2015.<\/p>\n<p>[PvdP16]\u00a0R.A. Pendavingh and J.G. van der Pol.\u00a0<em>On the number of bases in almost all matroids.\u00a0<\/em><a href=\"http:\/\/arxiv.org\/abs\/1602.04763\">Arxiv preprint 1602.04763<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Guest post\u00a0by 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 &hellip; <a href=\"https:\/\/matroidunion.org\/?p=1675\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":7,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-1675","post","type-post","status-publish","format-standard","hentry","category-matroids"],"_links":{"self":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/1675","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/users\/7"}],"replies":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1675"}],"version-history":[{"count":59,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/1675\/revisions"}],"predecessor-version":[{"id":1768,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/1675\/revisions\/1768"}],"wp:attachment":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1675"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1675"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1675"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}