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