Antimatroids and balanced pairs

DOI10.1007/S11083-013-9289-1MaRDI QIDQ2454046zbMATH OpenOpenAlexFDO

Authors David Eppstein

Publication date 12 June 2014

Published in Order (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1302.5967

zbMATH Keywords

antimatroidbalanced pairelimination ordering\(\frac{1}{3}\)-\(\frac{2}{3}\) conjecture

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Combinatorics of partially ordered sets (06A07)

Abstract: We generalize the 1/3-2/3 conjecture from partially ordered sets to antimatroids: we conjecture that any antimatroid has a pair of elements x,y such that x has probability between 1/3 and 2/3 of appearing earlier than y in a uniformly random basic word of the antimatroid. We prove the conjecture for antimatroids of convex dimension two (the antimatroid-theoretic analogue of partial orders of width two), for antimatroids of height two, for antimatroids with an independent element, and for the perfect elimination antimatroids and node search antimatroids of several classes of graphs. A computer search shows that the conjecture is true for all antimatroids with at most six elements.

Recommendations

• Antimatroids induced by matchings
• Two Characterizations of Antimatroids
• Anti-matroids
• The intersection of matroids and antimatroids
• An algorithmic characterization of antimatroids
• scientific article; zbMATH DE number 2060847
• Two remarks concerning balanced matroids
• Matroids and antimatroids - a survey
• Antimatroids of finite character
• scientific article; zbMATH DE number 4191655

Cites work

• scientific article; zbMATH DE number 3652386 (Why is no real title available?)
• scientific article; zbMATH DE number 3757213 (Why is no real title available?)
• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• scientific article; zbMATH DE number 805057 (Why is no real title available?)
• A Characterization of Block-Graphs
• An algorithmic characterization of antimatroids
• Antimatroids, betweenness, convexity
• Balance theorems for height-2 posets
• Balanced pairs in partial orders
• Balancing pairs and the cross product conjecture
• Balancing poset extensions
• Combinatorial representation and convex dimension of convex geometries
• Excluded-minor characterizations of antimatroids arisen from posets and graph searches.
• Greedoids
• Learning spaces. Interdisciplinary applied mathematics
• New graph classes of bounded clique-width
• On metric properties of certain clique graphs
• On simple characterizations of k-trees
• Reverse search for enumeration
• Semiorders and the 1/3-2/3 conjecture
• Some aspects of perfect elimination orderings in chordal graphs
• The Information-Theoretic Bound is Good for Merging
• The Theory of Round Robin Tournaments
• The gold partition conjecture
• The theory of convex geometries

Cited in

(4)

• scientific article; zbMATH DE number 524124 (Why is no real title available?)
• Improving the \(\frac{1}{3}\)-\(\frac{2}{3}\) conjecture for width two posets
• Two Characterizations of Antimatroids
• scientific article; zbMATH DE number 6796464 (Why is no real title available?)

This page was built for publication: Antimatroids and balanced pairs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2454046)