Intereting Posts

Volume of a pyramid as a determinant?
What's the intuition behind this equality involving combinatorics?
Apollonius circle, its radius and center
There are 3 points in the spectrum of some self-adjoint element of a non-unital C*-algebra.
Calculate $I=\int_0^1\frac{\ln(1+x)}{1+x^2}\,dx$
Limit of integral without Taylor expansion
Prove that the convex hull of a set is the smallest convex set containing that set
Surjective endomorphism of abelian group is isomorphism
Bounded functionals on Banach spaces.
Have I totally misunderstood the Banachâ€“Tarski paradox?
Partial Derivative v/s Total Derivative
Sum of $k {n \choose k}$ is $n2^{n-1}$
How to prove that complex numbers (C) are linear space over real numbers (R) field?
How do I simplify $\sqrt{3}(\cot 70^\circ + 4 \cos 70^\circ )$?
Expressing a quadratic form, $\mathbf{x}^TA\mathbf{x}$ in terms of $\lVert\mathbf{x}\rVert^2$, $A$

In a graph, the class of all the sets of vertices that can be covered by some matching forms a matroid.

I wonder what kind of structure the class of all the matchings in a graph can have? Or does it not have any usual structure?

It seems to me that it is close to but not a matroid. Is it the reason to study the class of all the sets of vertices covered by some matching, instead of studying directly the class of all the matchings?

- Is there is a way to construct a covering space of a wedge of two circles for a given normal subgroup
- Families of sets, determination of SDR (system of distinct representatives)
- Adjacency matrix and connectivity proof
- connection between graphs and the eigenvectors of their matrix representation
- 5-color graph problem
- Proof that there can be no planar graph with 5 faces, such that any two of them share an edge.

Thanks!

- How else can we be nauty?
- Infinite connected graph
- Definition of vertex-cut for digraph?
- Graph theory software?
- Easy to read books on Graph Theory
- Indicator function for a vertex-induced random subgraph of $G$?
- How many connected graphs over V vertices and E edges?
- 2- or 3-vertex-connected cubic planar bipartite graphs with only one Hamilton cycles
- Use Gröbner bases to count the $3$-edge colorings of planar cubic graphs…
- Let graph $G = (V, E)$ $\Rightarrow$ $\alpha(G) \ge \frac{{|V|}^{2}}{2 \times (|E| + |V|)}$

I think the main issue here is what the ground set of the matroid ought to be. The matching matroid has ground set $V(G)$, while each matching is a subset of $E(G)$. Unfortunately, in general, the set of matchings is not the set of independent sets of a matroid. It is of course a family that is closed under taking subsets, but the augmentation axiom fails. For example, if $G$ is path of three edges, and $M_1$ is the matching consisting of the middle edge, and $M_2$ is the matching consisting of the two end edges, then $|M_2|>|M_1|$, but we cannot augment $M_1$ via an edge in $M_2$.

That is not to say that the set of matchings does not have nice properties, just that it is not a matroid. For example, there is this beautiful theorem of Edmond’s that completely describes the convex hull of the set of matchings via linear inequalities.

- 2013 Putnam A1 Proof understanding (geometry)
- Definite integral of Normal Distribution
- Sufficient and necessary conditions to get an infinite fiber $g^{-1}(w)$
- Counting the (ordered) partitions of an integer into a fixed amount of parts
- Darboux's Integral vs. the “High School” Integral
- Complements of hypersurfaces in a projective space is affine.
- Ideal contained in a finite union of prime ideals
- Function which is not in $L^2(R^n)$
- Polya's formula for determining the number of six-sided dice
- Does $\neg(x > y)$ imply that $y \geq x$?
- Hausdorff metric and Vietoris topology
- Monotonicity of $\log \det R(d_i, d_j)$
- Logical formula of definition of linearly dependent
- How prove this $n^n+47\equiv 0\pmod{2^l}$
- How to start with mathematics?