## discrete mathematics – Proving that any arbitrary set of the rational numbers with a sum of leq 1 is not a matroid

Let $$(X,I)$$ be a matroid ($$X$$ is a finite set). We define $$I subseteq 2^S$$.

By definition $$(X,I)$$ is a matroid iff

a) $$Zin I$$ and $$Y subseteq Z implies Yin I$$ (hereditary condition)

c) $$Y,Z in I$$ and $$|Y|lt |Z|$$ then there exists an $$z in Zsetminus Y$$ such that $$(Ycup z) in I$$

Now, we consider finite sets of rational numbers $$Q$$, with the condition that the sum of the elements of any arbitrary $$Q$$ is less than or equal to 1.

That being said, if we define $$Q$$ so that $$Q={-5,5}$$, then it would mean that $$Qin S$$, however, according to part b) of our definition, a subset $$Y$$, say, in this case $$Y={5}$$, would also have to be in $$S$$, which is not the case. We conclude; $$(X,I)$$ can’t possibly be a matroid.

Is this proof permissible? I would really appreciate you guys’ thoughts 🙂

## co.combinatorics – Dimension of Circuit Space of a Matroid

If $$G$$ is a graph with edge set $$E$$, let $$W$$ be the $$mathbb{Z}/2$$-vector space generated by the elements of $$E$$. If $$A = {a_1, dots, a_n} subset E$$, let $$bar{A} = a_1 + dots + a_n in V$$; then $$bar{A}_1 + bar{A}_2 = overline{A_1 Delta A_2}$$, where $$Delta$$ indicates symmetric difference.

I’ll define the cycle space of $$G$$ to be the subspace of $$W$$ generated by simple cycles of $$G$$. More precisely, the cycle space of $$G$$ is the subspace of $$W$$ generated by the set $${bar{C} mid C text{ is a simple cycle of } G}$$. We could also view the cycle space as the first simplicial homology group of $$G$$ over $$mathbb{Z}/2$$. It is not difficult to show that the dimension of the cycle space of $$G$$ is the corank of the cycle matroid of $$G$$.

Given any matroid $$M$$ with ground set $$E$$, we could define the circuit space of $$M$$ in a completely analogous way, just using the word “circuit” instead of “simple cycle.” My question is: is it always true that the dimension of the circuit space of $$M$$ is the corank of $$M$$? If not, for what types of matroids is this true? Finally, can anyone recommend good resources that deal with this sort of thing?

Thanks!

## Matroid analog of Kneser’s theorem

What are the possible matroid analogs of Kneser’s theorem(or its linear version)?
This question can be formulated this way: If $$G$$ is a (finite) abelian group and $$M$$ is a matroid whose ground set is $$G$$, then what analogs we shall have for Kneser’s theorem in this setting?

## co.combinatorics – What are the coloops of a hypergraphic matroid?

For a hypergraph $$H=(V,E)$$ call $$Fsubseteq E$$ a hyperforest in $$H$$ iff there is a forest graph $$G$$ and a bijection $$smallphi:E(G)to F$$ satisfying $$smallforall ein E(G)(esubseteq phi(e))$$ or equivalently $$smallforall Isubseteq F(|I|+1leq |cup_{Sin I}S|)$$, further we call the matroid $$M(H)=(E,mathcal{I})$$ such that $$mathcal{I}={Isubseteq E:Itext{ is a hyperforest in }H}$$ the hypergraphic matroid of $$H$$ so in particular if $$H$$ is an undirected graph then this coincides with the standard definition described here while analogously if $$mathcal{E}in E$$ then $$M(Hsetminusmathcal{E})=M(H)setminusmathcal{E}$$.

Now with all of that said, my question is given any hypergraph $$H$$ what are the coloops of $$M(H)$$?

I suspect they relate to the line graph $$smallmathcal{L}(H)=(E(H),{{X,Y}subseteq E(H):Xneq Ytext{ and }Xcap Yneqemptyset})$$.

## What is the rank of a transversal matroid for a family of sets \$mathcal{F}\$ such that \$T=(mathcal{F},subseteq)\$ is a tree-order?

If we let $$small r(mathcal{F})=min{|mathcal{F}setminus mathcal{G}|+|cup_{Xinmathcal{G}}X|:mathcal{G}subseteqmathcal{F}}=max{|text{img}(f)|:ftext{ is a choice function of }mathcal{F}}$$and $$small (mathcal{F},subseteq)text{ is a tree}iffforall X,Y,Zinmathcal{F}(Xsubseteq Ycap Zrightarrow Ycup Zin {Y,Z})$$ can $$small r(mathcal{F})$$ be explicitly defined?

For example if $$omega(mathcal{F})$$ is the number of edges in the hasse diagram of $$(mathcal{F},subseteq)$$ (which is a tree graph) then $$r(mathcal{F})leq omega(mathcal{F})+1$$, in particular if $$mathcal{F}$$ is an inclusion chain (i.e. if the hasse diagram of $$(mathcal{F},subseteq)$$ is a path graph) then we know: $$r(mathcal{F})=omega(mathcal{F})+1$$. But what about in ​general? Is there a way to write $$r(mathcal{F})$$ in terms of a weighted sum of paths in the hasse diagram of $$(mathcal{F},subseteq )$$?

## co.combinatorics – Is the smallest packing number of any port in a matroid \$M\$ equal to the maximum number of pairwise disjoint bases in \$M\$?

