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 및 이메일 등에 표시하여 제출 필요. 다만 현역입영대상자의 전문연구요원 신규 편입은 불가하며, 보충역 대상자 및 타 기관에서 전직해서 오는 경우에 한하여 지원 가능(반드시 타 기관에서 전직 요건이 충족되는 등 전직 요건이 충족 되어야만 함)

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.

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.

• 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.

• 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.

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

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

• 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.

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

• 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.