Combinatorics Seminar

When: Sunday, March 29, 10am Where: Schreiber 309 Speaker: Ron Aharoni, Technion Title: Adding a matroid for almost free

Abstract:

Here are three famous conjectures:

Conjecture 1 [Goldberg-Seymour]: In a multigraph $\chi_e \le \chi_e^*+1$. ($\chi_e$ is the edge-chromatic number.)

Conjectue 2 [Ryser - Brualdi - Stein] Every Latin square of order $n$ has a permutation submatrix with at least $n-1$ distinct symbols.

Conjecture 3 [Rota] If $A_1, \ldots ,A_n$ are non-singular $n \times n$ matrices, then the multiset of the union of their column sets can be decomposed as $\bigcup_{i \le n} B_i$, each $B_i$ being a linearly independent set consisting of one column from each $A_i$.

These conjectures seem far apart, but in fact they (as well as some known theorems) are manifestations of the same mysterious phenomenon: the intersection of two matroids costs only the price of at most $1$ in the covering number (of vertices by edges), compared with the covering numbers of each of the two matroids separately; and it costs the price of at most $1$ in an ``independent representation'' parameter (exemplified in Conjecture 2).

Some results in this direction will be presented, based on works with Alon, Berger, Chudnovsky, Kotlar, Loebl and Ziv. The tools are mainly topological.