The Matroid Union | A blog for and by the matroid community

Time 2022-10-10 11:59:53

Web Name: The Matroid Union | A blog for and by the matroid community

WebSite: http://www.matroidunion.org

ID:347214

Keywords:

blog,for,Union,The

Description:

The Matroid Union

A blog for and by the matroid community

Colouring matroid reductions

Posted on October 9, 2022 by Jorn van der PolReply

Covering a graph by forests

Given a loopless graph $G = (V,E)$ with at least one edge, what is the smallest possible number of forests needed to cover all edges? This number is known as the arboricity$a(G)$ of $G$.

For example, consider the following 6-vertex graph, which is obtained from the complete graph $K_5$ by removing one edge, and adding a new pendant edge to one of the vertices of degree 3.

As the graph is connected and has six vertices, each forest in $G$ contains at most five edges. As the graph has ten edges in total, we need at least two forests to cover all edges.

But try as we might, we’ll never be able to cover all edges with only two forests. The reason is that similar bounds must hold in every subgraph of $G$. If we remove the unique degree-1 vertex and the edge incident with it, we are left with a connected graph on five vertices and nine edges. As in this subgraph every forest has at most four edges, we need at least three forests to cover the whole graph. I’ll leave it as an exercise to show that the original graph can actually be covered by three forests.

So, each subgraph $G’$ of $G$ (with at least one edge) provides a lower bound for $a(G)$, as $a(G) \ge \left\lceil \frac{|E(G’)|}{|V(G’)|-c(G’)}\right\rceil$ (here, $c(G’)$ denotes the number of components of $G’$).

Nash-Williams showed that we don’t need more forests than suggested by the worst possible bound obtained in this way: $$a(G) = \max_{G’\subseteq G : E(G’) \neq \emptyset} \left\lceil \frac{|E(G’)|}{|V(G’)|-c(G’)} \right\rceil.$$

Colouring matroids by independent sets

Each of the definitions above can be generalised to matroids, in which case the corresponding question becomes: Given a matroid $M$, how many independent sets do we need to cover the entire ground set of $M$?

The minimum number of independent sets that we need is known as the colouring number (or covering number) of the matroid, and we write $\text{col}(M)$. As loops are not contained in any independent set, we will assume that $M$ has no loops. Edmonds showed (PDF) that the following generalisation of Nash-Williams’ formula holds: $$\text{col}(M) = \max_{E’ \subseteq E: r(E’) > 0} \left\lceil\frac{|E’|}{r_M(E’)}\right\rceil.$$

We say that $M$ is $k$-colourable if $\text{col}(M) \le k$. Note that $a(G) = \text{col}(M(G))$ for any graph $G$, so the colouring number is a proper generalisation of arboricity.

(I like to use “colouring number” rather than “covering number”, as the definition is analoguous to that of “chromatic number” in graphs, which, after all, is the smallest number of independent sets of vertices into which the graph can be partitioned.)

Colouring partition matroids

The colouring number of the uniform matroid $U_{r,n}$ is $\lceil n/r\rceil$. It is clear that this is a lower bound, as $U_{r,n}$ has $n$ elements, and each independent set contains at most $r$ elements.

It is also an upper bound, for we can arbitrarily partition $U_{r,n}$ into $\lfloor n/r\rfloor$ independent sets of size $r$ and, if $r$ does not divide $n$, one more independent set of size less than $r$.

It is an exercise to show that $\text{col}(M_1 \oplus M_2) = \max\{\text{col}(M_1), \text{col}(M_2)\}$.

A matroid is a partition matroid if it is a direct sum of uniform matroids. The following result follows immediately from the above observations:

Lemma.If $M = \bigoplus\limits_{i=1}^k U_{r_i, n_i}$, then $\text{col}(M) = \max\limits_{i=1}^k \lceil n_i / r_i \rceil$.

A 1-partition matroid is a partition matroid in which each of the summands $U_{r_i, n_i}$ has rank 1. The colouring number of a 1-partition matroid is just the size of its largest component.

While colouring 1-partition matroids sounds trivial, the problem occurs naturally in discrete optimisation. For example, edge-colouring bipartite graphs can be described as finding an optimal colouring of the intersection of two 1-partition matroids corresponding to the two sides of the bipartition:

Weak maps and bounds

Suppose that $M$ is some complicated matroid and we want to know or bound $\text{col}(M)$. If $N$ is another matroid on the same ground set such that every independent set in $N$ is independent in $M$ (that is, $N$ is a weak map image of $M$), then $\text{col}(M) \le \text{col}(N)$.

