185 reputation
28
bio website people.cs.uu.nl/bart
location Utrecht, The Netherlands
age
visits member for 4 years, 7 months
seen May 23 '13 at 8:44

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.