Antimatroids and balanced pairs

DOI10.1007/S11083-013-9289-1zbMATH Open1292.05074arXiv1302.5967OpenAlexW3106223539MaRDI QIDQ2454046FDOQ2454046

Authors: David Eppstein 

Publication date: 12 June 2014

Published in: Order (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

Cited In (4)

• Title not available (Why is that?)
• Improving the \(\frac{1}{3}\)-\(\frac{2}{3}\) conjecture for width two posets
• Two Characterizations of Antimatroids
• Title not available (Why is that?)

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)