This is particularly useful when $N$ is a 1-partition matroid, as in that case $\text{col}(M)$ is bounded by the size of the largest uniform summand in $N$.

Thus, we have the problem of finding a 1-partition reduction: given a matroid $M$, can we find a 1-partition matroid $N$ that is a weak map image of $M$ whose colouring number is not much larger than that of $M$?

In particular, does there exist a constant $c$ such that we can always find a 1-partition reduction $N$ such that $\text{col}(M) \le \text{col}(N) \le c\cdot\text{col}(M)$? We call a matroid $(1,c)$-decomposable if admits such a 1-partition reduction.

A conjecture

This question was asked by Bérczi, Schwartz and Yamaguchi, who conjectured that every matroid is (1,2)-decomposable; that is, for every $k$-colourable matroid $M$, there exists a partition $E(M) = X_1 \cup X_2 \cup \ldots \cup X_\ell$ such that each $X_i$ contains at most $2k$ elements, and each transversal of $\{X_1, X_2, \ldots, X_\ell\}$ is independent.

While this sounds like a very strong statement, it is true for a large number of natural classes of matroids, including graphic matroids and transversal matroids. (In those cases, an actual 1-partition reduction can be found in polynomial time, based on the natural representations of such matroids).

Unfortunately, the general conjecture was recently shown to fail for large binary projective geometries by Abdolazimi, Karlin, Klein and Oveis Gharan (in fact, their argument shows that there are matroids that are not $(1,c)$-decomposable for arbitrary $c$; a stronger result was later obtained by Leichter, Moseley and Pruhs). I was later able to show the slightly stronger result that almost every $\mathbb{F}_q$-representable matroid is not $(1,c)$-decomposable.

However, not all is lost. While there are counterexamples to the conjecture, the number of such counterexamples may be small; more precisely, the conjecture may still hold for almost all matroids.

