Impact
~5k
people reached
- 0 posts edited
- 0 helpful flags
- 13 votes cast
Jul
2 |
awarded | Curious |
Jun
25 |
awarded | Promoter |
May
22 |
comment |
Checking whether an element is in all inclusion-wise maximal common independent sets of two matroids
Indeed, if there is a list of circuits then the alternative formulation is easy to verify. I'm interested in the setting where $M$ and $M'$ are given by independence oracles, and (even) in the setting where $M$ and $M'$ are transversal matroids represented by 2 set systems whose partial transversals are the independent sets of the matroids. |
May
8 |
revised |
Checking whether an element is in all inclusion-wise maximal common independent sets of two matroids
Added alternative formulation of the question. |
May
8 |
answered | shortest circuit/cocircuit problem on transversal matroids or Gammoids |
May
7 |
asked | Checking whether an element is in all inclusion-wise maximal common independent sets of two matroids |
Mar
14 |
comment |
Disjoint Maximum Independent Sets in $alpha$-critical graphs
I do indeed mean maxiMUM rather than maxiMAL. It is known that the alpha-critical bipartite graphs are exactly the perfect matchings, so these cannot give a counterexample: all perfect matchings have two disjoint maximum independent sets. |
Feb
13 |
awarded | Commentator |
Feb
13 |
comment |
Disjoint Maximum Independent Sets in $alpha$-critical graphs
You're right, of course. I should have added the condition that $G$ contains no isolated vertices, which I just did. (I'm used to thinking about the graphs as minor-minimal obstructions to having a vertex cover of a certain size; $\alpha$-critical graphs are only obstructions if they do not have any isolated vertices.) |
Feb
13 |
comment |
Disjoint Maximum Independent Sets in $alpha$-critical graphs
Thanks, Boris. The theorems in the book do not seem to answer my question, unfortunately. |
Feb
13 |
revised |
Disjoint Maximum Independent Sets in $alpha$-critical graphs
Added the condition that G does not have isolated vertices to the conjecture. Boris was kind enough to send me ``Matching Theory'', but it does not seem to contain relevant information. |
Feb
12 |
asked | Disjoint Maximum Independent Sets in $alpha$-critical graphs |
Mar
29 |
accepted | Large bicliques in r-partite graphs containing no independent sets having one vertex from each class |
Mar
26 |
revised |
Large bicliques in r-partite graphs containing no independent sets having one vertex from each class
deleted 3 characters in body |
Mar
26 |
asked | Large bicliques in r-partite graphs containing no independent sets having one vertex from each class |
Nov
7 |
asked | Proof technique for packing constant-size paths with degree constraints in a tree with a perfect matching |
Apr
8 |
awarded | Yearling |
Mar
2 |
comment |
Decreasing the size of integers in a multiset while maintaining the total order on sums of subsets
Thanks for your extensive answer and insights. The pointer to threshold logic was very valueable: it lead me to the paper "On the Size of Weights for Threshold Gates" by Johan Hastad ( nada.kth.se/~johanh/threshweights.pdf ) where it is shown that in this voting scheme setting (which corresponds to a threshold gate) numbers of O(n log n) bits always suffice. Using an ILP characterization one can show that numbers of poly(n) bits also suffice for the original question. Whether you can find such numbers in polynomial time remains an open question. |
Mar
2 |
accepted | Decreasing the size of integers in a multiset while maintaining the total order on sums of subsets |
Feb
10 |
comment |
Decreasing the size of integers in a multiset while maintaining the total order on sums of subsets
Using an ILP formulation is an interesting idea, but it seems hard to appropriately bound the size of the solution that is found (i.e. the size of the numbers in the solution). From an input multiset with $n$ numbers you get $2^n$ subsets and hence naively you would have to make $(2^n)^2$ inequalities in an ILP formulation. According to lecture notes from Kurt Mehlhorn, if an ILP has a solution that it has one whose integers are bounded by $4^{nL}$ where $L$ is the number of bits needed to describe the coefficient matrix; but then $L$ would be $\Omega((2^n)^2)$ so this is not yet good enough. |