graph-theory
Algebraic matroids
Let $\mathbb{F}\subseteq \mathbb{K}$ be a field extension. An element $u\in\mathbb{K}$ is algebraic over $\mathbb{F}$ if $P(u)=0$ for some $P\in\mathbb{F}[x]$, and transcendental otherwise. A finite $T\subseteq\mathbb{K}$ is algebraically dependent over $\mathbb{F}$ if some $t\in T$ is algebraic over $\mathbb{F}(T\setminus\{t\})$.
Theorem. If $E\subseteq\mathbb{K}$ is finite, the algebraically independent subsets of $E$ are the independent sets of a matroid.
Definition. A matroid is algebraic if it arises in this way.
Example. Over $\mathbb{F}=\mathbb{R}\subseteq \mathbb{K}=\mathbb{C}(x,y,z)$, the elements \[ a=x, b=z^{2}, c=yz, d=y, e=2y, f=1+i \] realise the running example. The explicit relations \[ f^{2}-2f+2=0, e-2d=0, c^{2}-d^{2}b=0 \] show that $f$ is a loop, $\{d,e\}$ is a parallel pair, and $\{b,c,d\}$, $\{b,c,e\}$ are $3$-circuits, while $a$ does not appear and is a coloop.
The board writes $b=(y+z)^{2}$ and $c=x(y+z)$ with $d=e=x$; that also makes $\{d,e\}$ parallel, but then $a$ is entangled with $b$ and is no longer a coloop. The specialisation above matches the circuits $\{f\}$, $\{d,e\}$, $\{b,c,d\}$, $\{b,c,e\}$ of the running example.
Example. Over $\mathbb{R}\subseteq\mathbb{C}$ every complex number is algebraic, so a finite subset of $\mathbb{C}$ consists entirely of loops. Over $\mathbb{Q}\subseteq\mathbb{R}$ the picture is mixed. For $\{a,b,c,d\}=\{\sqrt{2},\sqrt{3},e,e+\pi\}$ one has: $a$ and $b$ are loops ($t^{2}-2$, $t^{2}-3$); $c=e$ is transcendental (Hermite), hence independent; whether $d=e+\pi$ is algebraic over $\mathbb{Q}$, or over $\mathbb{Q}(e)$, is open.
To prove we check that \[ \overline(A)=\{x\in E:\ x\text{ is algebraic over }\mathbb{F}(A)\} \] satisfies (CL1)–(CL4).
Lemma. An element $x$ is algebraic over $\mathbb{F}(a_1,\ldots,a_n)$ if and only if the extension degree $[\mathbb{F}(a_1,\ldots,a_n,x):\mathbb{F}(a_1,\ldots,a_n)]$ is finite.
*Proof.* If $P(x)=0$ has degree $m$, then $1,x,\ldots,x^{m}$ are linearly dependent over $\mathbb{F}(a_1,\ldots,a_n)$ and $1,x,\ldots,x^{m-1}$ span $\mathbb{F}(a_1,\ldots,a_n,x)$. If there is no algebraic relation then $1,x,x^2,\ldots$ are linearly independent, so the degree is infinite.
Lemma（Tower law）. If $\mathbb{F}\subseteq \mathbb{K}\subseteq \mathbb{L}$ then $[\mathbb{L}:\mathbb{F}]=[\mathbb{L}:\mathbb{K}]\cdot[\mathbb{K}:\mathbb{F}]$.
*Proof.* If $(x_i)$ is a $\mathbb{K}$-basis of $\mathbb{L}$ and $(y_j)$ is an $\mathbb{F}$-basis of $\mathbb{K}$, then $(x_i y_j)$ is an $\mathbb{F}$-basis of $\mathbb{L}$.
*Proof.* (CL1): $a\in A$ is a root of $t-a\in\mathbb{F}(A)[t]$. (CL2): a polynomial over $\mathbb{F}(A)$ is a polynomial over $\mathbb{F}(B)$ if $A\subseteq B$. (CL4): if $a\in\overline(A\cup\{b\})$ and $a\notin\overline(A)$, a relation $P(a)=0$ with coefficients in $\mathbb{F}(A,b)$ involves $b$ (else $a\in\overline(A)$). Write $P=\sum_{i=0}^{m} Q_i(b) a^{i}$ with $Q_i\in\mathbb{F}(A)[t]$ and some $Q_i$ of positive degree; clearing the highest power of $b$ produces a nonzero polynomial in $b$ over $\mathbb{F}(A,a)$. Rearranging gives a polynomial equation for $b$ over $\mathbb{F}(A,a)$, so $b\in\overline(A\cup\{a\})$. (CL3): the inclusion $\overline(A)\subseteq\overline(\overline(A))$ is (CL1). If $a\in\overline(\overline(A))$ then $[\mathbb{F}(\overline(A),a):\mathbb{F}(\overline(A))]<\infty$. Each element of $\overline(A)$ is algebraic over $\mathbb{F}(A)$, so adjoining them one at a time gives $[\mathbb{F}(\overline(A)):\mathbb{F}(A)]<\infty$. The tower law yields $[\mathbb{F}(\overline(A),a):\mathbb{F}(A)]<\infty$, hence $[\mathbb{F}(A,a):\mathbb{F}(A)]<\infty$, so $a\in\overline(A)$.
Thus algebraic independence is a matroid closure, and follows from .
> *Supplement.* Every linear matroid is algebraic. Given a representation of $M$ by > vectors $v_1,\ldots,v_n\in\mathbb{F}^r$, choose algebraically independent > indeterminates $x_1,\ldots,x_r$ over the prime field of $\mathbb{F}$, and set > $e_i=\sum_j a_{ji}x_j$ using the coordinates of $v_i$. Algebraic > independence of a subset of the $e_i$ is then equivalent to linear > independence of the corresponding $v_i$. > > The converse is false. The non-Pappus matroid of the previous section is > algebraic (Lindstrom) but not linear over any field. The V\'amos > matroid is neither linear nor algebraic: Ingleton's inequality, a linear > rank inequality with no algebraic analogue of the same strength, already > obstructs a representation by field elements. Thus > \[ > \text{graphic}\ \subsetneq\ \text{regular}\ \subsetneq\ \text{linear} > \ \subsetneq\ \text{algebraic}\ \subsetneq\ \text{all matroids}. > \] > Minors of algebraic matroids are algebraic, but it is open whether the > dual of an algebraic matroid is always algebraic. > > The rank of an algebraic matroid is the transcendence degree: if > $E\subseteq\mathbb{K}$ is finite then $r(M)=\mathrm{trdeg}(\mathbb{F}(E)/\mathbb{F})$. In > the running realisation above one has $\mathbb{F}(E)=\mathbb{C}(x,y,z)$ of transcendence > degree $3$, matching $r(M)=3$.