Let $\mathcal{P}$ be a matroid property that is closed under isomorphism. We say that almost every matroid has property $\mathcal{P}$ if the fraction of matroids on ground set $[n]$ that fail $\mathcal{P}$ vanishes as $n$ tends to infinity, that is $$\lim_{n \to \infty} \frac{\#\{\text{matroids on $[n]$ with $\mathcal{P}$}\}}{\#\{\text{matroids on $[n]$}\}} = 1.$$

Bérczi, Schwarcz, and Yamaguchi proved that paving matroids are (1,2)-decomposable. It is widely believed that almost every matroid is paving; proving this conjecture would imply that almost every matroid is (1,2)-decomposable.

In fact, since we know a little more about random matroids, the factor 2 can be improved slightly.

First, we know that almost every matroid has rank close to half its size. More precisely, for $\varepsilon > 0$, almost every matroid satisfies $$\left(\frac{1}{2}-\varepsilon\right)|E(M)| \le r(M) \le \left(\frac{1}{2}+\varepsilon\right)|E(M)|.$$

Second, Bérczi, Schwarcz and Yamaguchi proved that a paving matroid of rank $r \approx n/2$ is 2- or 3-colourable, and that if it is $k$-colourable, it has a $\lceil\frac{r}{r-1}k\rceil$-colourable partition reduction. This leads to the following updated version of the conjecture, which may still be true:

Conjecture. Almost every matroid is (1, 3/2)-decomposable.

Odd circuits in binary matroids

Posted on May 3, 2022 by Guest Contributor1

Guest post by James Oxley.

1. Introduction

It is well known that a graph is bipartite if and only if every cycle has an even number of edges and that a connected graph is Eulerian if and only if every vertex has even degree. While we cannot characterize arbitrary matroids in which every circuit has even cardinality, we can characterize binary matroids with this property. For reasons that will be clarified later, such a binary matroid is called affine. The goal of this note is to prove the following two theorems. The first is due to Jim Geelen and Peter Nelson, the second to Nathan Bowler. A circuit $C$ in a matroid is odd if $|C|$ is odd; otherwise $C$ is even.

Theorem 1.1 (Geelen and Nelson). Let $M$ be a loopless, connected, non-affine, binary matroid. If a largest odd circuit of $M$ has $k$ elements, then $M$ has no circuit of size exceeding $2k-2$.

Theorem 1.2 (Bowler).Let $n$ and $k$ be integers exceeding two where $k$ is odd. Then there is an integer $N(k,n)$ such that every $3$-connected, non-affine, binary matroid whose largest odd circuit has $k$ elements either has at most $N(k,n)$ elements or has a minor isomorphic to $M(K_{3,n})$.

Both of these theorems emerged two years ago from discussions following the author’s online seminar talk [7] based on the paper by Chun, Oxley, and Wetzler [2]. The proofs of these theorems were emailed to the author by Jim Geelen and Nathan Bowler. The matroid terminology used here will follow [6].

2. Background

Recall that the rank-$r$ binary projective geometry $PG(r-1,2)$is the matroid whose elements are the non-zero vectors of $V(r,2)$, the $r$-dimensional vector space over the two-element field, and whose independent sets are the linearly independent subsets of $V(r,2)$. For example, the matroids $PG(0,2)$, $PG(1,2)$, and $PG(2,2)$ are $U_{1,1}$, $U_{2,3}$, and the Fano matroid. Of course, every simple binary matroid of rank $r$ is isomorphic to a restriction of $PG(r-1,2)$. The rank-$r$ binary affine geometry $AG(r-1,2)$is the matroid that is obtained from $PG(r-1,2)$ by deleting one of its hyperplanes. Thus $AG(0,2)$, $AG(1,2)$, and $AG(2,2)$ are $U_{1,1}$, $U_{2,2}$, and $U_{3,4}$. Clearly, $AG(r-1,2)$ is the matroid that is obtained from $V(r,2)$ by deleting a $V(r-1,2)$. The symmetry of $V(r,2)$ means that it does not matter which hyperplane we choose to delete. If we delete the hyperplane consisting of the vectors whose first coordinate is zero, then we see that the elements of $AG(r-1,2)$ are the vectors of $V(r,2)$ whose first coordinate is one. It follows that every circuit of $AG(r-1,2)$ is even. To see that a simple binary matroid $M$ having no odd circuits is a restriction of a binary affine geometry, we proceed as follows. Let $A$ be a binary matrix representing $M$. Adjoin a new row to $A$ consisting entirely of ones to get the matrix $A^+$. Then one easily checks that $M[A] = M[A^+]$. Clearly $M[A^+]$ is a restriction of a binary affine geometry.

Adding elements in parallel to existing elements of a simple binary affine matroid yields another binary matroid in which every circuit is even. We deduce that a binary matroid is affine if and only if it has no loops and its simplification is isomorphic to a restriction of a binary affine geometry. The next theorem, which incorporates this observation, is obtained by combining results of Brylawski [1], Heron [4], and Welsh [8]. A proof of the equivalence of i and ii was outlined above. A proof of the equivalence of i and iii may be found in [6, Proposition 9.4.1]. This equivalence, originally shown by Welsh, generalizes to binary matroids the dual relationship between bipartite and Eulerian graphs.

Theorem 2.1. The following are equivalent for a non-empty binary matroid $M$.

Every circuit of $M$ is even.$M$ is loopless and its simplification is isomorphic to a restriction of a binary affine geometry.$E(M)$ can be partitioned into cocircuits.

3. Proofs and Consequences

This section presents the proofs of the two main theorems. The proof of Theorem 1.1 will use the next two lemmas. A theta-graphis a graph $G$ consisting of two vertices, $u$ and $v$, and three internally disjoint paths joining them. These three $uv$-paths in $G$ are the series classesof the theta-graph.

Lemma 3.1.In a connected binary matroid $M$ with an element $e$ and an odd circuit $C$, either $E(M) = C$, or $M$ has as a restriction the cycle matroid of a theta-graph that contains the element $e$ and has $C$ as the union of two of its series classes. In particular, $M$ has an odd circuit containing $e$.

Proof.We may assume that $E(M) \neq C$. Let $d$ be an element of $E(M) – C$, and let $D$ be a circuit that contains $d$ and meets $C$ such that $D – C$ is minimal. As $M$ is binary, $C \bigtriangleup D$ is a disjoint union of circuits. The minimality of $D- C$ implies that $C \bigtriangleup D$ is a circuit, so $M|(C \cup D)$ is the cycle matroid of a theta-graph in which $C$ is the union of two of the series classes. To ensure that $e \in C \cup D$, we take $e = d$ when $e \notin C$. Because the series classes in $M|(C \cup D)$ do not all have even cardinality, it follows that $e$ is in an odd circuit of $M$.

Lemma 3.2. Let $M$ be a connected, non-affine binary matroid. If $M|X$ is connected and affine having at least two elements, then $M$ has an odd circuit $D$ that meets both $X$ and $E(M) – X$ for which $D-X$ is a circuit of $M/X$. Moreover, if $X$ is a circuit, then $M|(X\cup D)$ is the cycle matroid of a theta-graph in which exactly two of the series classes have the same parity.

Proof. As $M$ is not affine, it has an odd circuit $C$. Thus, by Lemma 3.1, $M$ has an odd circuit containing $e$. Hence we can take an odd circuit $D$ that meets $X$ for which $D – X$ is minimal. Suppose that $D -X$ is not a circuit of $M/X$. Then $M/X$ has a circuit $D_1$ that is properly contained in $D -X$. Thus $M$ has a circuit $D_2$ that meets $D-X$ in $D_1$ and is contained in $D_1 \cup X$. The choice of $D$ implies that $D_2$ is even. Now $D \bigtriangleup D_2$ is a disjoint union of circuits of $M$. As $|D \bigtriangleup D_2|$ is odd, $D \bigtriangleup D_2$ contains an odd circuit. This odd circuit cannot be contained in $X$, nor does it contain $D-X$. Hence it contradicts the choice of $D$. Thus $D -X$ is a circuit of $M/X$.  It follows immediately that if $X$ is a circuit, then $M|(X\cup D)$ is the cycle matroid of a theta-graph. As each of $D$ and $X$ is the union of exactly two of the series classes in this theta-graph, and $|D|$ and $|X|$ have different parities, it follows that exactly two of the series classes in $M|(X\cup D)$ have the same parity.

Proof of Theorem 1.1. Let $C$ be a largest circuit of $M$. We may assume that $C$ is even. By Lemma 3.2, $M$ has an odd circuit $D$ that meets $C$ such that $M|(C\cup D)$ is the cycle matroid of a theta-graph. Let the series classes of the theta-graph be $S_1$, $S_2$, and $S_3$ where the first two have the same parity. Then $C = S_1 \cupS_2$.
Suppose that each of $|S_1 \cup S_3|$ and $|S_2 \cup S_3|$ is at most $\tfrac{1}{2}|C|$. Then $|S_1| + |S_2| + 2|S_3| \le |S_1| + |S_2|$. Thus $S_3$ is empty, a contradiction. Hence $|S_1 \cup S_3|$ or $|S_2 \cup S_3|$ exceeds $\tfrac{1}{2}|C|$, and the theorem follows.

A theta-graph with two series classes each having $k – 1$ elements and one having exactly one element shows that the bound in Theorem 1.1 is sharp. Another immediate consequence of Lemma 3.2 is the following.

Corollary 3.3.Every even circuit in a connected, non-affine, binary matroid is the symmetric difference of two odd circuits.

In a connected matroid $M$ with at least two elements, the sizes of a largest circuit and a largest cocircuit are thecircumference$c(M)$ and the cocircumference$c^*(M)$, respectively. When $M$ has an odd circuit, we denote the size of a largest odd circuit by $c_o(M)$; when $M^*$ has an odd circuit, we write $c^*_o(M)$ for $c_o(M^*)$.

Corollary 3.4.Let $M$ be a connected binary matroid having an odd circuit and an odd cocircuit. Then
$$|E(M)| \le 2(c_o(M) – 1)(c^*_o(M) – 1).$$

Proof.By a result of Lemos and Oxley [5], $|E(K)| \le \tfrac{1}{2}c(K)c^*(K)$ for all connected matroids $K$. Combining this with Theorem 1.1 gives the result.

In the next proof, $M({\mathcal W}_m)$ denotes the cycle matroid of a rank-$m$ wheel, while atipless binary spike of rank $m$is the vector matroid of the binary matrix $[I_m|I_m^c]$ where $I_m^c$ is the $m \times m$ matrix that is obtained from $I_m$ by replacing each entry by the other element in the two-element field.

Proof of Theorem 1.2.Let $m = \max\{n, 2k -1\}$. By a theorem of Ding, Oporowski, Oxley, and Vertigan [3], there is a number $N(m)$ such that every $3$-connected binary matroid having more than $N(m)$ elements has as a minor one of $M({\mathcal W}_m)$, $M(K_{3,m})$, $M^*(K_{3,m})$, or a tipless binary spike of rank $m$. If $M$ is a non-affine such matroid and its largest odd circuit has $k$ elements, then, by Theorem 1.1, its largest circuit has at most $2k-2$ elements. Each of $M({\mathcal W}_m)$, $M^*(K_{3,m})$, and the tipless binary spike of rank $m$ has an $m$-element circuit, so none of these matroids occurs as a minor of $M$. Hence $M$ has a minor isomorphic to $M(K_{3,m})$. Taking $N(k,n)$ to be $N(m)$, we get the theorem.

Corollary 3.5.For every odd integer $k$ exceeding two, there is an integer $N'(k)$ such that every $3$-connected, non-Eulerian, simple graph whose largest odd bond has $k$ edges has at most $N'(k)$ edges.

Bibliography

[1] T.H. Brylawski, A decomposition of combinatorial geometries, Trans. Amer. Math. Soc. 171 (1972), 235-282.

[2] C. Chun, J. Oxley, K. Wetzler, The binary matroids with no odd circuits of size exceeding five, J. Combin. Theory Ser. B 152 (2022), 80-120.

[3] G. Ding, B. Oporowski, J. Oxley, and D. Vertigan, Unavoidable minors of large $3$-connected binary matroids, J. Combin. Theory Ser. B 66 (1996), 334-360.

[4] A.P. Heron, Some topics in matroid theory, D.Phil. thesis, University of Oxford, 1972.

[5] M. Lemos and J. Oxley, A sharp bound on the size of a connected matroid, Trans. Amer. Math. Soc. 353 (2001), 4039-4056.

[6] J. Oxley, Matroid Theory, Second edition, Oxford University Press, New York, 2011.

[7] J. Oxley, The binary matroids with no odd circuits of size exceeding five, Graphs and Matroids Online Seminar, University of Waterloo, April 17, 2020.

[8] D.J.A. Welsh, Euler and bipartite matroids, J. Combin.Theory 6 (1969), 313-316.

Online Event: EDI Panel (April 19)

Posted on April 12, 2022 by Shayla Redlin HumeReply

Hi everyone,

Today (April 12) was the last online talk for a while, but I am organizing an Equity, Diversity, and Inclusion (EDI) Panel with the Women in Math Committee at the University of Waterloo that will take place next Tuesday, April 19 at 3pm EDT. The panel is open to anyone in math and will be held on Zoom.

Registration link: https://uwaterloo.zoom.us/webinar/register/WN_OBWbyIMHQtyAq4qFFxf3vg
Event page: https://uwaterloo.ca/women-in-mathematics/events/equity-diversity-and-inclusion-panel
Date: April 19
Time: 3-4:30pm EDT (8-9:30pm BST, 7-8:30am Wed NZST)

Hope to see you there!

 – Shayla

Online Talk: Carolyn Chun

Posted on April 6, 2022 by Shayla Redlin HumeReply

Tuesday, April 12, 3pm ET (8pm BST, 7am Wed NZST)
Carolyn Chun, United States Naval Academy
Lattice path matroids, lattice path polymatroids, and excluded minors

YouTube: https://youtu.be/4DJ9jLc5GiQ

 

Abstract:

We define lattice path matroids, polymatroids, Boolean polymatroids, and lattice path polymatroids, which are a subclass of Boolean polymatroids.  We give an excluded minor characterization for lattice path polymatroids, based on a proof where the main tool was Venn diagrams!  There are infinitely many excluded minors for lattice path polymatroids, but they fall into a small number of easily-described types.

Twitter

Follow @matroidunion

E-mail subscription

Feedly

Recent Posts

Colouring matroid reductionsOdd circuits in binary matroidsOnline Event: EDI Panel (April 19)Online Talk: Carolyn ChunOnline Talk: Lise Turner

Recent Comments

James Oxley on Odd circuits in binary matroidsJorn on Matroids and the De Bruijn–Erdős TheoremJim Geelen on Online Event: Open Problem Session (Dec 14)James Oxley on Henry Crapo: A Brief ReminiscenceMichael Stein on Henry Crapo: A Brief Reminiscence

Other blogs and links

SymOmegaPeter CameronGil KalaiOpen Problem Garden

Archives

October 2022May 2022April 2022March 2022February 2022January 2022December 2021November 2021October 2021September 2021August 2021July 2021June 2021May 2021April 2021March 2021February 2021January 2021December 2020November 2020October 2020September 2020August 2020July 2020June 2020May 2020April 2020October 2019November 2018October 2018September 2018February 2018November 2017October 2017August 2017June 2017May 2017February 2017January 2017December 2016November 2016September 2016July 2016June 2016May 2016April 2016March 2016February 2016January 2016December 2015October 2015September 2015July 2015June 2015May 2015April 2015March 2015February 2015January 2015December 2014November 2014October 2014August 2014July 2014June 2014May 2014April 2014March 2014February 2014January 2014December 2013November 2013October 2013September 2013August 2013July 2013

Meta

Log inEntries feedComments feedWordPress.org

TAGS:blog for Union The

<<< Thank you for your visit >>>

Hot Websites