2024 Workshop on (Mostly) Matroids

We are excited to announce the 2024 Workshop on (Mostly) Matroids, held in-person at the Institute for Basic Science (IBS), Daejeon, South Korea, on August 19 – 23, 2024.  We hope that this workshop will continue the tradition of previous workshops held in Sittard  (2008), Maastricht (2010, 2012), Princeton (2014), Eindhoven (2016), Waterloo (2017), and Baton Rouge (2019). The focus will be on all aspects of matroid theory, including its connections to graph theory, algebraic geometry, and other areas of mathematics.

We plan to bring together 50-70 researchers from all over the world. We are enthusiastic about making this workshop an opportunity for graduate students and postdoctoral fellows, especially those who have had limited opportunities for research collaborations and in-person meetings. If you or your students who would like to attend, please send an email to the address below. We may be able to offer some funding to support graduate students and postdocs, so please let us know if this could be helpful.

More information is posted on the conference website: https://indico.ibs.re.kr/e/wmm2024

You can contact us using the address matroids@proton.me.

Organizers: Spencer Backman, Rutger Campbell, Dillon Mayhew, Sang-il Oum.

Dates: August 19 – 23, 2024. We start Monday morning and finish Friday at the end of the afternoon. We expect most people to arrive on Sunday, August 18 and leave on Saturday, August 24.

The workshop is by invitation only.

Hotels

The organizers have contacted the following nearby hotels for discounts for the participants. 

  • ICC Hotel: A 2-star hotel within a short walking distance (about 800m).  Please fill out this form and send it to the ICC hotel email address to secure a reservation at a discounted rate. Expect to pay around 100 USD per night. Free breakfast.
  • I-Hotel: Formerly a guest house for visitors to research institutions in Daejeon. It is in the same neighbourhood as the ICC Hotel and next to the famous bakery cafe (Sungsimdang) of Daejeon. Visit the iHotel website, fill out the form, and send it. You can pay the accommodation fee upon check-in. After the IBS discount, expect to pay about 35 USD per night for a single one-person room or 46 USD for a two-person room.

Postdoc positions at the IBS Discrete Mathematics Group, South Korea (Deadline: December 3)

