Timeline for Number of bases of a matroid
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 28, 2015 at 4:03 | comment | added | Suvrit | 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. | |
| Jul 28, 2015 at 1:52 | comment | added | David E Speyer | 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$. | |
| Jul 28, 2015 at 1:19 | comment | added | Suvrit | 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.. | |
| Jul 27, 2015 at 23:49 | vote | accept | Quentin Fortier | ||
| Jul 27, 2015 at 20:32 | comment | added | David E Speyer | @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))$. | |
| Jul 27, 2015 at 20:15 | comment | added | Timothy Chow | 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). | |
| Jul 27, 2015 at 19:04 | history | edited | David E Speyer | CC BY-SA 3.0 |
added 297 characters in body
|
| Jul 27, 2015 at 17:16 | history | answered | David E Speyer | CC BY-SA 3.0 |