I would like to know the minimum number of bases of a matroid of rank $k$ and $n$ elements, knowing that each singleton is independent. At least for small ranks.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ It would be more natural to also impose that there are no co-loops. (I.e. all singletons are independent in the dual matroid.) $\endgroup$– David E SpeyerCommented Jul 27, 2015 at 17:10
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
5
With the problem as stated, the answer is $n-k+1$. Take the uniform matroid of rank $1$ on $n-k+1$ elements and direct sum with $k-1$ co-loops. (Geometrically, take the standard basis $e_1$, $e_2$, ..., $e_k$ of $\mathbb{R}^k$ and duplicate the first basis element $n-k+1$ times.)
To see that this is optimal, suppose for the sake of contradiction that we could achieve $n-k$ bases: $B_1$, $B_2$, ..., $B_{n-k}$. Consider the exchange graph, where $B_i$ and $B_j$ are connected by an edge if $\#(B_i \setminus B_j)= \#(B_j \setminus B_i) = 1$. It is known to be connected. Reorder the $B_i$ such that the induced subgraph on $B_1$, $B_2$, ..., $B_r$ is connected. Then, for $2 \leq r \leq n-k$, there is at most one element of $B_r$ not in $\bigcup_{1 \leq i<r} B_i$. We deduce that $\# \bigcup_{1 \leq i \leq n-k} B_i \leq \# B_1 + (n-k-1) = n-1$. So there is some element not in $\bigcup B_i$, and this element is not independent.
As I commented above, I think it would be more natural to impose that $M$ has neither loops nor co-loops. The best I can find for that problem $k(n-k)$, by using $U(k-1,k) \oplus U(1, n-k)$, where $U(r,m)$ is the uniform matroid of rank $r$ on $m$ elements. If you ask for the matroid to be connected, I can achieve $k(n-k)+1$ by starting with $U(k,k+1)$ and replacing one element with $n-k$ parallel copies. I would guess these are optimal.
answered Jul 27, 2015 at 17:16
-
2$\begingroup$ If the matroid is connected then your bound of $k(n-k)+1$ is indeed optimal, as shown independently by Dinolt (An extremal problem for non-separable matroids, Théorie des Matroïdes, Lecture Notes in Mathematics Volume 211, 1971, pp 31–49) and Murty (On the number of bases of a matroid, Proc. Second Louisiana Conf. on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1971), pp 387–410). $\endgroup$ Commented Jul 27, 2015 at 20:15
-
$\begingroup$ @TimothyChow Thanks! And that means that the case of no loops and no co-loops reduces to a hopefully easy optimization problem: Minimize $\prod (a_i b_i+1)$, subject to $\sum a_i = k$, $\sum b_i = n-k$, and $a_i$, $b_i \geq 1$. My claim is that the optimum is $((a_1, b_1), (a_2, b_2)) = ((k-1,1), (1,n-k-1))$. $\endgroup$ Commented Jul 27, 2015 at 20:32
-
$\begingroup$ Is it really $a_i, b_i \ge 1$ for all $i$? In which case the unconstrained minimum value is with $a_i=b_i=1$ --- but this could violate the summation constraints, but in any case, this is going to be different from the $a_1,b_1$ claim in your comment.. $\endgroup$– SuvritCommented Jul 28, 2015 at 1:19
-
$\begingroup$ It really is $a_i$, $b_i \geq 1$. But choosing all $1$'s isn't optimal. But choosing all $1$'s isn't optimal. If $k=n-k$, then my choice of $(k-1,1)+(1,k-1)$ giving $k^2$ is much better than your choice of $(1,1)+(1,1) + \cdots + (1,1)$ giving $2^k$. $\endgroup$ Commented Jul 28, 2015 at 1:52
-
$\begingroup$ I was confused with the notation; if you only pick $a_1,b_1$ and $a_2, b_2$ but set the rest $a_i, b_i$ to zero, then the constraints $a_i,b_i \ge 1$ get violated. I guess, you are also optimizing over $k$ at the same time, not just over $a_i,b_i$, which explains my confusion! Thanks. $\endgroup$– SuvritCommented Jul 28, 2015 at 4:03
$\begingroup$
$\endgroup$
There are two additional bounds, to be found in:
Purdy, G. "The independent sets of rank k of a matroid." Discrete Mathematics 38.1 (1982): 87-91.
Björner, Anders. "Some matroid inequalities." Discrete Mathematics 31.1 (1980): 101-103.
Purdy gave lower bounds for the number of independent sets of some cardinality. When specialized to the rank (and switched to your notation because Purdy uses $k$ for the general cardinality and $d$ for the rank) his bound yields: $$ b(M) \geq \binom{n-k+2}{2}. $$
Björner showed that if the girth of the matroid is known (he denotes it by $c$) then even stronger bounds are available: $$ b(M) \geq \binom{n-k+c-1}{c-1}. $$
answered Apr 30, 2023 at 13:23