Effective Poset Inequalities

DOI10.1137/22M1532317zbMATH Open1520.05017arXiv2205.02798MaRDI QIDQ6046818FDOQ6046818

Authors: Swee Hong Chan, Igor Pak, Greta Panova 

Publication date: 6 September 2023

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: We explore inequalities on linear extensions of posets and make them effective in different ways. First, we study the Bj"orner--Wachs inequality and generalize it to inequalities on order polynomials and their $q$-analogues via direct injections and FKG inequalities. Second, we give an injective proof of the Sidorenko inequality with computational complexity significance, namely that the difference is in $$. Third, we generalize the Sidorenko inequality to posets with small chain intersections and give complexity theoretic applications.

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

Recommendations

• Log-concave poset inequalities (extended abstract)
• scientific article; zbMATH DE number 1488842
• On the posets \((\mathcal W_2^k,<)\) and their connections with some homogeneous inequalities of degree 2
• Multivariate correlation inequalities for \(P\)-partitions
• A correlational inequality for linear extensions of a poset

zbMATH Keywords

\(q\)-analogueslinear extensionshook-length formulaFKG inequalityorder polynomials\#P-complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) (q)-calculus and related topics (05A30) Combinatorics of partially ordered sets (06A07) Combinatorial inequalities (05A20)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Computing the Continuous Discretely
• Two poset polytopes
• Dual equivalence with applications, including a conjecture of Proctor
• Combinatorial Markov chains on linear extensions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computational Complexity
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Counting linear extensions
• The probabilistic method
• Title not available (Why is that?)
• Chromatic graph theory
• Correlation inequalities on some partially ordered sets
• Unimodality, log-concavity, real-rootedness and beyond
• The nature of computation
• Systems of equations with a single solution
• q-hook length formulas for forests
• Two combinatorial applications of the Aleksandrov-Fenchel inequalities
• Promotion and evacuation
• Promotion des morphismes d'ensembles ordonnes
• Title not available (Why is that?)
• A \(q\)-analogue of the FKG inequality and some applications
• On the complexity of computing Kronecker coefficients
• Inductive proofs of \(q\)-log concavity
• Reduced matrices and q-log-concavity properties of q-Stirling numbers
• How often are two permutations comparable?
• Order polynomials and Pólya's enumeration theorem.
• Product decompositions of the symmetric group induced by separable permutations
• Title not available (Why is that?)
• On the q-log-concavity of Gaussian binomial coefficients
• A Rogers-Ramanujan bijection
• Title not available (Why is that?)
• Deciding positivity of Littlewood-Richardson coefficients
• Title not available (Why is that?)
• On the conductance of order Markov chains
• \(q\)-analogues of Ehrhart polynomials
• On \(q\)-integrals over order polytopes
• Title not available (Why is that?)
• A recurrence for linear extensions
• The extremals of Minkowski's quadratic inequality
• On positivity of Ehrhart polynomials
• The XYZ conjecture and the FKG inequality
• A correlational inequality for linear extensions of a poset
• The FKG Inequality and Some Monotonicity Properties of Partial Orders
• A loop-free algorithm for generating the linear extensions of a poset
• Evacuation of labelled graphs
• When is the multiplicity of a weight equal to 1?
• Generating a random linear extension of a partial order
• On log concavity for order-preserving maps of partial orders
• Combinatorial applications of the Hodge-Riemann relations
• Geometrical techniques for estimating numbers of linear extensions
• Multivariate correlation inequalities for \(P\)-partitions
• Geometry and complexity of O'Hara's algorithm
• The bounds for the number of linear extensions via chain and antichain coverings
• Bijections related to statistics on words
• Counting linear extensions of restricted posets
• Inequalities for the number of linear extensions
• Upper Bounds on Mixing Time of Finite Markov Chains
• Asymptotics of the number of standard Young tableaux of skew shape
• Bijective proofs of the hook formula for rooted trees.
• Stanley's non-Ehrhart-positive order polytopes
• Separable elements and splittings of Weyl groups
• Why is pi less than twice phi?
• Promotion sorting
• Friends and strangers walking on graphs
• Introduction to the combinatorial atlas
• Skew shape asymptotics, a case-based introduction
• Hook inequalities
• Geometric inequalities for anti-blocking bodies
• Combinatorial Inequalities
• The hull metric on Coxeter groups
• The cross-product conjecture for width two posets
• Extensions of the Kahn-Saks inequality for posets of width two

Cited In (7)

• Log-concave poset inequalities (extended abstract)
• Log-concave poset inequalities
• Enumerative combinatorics. Abstracts from the workshop held December 11--17, 2022
• Extensions of the Kahn-Saks inequality for posets of width two
• Correlation inequalities for linear extensions
• On the posets \((\mathcal W_2^k,<)\) and their connections with some homogeneous inequalities of degree 2
• Equality cases of the Alexandrov-Fenchel inequality are not in the polynomial hierarchy

This page was built for publication: Effective Poset Inequalities

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