If for any matroid $$M=(E,mathcal{I})$$ we let $$M_e={Ssubseteq Esetminus{e}:Scup{e}text{ is a circuit of }M}$$ and for any family of non-empty sets $$mathcal{F}neqemptyset$$ we let $$nu(mathcal{F})$$ be the maximum number of pairwise disjoint sets in $$mathcal{F}$$ then is it true that $$min{nu(M_e):ein E}=nu({B:Btext{ is a base of }M})$$? I’m fairly sure this is correct though I just want to make sure.

Sorry if this is elementary, I know by NW that if $$beta(M)=nu({B:Btext{ is a base of }M})$$ then we have $$smallbeta(M)=maxleft{frac{|E|-|X|}{r(E)-r(C)}:Xsubseteq Etext{ and }r(X)neq r(E)right}$$ and $$min{nu(M_e):ein E}$$ is equal to either $$beta(M)-1$$ or $$beta(M)$$ so basically I want to verify this quantity always evaluates to the latter.

## ag.algebraic geometry – What’s known about the matroid induced by the Plücker coordinates of the representation of a matroid?

Let $$M$$ be a linear matroid with ground set $$E$$ and independent subsets $$mathcal I$$, represented by $$rho: E rightarrow V$$.
This induces a map
$$hatrho: mathcal I rightarrow mathbf P(Lambda V), {e_1,ldots,e_k} mapsto (rho(e_1) wedge cdots wedge rho(e_k)).$$
The subset $$operatorname{Im}(hatrho) subset mathbf P(Lambda V)$$ in turn defines a linear matroid $$hat M$$ over $$Lambda V$$.

Is there anything known about this matroid $$hat M$$, e.g. how it depends on the choice of representation, and what its bases look like in relation to the bases of $$M$$? I’m interested in particular in the case where $$M$$ is uniform (for instance, I think the representation shouldn’t matter in that case) or arises combinatorially, and would like to obtain combinatorial descriptions of $$hat M$$. But any pointers would be greatly appreciated.

## co.combinatorics – Does the non-extreme point operator of a closure space being idempotent, imply said space is a matroid (in flat lattice form)?

Given any set $$X$$ and some closure operator $$text{cl}:2^Xto 2^X$$ on $$X$$, we define $$psi:2^Xto 2^X$$ so that $$psi(Q)={qin Q:qintext{cl}(Qsetminus{q})}$$ for all $$Qsubseteq X$$, now if $$forall Ssubseteq X(psi(psi(S))=psi(S))$$ (i.e. if $$psi$$ is idempotent) must $$text{cl}$$ be the closure operator of some matroid?

Sorry if this is either trivially true or trivially false as I am still new to matroid theory.

I know that if $$text{cl}$$ is the closure operator of a matroid then $$psi$$ must be idempotent so the converse statement holds. Further I have been able to reduce the problem to proving $$mathscr{C}={Csubseteq X:psi(C)neq emptysetlandbigcup_{Ssubset S}psi(C)=emptyset}$$ is such that for all $$C_1,C_2in mathscr{C}$$ we have $$ein C_1cap C_2implies exists C_3in mathscr{C}:C_3subseteq (C_1cup C_2)setminus {e}$$ i.e. that the family of sets $$mathscr{C}$$ satisfies the matroid circuit axioms. This is because if $$text{cl}$$ is the closure operator of a matroid $$M$$ grounded on $$X$$, then $$psi$$ maps every $$Ssubseteq X$$ to the maximal cyclic set of $$M$$ in $$S$$ or in other words $$psi(S)$$ is the union of all circuits of $$M$$ contained in $$S$$, so in particular the closure operator $$text{cl}^*:2^Xto 2^X$$ of the dual matroid $$M^*$$ of $$M$$ satisfies $$text{cl}^*(Q)=Xsetminuspsi(Xsetminus Q)$$ for all $$Qsubseteq X$$.

## Independent pair in matroid – MathOverflow

Given a matroid $$M$$ with ground set $$E$$ of size $$2n$$, suppose there exists $$Asubseteq E$$ of size $$n$$ such that both $$A$$ and $$Esetminus A$$ are independent. What is the minimum number of $$Bsubseteq E$$ such that both $$B$$ and $$Esetminus B$$ are independent?

With $$n=2$$, some casework shows that the answer is $$4$$: suppose $${1,2},{3,4}$$ are independent. Using the augmentation property with $${1}$$ and $${3,4}$$, we get that wlog $${1,3}$$ is independent. If $${2,4}$$ is independent, we get four sets $$B$$, so using $${2}$$ against $${3,4}$$, it must be that $${2,3}$$ is independent. But then using $${4}$$ against $${1,2}$$ gives us the claim. It is possible that the independent sets are $$emptyset,{1},{2},{3},{4},{1,2},{3,4},{1,3},{2,4}$$, giving the answer of $$4$$.

## co.combinatorics – Is matroid realizability computable?

Contra my suspicions, the Internet is telling me that Vámos proved in “A necessary and sufficient condition for a matroid to be linear” (citation below) that it is decidable if a matroid is representable over a field. See quote on pg. 3 of Solving Rota’s Conjecture which says “The first exception is the algorithmic problem of determining when a given matroid is representable over an unspecified field, which was proved to be decidable by Vámos (28).”

Vamos, P., A necessary and sufficient condition for a matroid to be linear, Möbius Algebras, Conf. Proc. Waterloo 1971, 162-169 (1975). ZBL0374.05017.