Every poset has a central element

DOI10.1016/0097-3165(85)90087-1zbMath0582.06002OpenAlexW1970716647MaRDI QIDQ1068859

Nathan Linial, Michael E. Saks

Publication date: 1985

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0097-3165(85)90087-1

zbMATH Keywords

finite posetbipartite graphscomplexity theoryorder idealsposets of height 1d-central elementhyperhraphsisomorphism problem for finite distributive lattices

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Partial orders, general (06A06) Searching and sorting (68P10) Extremal problems in graph theory (05C35) Graph theory (05C99)

Related Items

The average size of an independent set in graphs with a given chromatic number, On complexity of maximizatin of submodular functions^*, On searching a table consistent with division poset, Searching in random partially ordered sets, The average order of dominating sets of a graph, Searching monotone multi-dimensional arrays, On Generalized Comparison-Based Sorting Problems, An inequality for the sizes of prime filters of finite distributive lattices

Cites Work

• Counting antichains in finite partially ordered sets
• How good is the information theory bound in sorting?
• Correlation inequalities on some partially ordered sets
• The Information-Theoretic Bound is Good for Merging
• Searching ordered structures
• Information Bounds Are Weak in the Shortest Distance Problem
• An inequality for the weights of two families of sets, their unions and intersections
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item