#matroid — Public Fediverse posts

The #paperOfTheDay is "The Ehrhart polynomial of a matroid specializes to the beta invariant" from 2025.
A #matroid is an abstract generalization of a set of vectors in a vector space: Consider some set of k vectors in R^n (allowing k>n). Some of these k vectors could be linearly independent, but assume that not all of them are. If some subset is linearly independent, then so is every subset of that subset. This and a few other properties jointly give the definition of a matroid: Basically, consider the same logical relations arising from linear independence, but without demanding that the objects under consideration are actually vectors in R^n.
If one declares the elements of a matroid to be unit vectors in some abstract vector space (these basis vectors are all linearly independent in that abstract space, whereass not all elements are independent in the matroid), then the maximum set of independent vectors in the matroid amounts to some subset of these abstract vectors, whose convex hull is a polytope. This polytope contains a finite number of points of Z^n. If one rescales the polytope by an integer t, the number of lattice points changes. It turns out that the number of lattice points included is a polynomial of t (not a more complicated function), this defines the Ehrhart polynomial.
Every graph gives rise to a matroid (but not every matroid can be represented as a graph). For graphs, the Tutte polynomial is a classical quantity. The linear term of the Tutte polynomial is the Crapo-beta invariant (and can also be defined for non-graphical matroids). The present paper proves that a linear term of the Ehrhart polynomial coincides with beta. https://arxiv.org/abs/2504.15518 #mathematics #graphTheory

Neat little set of experiments I did :)

https://harrison.totty.dev/p/positroid-structure-relu-networks

#mathematics #positroid #matroid

'Deletion Robust Non-Monotone Submodular Maximization over Matroids', by Paul Dütting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, Morteza Zadimoghaddam.

http://jmlr.org/papers/v26/23-1219.html

#matroid #matroids #algorithms

Great introductory article on #matroid s:

Neel, David L., and Nancy Ann Neudauer. 2009. “Matroids You Have Known.” Mathematics Magazine 82 (1): 26–41. https://doi.org/10.1080/0025570X.2009.11953589.

#Matroid s are a specific kind of sets that contain other sets, but for any set they contain, they also need to contain its subsets. For more look here:

https://en.wikipedia.org/wiki/Matroid

Looking oddly specific, they're in fact an interesting structure which pops out in the study of many combinatorial subjects like graph theory, and, as I just learned, #homology!