\(\newcommand{\R}{\mathbb{R}}\) \(\newcommand{\Z}{\mathbb{Z}}\) \(\newcommand{\N}{\mathbb{N}}\)
For what kind of feasible family \(\mathcal{F}\), is search over \(\mathcal{F}_b\) is easy?
Cycle
Given a (directed) graph, find a cycle.
Cycle
Given a (directed) graph, find a cycle.
Zero Base Problem
Given a matroid \(M\) and \(\ell:E\to \Z_k\). Find a base \(B\) such that \(\ell(B)=0\).
Theorem (Combinatorial)
If \(k\) is a prime power or product of two primes, then for any base \(B\), if there exists a zero base, then there exists a zero base \(D\) such that \(|B\setminus D|\leq k-1\).
Theorem (Algorithm)
If \(k\) is a prime power or product of two primes, then there exists an algorithm to find a zero base in a \(\Z_k\) labelled matroid of \(n\) elements in \(O((2k-1)^{k-1}n^c)\) time.
Zero base problem is FPT!
Definition (Partition Matroid)
A matroid \(M=(E,\mathcal{I})\) is a partition matroid if there is a partition \(E_1,\ldots,E_k\) of \(E\) and capacities \(a_1,\ldots,a_k\), such that a set \(I\) is independent if and only if \(|I\cap E_i|\leq a_i\).
Definition (Matroid Intersection)
For two matroids \(M_1=(E,\mathcal{I}_1)\) and \(M_2=(E,\mathcal{I}_2)\), the matroid intersection \(M=M_1\cap M_2\) is the set system \(M=(E,\mathcal{I}_1 \cap \mathcal{I}_2)\).
Optimization over matroid intersection takes polynomial time.
Lemma (Brualdi 1969)
Let \(B\) and \(D\) be bases, then there exists a bijection \(f:B\setminus D\to D\setminus B\), such that for all \(e\in B\setminus D\), \(B-e+f(e)\) is a base.
Theorem
If a matroid has a zero base in \(\Z_2\), then for any base \(B\), there exists an zero base \(D\) such that \(|B\setminus D|\leq 1\).
Proof: If \(B\) is a zero base, then we are done. Otherwise, \(B\) is a \(1\) base, then consider a bijection \(f:B\setminus D \to D\setminus B\). At least 1 \(e\in B\setminus D\), \(\ell(f(e))+\ell(e) = 1\). \(B-e+f(e)\) is a zero base.
The algorithm for finding a zero base over \(\Z_2\).
Definition (Strongly Base-orderable Matroid)
A matroid is strongly base-orderable, if for any bases \(B\) and \(D\), there exists a bijection \(f:B\setminus D\to D\setminus B\), such that for all \(X\subseteq B\setminus D\), \(B-X+f(X)\) is a base.
Similar proof show
Theorem
If a strongly base-orderable matroid has a zero base, then for any base \(B\), there exists an zero base \(D\) such that \(|B\setminus D|\leq k-1\).
Proximity Conjecture
If the matroid has a zero base in \(\Z_k\). Let \(B\) be the a base, there exists a zero base \(D\) such that \(|B\setminus D|\leq k-1\).
A \(O(n^{2(k-1)})\) time algorithm:
Total running time is \((2k-1)^k\) times matroid intersection.
Conjecture (Strong Proximity)
Let \(B\) be any base, for each \(b\in \Z_k\), if there exists a base \(D'\) such that \(\ell(D')=b\), then there exists a base \(D\) such that \(\ell(D)=b\) and \(|B\setminus D|\leq k-1\).
Observations:
A labelling isolates a base, if no other base has the same label sum.
Our main conjecture equivalent to the following:
Conjecture (Isolation)
For every block matroid of rank \(k\), there is no \(\Z_k\) labelling that isolates a block.
For a fixed \(k\), number of block matroid of rank \(k\) is finite. One can check the theorem is true for small \(k\)!
We’ve tested for \(k=2,3,4,5\), all of which are true.
Theorem (Isolation)
Let \(p\) be a prime. For every block matroid of rank \(p\), there is no \(\Z_p\) labelling that isolates a block.
Consider disjoint bases \(B\) and \(D\).
A pair \(e\in D\) and \(e'\not\in D\) is called trivially exchangeable, if \(\ell(e)=\ell(e')\) and \(D-e+e'\) is a base.
If \(D\) has a trivially exchangeable pair, then we are done.
If \(D\) does not have a trivially exchangable pair with label \(i\), then we claim \(r(E_i) = r(E_i\cap B)+r(E_i\cap D)\).
Theorem (Schrijver and Seymour 1990)
Let \(M\) be a matroid with bases \(\mathcal{B}\), let \(p\) be a prime number, \(\ell:E\to \Z_p\) a label function.
\[|\ell(\mathcal{B})|\geq \min\{p, \sum_{i\in \Z_p} r(E_i-r(M)+1)\}.\]
Pick a \(e\in D\), and consider the matroid \(M'=M-e\). \[\begin{aligned} &\left(\sum_{i\in \Z_p} r(E_i)\right) - r(M')+1\\ \geq& \left(\sum_{i\in \Z_p,\ell(e)\neq i} r(E_i\cap B) + r(E_i\cap D) \right)\\ & + r(E_{\ell(e)}\cap B) + (r(E_{\ell(e)}\cap D)-1) - p + 1\\ =& 2p-p \\ =& p\\ \end{aligned}\] \(M'\) has a base of every sum. There is a base \(D'\) in \(M'\) s.t \(\ell(D')=\ell(D)\), which is also a base in \(M\).
Conjecture (Schrijver-Seymour)
Let \(M\) be a matroid with bases \(\mathcal{B}\), let \(G\) be an abelian group and \(\ell:E\to G\) a label function. If \(H=Stab(\ell(M))\), then \[|\ell(\mathcal{B})|\geq |H|\cdot (\sum_{Q\in R/H} r(\ell^{-1}(Q))-r(M)+1)).\]
Theorem (Liu-X)
For any group \(G\) where Schrijver-Seymour conjecture is true, and a zero base exists, then for any base \(B\), there is a zero base \(D\) such that \(|B\setminus D|\leq |G|-1\).
Theorem (DeVos, Goddyn, and Mohar 2009)
Schrijver-Seymour conjecture is true if \(|G|=pq\) or \(G=\Z_{p^k}\), for prime \(p\) and \(q\).
Theorem
Let \(k\) be a power of a prime, or product of two primes. For a matroid \(M\), let \(B\) be a base, for each \(b\in \Z_k\), if \(D'\) such that \(\ell(D')=b\), then there exists a base \(D\) such that \(\ell(D)=b\) and and \(|B\setminus D|\leq k-1\).
Conjecture (Proximity for Optimization)
For any optimum base \(B\), either there exists an optimum zero base \(D\) such that \(|B\setminus D|\leq k-1\), or there is no zero base.
We verified this is true for \(\Z_3\) and \(\Z_4\).
\(D(G)\), the Davenport constant of a group \(G\), is the smallest number that any set of size \(D(G)\) must contain a non-empty subset that sums to 0.
\(D(G)\) can be much smaller than \(|G|\), but \(D(G)=|G|\) if \(G=\Z_k\).
Theorem
Let \(G\) be a group and \(M\) be a strongly base-orderable matroid. For any optimum base \(B\), either there exists a optimum zero base \(D\), such that \(|B\setminus D|\leq D(G)-1\), or there is no zero base.
Does the above theorem generalize to all matroids?