The IBS Discrete Mathematics Group (DIMAG, https://dimag.ibs.re.kr/) in Daejeon, Korea invites applications for three research fellowship positions:

URL: https://dimag.ibs.re.kr/hiring/

DIMAG is a research group that was established on December 1, 2018 at the Institute for Basic Science (IBS), led by Prof. Sang-il Oum. DIMAG is located at the headquarters of the Institute for Basic Science (IBS) in Daejeon, South Korea, a city of 1.5 million people.

Currently, DIMAG consists of researchers from various countries such as Korea, the USA, Germany, Canada, and Australia, and the work is done in English. DIMAG is co-located with the IBS Extremal Combinatorics and Probability Group (ECOPRO).

Successful candidates for research fellowship positions will be new or recent Ph.D.’s with outstanding research potential in all fields of discrete mathematics with emphasis on structural graph theory, combinatorial optimization, matroid theory, and algorithms.

These appointments are for about two years, and the starting salary is no less than KRW 59,000,000. The appointment is one-time renewable up to 5 years in total contingent upon the outstanding performance of the researcher. The expected appointment date is September 1, 2024, but it is negotiable within the same calendar year.

These are purely research positions and will have no teaching duties.

A complete application packet should include:

  1. AMS standard cover sheet (preferred) or cover letter (PDF format)
  2. Curriculum vitae including a publication list (PDF format)
  3. Research statement (PDF format)
  4. Application for the IBS & Consent to Collection and Use of Personal Information (PDF file)
  5. At least 3 recommendation letters

For full consideration, applicants should email items 1, 2, 3, and 4 and arrange their recommendation letters emailed to dimag@ibs.re.kr by December 3, 2023, Sunday. (Anywhere on Earth)

Recommendation letters forwarded by an applicant will not be considered.

DIMAG encourages applications from individuals of diverse backgrounds.

For Korean citizens who have not yet completed their military duty: 전문연구요원 종사를 희망하는 경우에는 지원 의사와 병역 관계를 cover letter 및 이메일 등에 표시하여 제출 필요. 다만 현역입영대상자의 전문연구요원 신규 편입은 불가하며, 보충역 대상자 및 타 기관에서 전직해서 오는 경우에 한하여 지원 가능(반드시 타 기관에서 전직 요건이 충족되는 등 전직 요건이 충족 되어야만 함)

Postdoc positions at the IBS Discrete Mathematics Group, South Korea

The IBS Discrete Mathematics Group (DIMAG) in Daejeon, Korea invites applications for two postdoctoral research fellowship positions.

URL: https://dimag.ibs.re.kr/hiring/

DIMAG is a research group that was established in December 1, 2018 at the Institute for Basic Science (IBS), led by Prof. Sang-il Oum. DIMAG is located at the headquarters of the Institute for Basic Science (IBS) in Daejeon, South Korea, a city of 1.5 million people. 

The position is available for individuals who are within the first five years after obtaining their Ph.D. at the date of appointment or expecting to obtain a Ph.D. within three months from the date of appointment. Successful candidates for postdoctoral research fellowship positions will be new or recent Ph.D.’s with outstanding research potential in all fields of discrete mathematics with emphasis on structural graph theory, extremal graph theory, combinatorial optimization, matroid theory, or fixed-parameter tractable algorithms.

This appointment is for two years, and the starting salary is no less than KRW 57,000,000. The appointment is one time renewable up to 3 years in total contingent upon the outstanding performance of the researcher. The expected appointment date is September 1, 2022. This is a purely research position and will have no teaching duties.

A complete application packet should include:

  1. AMS standard cover sheet (preferred) or cover letter (PDF format)
  2. Curriculum vitae including a publication list (PDF format)
  3. Research statement (PDF format)
  4. Consent to Collection and Use of Personal Information (PDF file)
  5. At least 3 recommendation letters

For full consideration, applicants should email items 1, 2, 3, and 4 and arrange their recommendation letters emailed to dimag@ibs.re.kr by December 5, 2021, Sunday.

Recommendations letters forwarded by an applicant will not be considered.

DIMAG encourages applications from individuals of diverse backgrounds.

The rank-3 excluded minors for GF(5)-representability

This past spring, Jim Geelen and I co-supervised Timothy Wahyudi, an undergraduate researcher who did the actual coding for this project. Using computer searches, we hoped to get a better sense of how the excluded minors for $\text{GF}(5)$-representability are distributed and to see what we could say about their structures. This being a difficult problem, the main resolution was generating the complete list of the rank-$3$ excluded minors. All the excluded minors for $\text{GF}(5)$-representability on up to nine elements have already been determined (in any rank) [MR09], while $U_{2,7}$ is known to be the only rank-$2$ excluded minor. We found that there are a total of eighteen rank-$3$ excluded minors and they have the following distribution.

$n$Number of $n$-element rank-$3$ excluded minors for
$\text{GF}(5)$-representability
$n<7$$0$
$7$$5$
$8$$2$
$9$$9$
$10$$1$
$11$$1$
$n>11$$0$

The strategy

A naïve approach to finding all the rank-$3$ excluded minors is as follows.

  1. Generate all the simple $\text{GF}(5)$-representable matroids of rank $3$.
  2. Find all single-element extensions of these matroids.
  3. Filter out the extensions that are $\text{GF}(5)$-representable or contain a $U_{2,7}$-minor.
  4. Only keep those that are now restriction-minimal.

However, the simple, $\text{GF}(5)$-representable matroids of rank $3$ can have at most $|\text{PG}(2,5)|=31$ elements, so this would be computationally taxing. We do not want to generate matroids that cannot be extended to an excluded minor, so we should avoid using too many elements that do not help prevent possible $\text{GF}(5)$-representations in some way.

As Stefan van Zwam discussed in a previous post, stabilizers help distinguish between inequivalent representations. Recall that a matroid $N$ is a stabilizer for $\text{GF}(5)$-representability when, for each $\text{GF}(5)$-representation $A$ of $N$ and each $3$-connected matroid $M$ containing $N$ as a minor, there is at most one representation of $M$ (up to projective equivalence) that contains $A$ as a submatrix.

Lemma. Let $r\geq 2$. Let $N$ be a $3$-connected stabilizer for $\text{GF}(5)$-representability of rank $r$ and let $M$ be a rank-$r$ excluded minor for $\text{GF}(5)$-representability that contains $N$ as a restriction. For any representation $A$ of $N$, there is some subset $X\subseteq E(M)$ of size at most $r$ such that $A$ does not extend to a representation of $M|E(N)\cup X$.

Proof. Consider a fixed $\text{GF}(5)$-representation $A$ of $N$. For any $e\in E(M)-E(N)$, as $N$ is $3$-connected and has the same rank as $M$, we have that $M|E(N)\cup\{e\}$ is $3$- connected. We may assume that there is a representation of $M|E(N)\cup\{e\}$ of the form $[A|v_e]$ for some vector $v_e$ as otherwise we are done. As $N$ is a stabilizer, this representation extending $A$ is unique up to row operations and column scaling. However, as $N$ is connected and $E(N)$ is spanning, the submatrix $A$ uniquely determines the vector $v_e$ up to scaling.

Now consider the matrix $A’=[A|v_e]_{e\in E(M)-E(N)}$ where we extend $A$ by $v_e$ for each $e\in E(M)-E(N)$. As $M$ is not $\text{GF}(5)$-representable, there is some $X\subseteq E(M)$ of size at most $r$ such that the rank $X$ in $M$ disagrees with the rank of the set of columns of $A’$ indexed by $X$. As the choice of column vectors is unique (up to scaling), $A$ does not extend to a representation of $M|E(N)\cup X$. $\square$

By applying this lemma to each representation of a $3$-connected rank-$r$ stabilizer, we get the following.

Corollary. Let $M$ be a rank-$r$ excluded minor for $\text{GF}(5)$-representability that contains a $3$-connected rank-$r$ stabilizer $N$. Then there is a sequence of matroids $N=N_0,N_1,\dots,N_k=M$ such that $N_{i}$ is a single element extension of $N_{i-1}$ for $i$ in $\{1,\dots,k\}$, and for $i$ in $\{r,r+1,\dots,k\}$ there are strictly fewer inequivalent $\text{GF}(5)$-representations for $N_{i}$ than for $N_{i-r}$.

However, to use this to create a search strategy, it remains to be seen that every rank-$r$ excluded minor for $\text{GF}(5)$-representability actually contains a $3$-connected rank-$r$ stabilizer $N$. Here we can use the following theorem due to Whittle.

Theorem (Whittle [Whi99])

  • $U_{2,5}$ and $U_{3,5}$ are stabilizers for $\text{GF}(5)$-representability.
  • $U_{2,4}$ is a stabilizer for $\text{GF}(5)$-representability for matroids without a $U_{2,5}$ or a $U_{3,5}$ as a minor.

Furthermore, note that $\text{GF}(5)$-representable matroids without a $U_{2,4}$ minor are $\text{GF}(2)$-representable [Tut58] and have a unique $\text{GF}(5)$-representation [BL76] (see [Oxley] Theorem 6.5.4 and Proposition 6.6.5 respectively). Starting with these facts and using Seymour’s Splitter Theorem [Sey95] (see [Oxley] Corollary 12.2.1), one can check that the following holds.

Lemma. Each $3$-connected matroid with rank $r\geq3$ either

  • contains a $U_{3,5}$-minor as a stabilizer,
  • does not contain a $U_{3,5}$-minor and contains a minor isomorphic to the three-whirl, $\mathcal{W}^3$, as a stabilizer, or
  • does not have a $U_{2,4}$-minor and contains a minor isomorphic to the three-wheel, $\mathcal{W}_3=M(K_4)$, as a stabilizer.

(see also Proposition 12.2.15 and Corollary 12.2.19 in [Oxley]). One can do this more generally to find the list of appropriate $3$-connected rank-$r$ stabilizers for a given $r$.

As excluded minors for $\text{GF}(5)$-representability are $3$-connected, we can use the above lemmas to show that the following approach finds all the rank-$3$ excluded minors.

  1. Start with $U_{3,5}$ (six inequivalent representations), $\mathcal{W}^3$ (three inequivalent representations), and $\mathcal{W}_3$ (one inequivalent representation).
  2. By keeping track of inequivalent representations while extending matrices, find all $\text{GF}(5)$-representable matroids of rank-$3$ that are never more than $3$ deletions away from a $3$-connected rank-$3$ matroid with strictly more inequivalent $\text{GF}(5)$-representations.
  3. Find all single element extensions of these matroids.
  4. Filter out the extensions that are $\text{GF}(5)$-representable or contain a $U_{2,7}$.
  5. Only keep those that are now restriction-minimal.

The resulting collection of matroids is the set of rank-$3$ excluded minors for $\text{GF}(5)$-representability. I have included a geometric representations for each of them below and brief descriptions of their representabilities. 

The matroids

To avoid ambiguity, lines of the matroid do not cross in the diagram when they are drawn tangent to each other.

$U_{3,7}$ A rank-3 excluded minor for GF(5)-representability A rank-3 excluded minor for GF(5)-representability $\Delta-Y$ of $U_{2,7}$

  • The above matroids are each representable over a field $\mathbb{F}$ if and only if $|\mathbb{F}|\geq 7$. To see non-$\text{GF}(5)$-representability, we can consider intersections of lines in the ambient geometry to force the existence of a $U_{2,7}$-minor.

A rank-3 excluded minor for GF(5)-representability A rank-3 excluded minor for GF(5)-representability

  • These two matroids are each $\mathbb{F}$-representable if and only if $|\mathbb{F}|\geq 7$. To see non-$\text{GF}(5)$-representability, we can consider some of the points “at infinity” and check how we may arrange the remaining points in the affine plane over $\text{GF}(5)$.

For all the remaining examples, one can find three lines (not necessarily disjoint) whose union contains all the points of the matroid. If these lines are to be coincident in a representation we can obtain a system of additive relations, while if they are not we can obtain a system of multiplicative relations. We can check that there are no solutions in $\text{GF}(5)$ for whichever may be the case.

A rank-3 excluded minor for GF(5)-representability A rank-3 excluded minor for GF(5)-representability

A rank-3 excluded minor for GF(5)-representability A rank-3 excluded minor for GF(5)-representability

  • The four matroids above are also each $\mathbb{F}$-representable if and only if $|\mathbb{F}|\geq 7$.

The Fano matroid

  • The Fano matroid is the Reid geometry of order two and is $\mathbb{F}$-representable if and only if $\mathbb{F}$ has characteristic two.

$AG(2,3)\!\backslash\! e$

  • The ternary affine plane minus an element is $\mathbb{F}$-representable if and only if either $\mathbb{F}$ has characteristic three or there is a third root of unity.

Pappus matroid

  • The Pappus matroid is $\mathbb{F}$-representable if and only if either $|\mathbb{F}|=4$ or $|\mathbb{F}|\geq 7$.

non-Pappus matroid A rank-3 excluded minor for GF(5)-representability

Ried geometry of order four

A rank-3 excluded minor for GF(5)-representability A rank-3 excluded minor for GF(5)-representability

  • None of these are representable over any field and include the non-Pappus matroid (first) and the Reid geometry of order four (middle).

While there seem to be some nice patterns and symmetries here (some of which can be made more obvious with different drawings and groupings), to what extent they generalize or are useful remains to be seen.

References

  • [BL76] Brylawski, T.H. and Lucas, D. (1976). Uniquely representable combinatorial geometries. In Teorie combinatorie (Proc. 1973 Internat. Colloq.), 83–104. Accademia Nazionale dei Lincei, Rome.
  • [MR08] Mayhew, D. and Royle, G. (2008). Matroids with nine elements. J. Combin. Theory Ser. B 98, 415–431.
  • [Oxley] Oxley, J. (2011). Matroid Theory, 2nd edition. Oxford University Press.
  • [Sey95] Seymour, P. D. (1995). Matroid minors. In Handbook of combinatorics (eds. R. Graham, M. Grötschel, L. Lovász), 527–550. Elsevier, Amsterdam; MIT Press, Cambridge.
  • [Tut58] Tutte, W. T. (1958). A homotopy theorem for matroids, I, II. Trans. Amer. Math. Soc. 88, 144–174.
  • [Whi99] Whittle, G. (1999). Stabilizers of classes of representable matroids. J. Combin. Theory Ser. B 77, 39–72.