Mathematics – Combinatorics
Scientific paper
2002-05-28
Mathematics
Combinatorics
Joined forces with Goemans and Vondrak---several new partial results; 28 pages, submitted to Adv. Appl. Math
Scientific paper
Say that mu is a ``subpartition'' of an integer partition lambda if the multiset of parts of mu is a submultiset of the parts of lambda, and define an integer partition lambda to be ``wide'' if for every subpartition mu of lambda, mu >= mu' in dominance order (where mu' denotes the conjugate or transpose of mu). Then Brian Taylor and the first author have conjectured that an integer partition lambda is wide if and only if there exists a tableau of shape lambda such that (1) for all i, the entries in the ith row of the tableau are precisely the integers from 1 to lambda_i inclusive, and (2) for all j, the entries in the jth column of the tableau are pairwise distinct. This conjecture was originally motivated by Rota's basis conjecture and, if true, yields a new class of integer multiflow problems that satisfy max-flow min-cut and integrality. Wide partitions also yield a class of graphs that satisfy ``delta-conjugacy'' (in the sense of Greene and Kleitman), and the above conjecture implies that these graphs furthermore have a completely saturated stable set partition. We present several partial results, but the conjecture remains very much open.
Chow Timothy Y.
Fan Kenneth C.
Goemans Michel X.
Vondrák Jan
No associations
LandOfFree
Wide partitions, Latin tableaux, and Rota's basis conjecture does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Wide partitions, Latin tableaux, and Rota's basis conjecture, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Wide partitions, Latin tableaux, and Rota's basis conjecture will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-560466