Bart Jansen
Reputation
210
Top tag
Next privilege 250 Rep.
 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.