Timeline for Determining strong base-orderability of a matroid
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 14, 2021 at 18:18 | comment | added | Karagounis Z | Isn't the definition of strongly base-orderable that there is a bijection such that for every subset X of B1, that both B1 \ X + phi(X) AND B2 \ phi(X) + X are bases? I get this from here: en.wikipedia.org/wiki/Base-orderable_matroid | |
| Jan 20, 2015 at 17:33 | comment | added | Marek Adamczyk | Good point. Suppose we are given two bases, and we want to see whether they satisfy the strong exchange property in time polynomial in the rank. Assume we have an oracle that given a set tells us whether it's independent. For weak orderability it is possible in polynomial time, i.e., just construct a graph of possible exchanges and find a perfect matching. My main interest is in understanding whether it's the same situation here as with Hall's theorem for perfect matchings --- we run an algorithm polynomial in the number of vertices, but then we know Hall's condition holds for all subsets. | |
| Jan 20, 2015 at 1:05 | comment | added | Gordon Royle | How is the matroid given? | |
| Jan 16, 2015 at 0:42 | history | edited | Marek Adamczyk |
edited tags
|
|
| Jan 15, 2015 at 15:51 | review | First posts | |||
| Jan 15, 2015 at 15:54 | |||||
| Jan 15, 2015 at 15:47 | history | asked | Marek Adamczyk | CC BY-SA 3.0 |