Skip to main content
edited tags
Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187
Became Hot Network Question
added 2 characters in body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

Let $I, J$ be two bases of a matroid. For every $x$ in $I$, there is some $y$ in $J$ such that, if we exchange $x$ with $y$, then both resulting sets ($I \setminus x \cup y$ and $J \setminus y \cup x$) are bases (this is the strong basis exchange property).

Can we extend this property as follows: there exists a bijection $f$ between $I\setminus J$ and $J\setminus I$, such that for every $x$ in $I$, if we exchange $x$ with $f(x)$, then both resulting sets are bases?

The nearest result I found was in lecture notes by Goemans. In Lemma 5, he proves that there is a perfect matching between $I\setminus J$ and $J\setminus I$ in a bipartite graph that he denotes by $D_M(I)$. This means that for every $x$ in $I$, if we exchange $x$ with $f(x)$, then $I \setminus x \cup f(x)$ is a base. But, it does not imply that $J \setminus f(x) \cup x$ is a base too.

Let $I, J$ be two bases of a matroid. For every $x$ in $I$, there is some $y$ in $J$ such that, if we exchange $x$ with $y$, then both resulting sets ($I \setminus x \cup y$ and $J \setminus y \cup x$) are bases (this is the strong basis exchange property).

Can we extend this property as follows: there exists a bijection $f$ between $I\setminus J$ and $J\setminus I$, such that for every $x$ in $I$, if we exchange $x$ with $f(x)$, then both resulting sets are bases?

The nearest result I found was in lecture notes by Goemans. In Lemma 5, he proves that there is a perfect matching between $I\setminus J$ and $J\setminus I$ in a bipartite graph that he denotes by $D_M(I)$. This means that for every $x$ in $I$, if we exchange $x$ with $f(x)$, then $I \setminus x \cup f(x)$ is a base. But, it does not imply that $J \setminus f(x) \cup x$ is base too.

Let $I, J$ be two bases of a matroid. For every $x$ in $I$, there is some $y$ in $J$ such that, if we exchange $x$ with $y$, then both resulting sets ($I \setminus x \cup y$ and $J \setminus y \cup x$) are bases (this is the strong basis exchange property).

Can we extend this property as follows: there exists a bijection $f$ between $I\setminus J$ and $J\setminus I$, such that for every $x$ in $I$, if we exchange $x$ with $f(x)$, then both resulting sets are bases?

The nearest result I found was in lecture notes by Goemans. In Lemma 5, he proves that there is a perfect matching between $I\setminus J$ and $J\setminus I$ in a bipartite graph that he denotes by $D_M(I)$. This means that for every $x$ in $I$, if we exchange $x$ with $f(x)$, then $I \setminus x \cup f(x)$ is a base. But, it does not imply that $J \setminus f(x) \cup x$ is a base too.

edited tags
Link
YCor
  • 63.9k
  • 5
  • 187
  • 286
Source Link
Loading