Forcing posets with large dimension to contain large standard examples

DOI10.1007/S00373-015-1624-4zbMATH Open1406.06001arXiv1402.5113OpenAlexW1740006672MaRDI QIDQ293603FDOQ293603

William T. Trotter, Csaba Biró, Peter Hamburger, Attila Pór

Publication date: 9 June 2016

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: The dimension of a poset $P$, denoted $dim(P)$, is the least positive integer $d$ for which $P$ is the intersection of $d$ linear extensions of $P$. The maximum dimension of a poset $P$ with $|P|le2n+1$ is $n$, provided $nge2$, and this inequality is tight when $P$ contains the standard example $S_n$. However, there are posets with large dimension that do not contain the standard example $S_2$. Moreover, for each fixed $dge2$, if $P$ is a poset with $|P|le2n+1$ and $P$ does not contain the standard example $S_d$, then $dim(P)=o(n)$. Also, for large $n$, there is a poset $P$ with $|P|=2n$ and $dim(P)ge(1-o(1))n$ such that the largest $d$ so that $P$ contains the standard example $S_d$ is $o(n)$. In this paper, we will show that for every integer $cge1$, there is an integer $f(c)=O(c^2)$ so that for large enough $n$, if $P$ is a poset with $|P|le2n+1$ and $dim(P)gen-c$, then $P$ contains a standard example $S_d$ with $dgen-f(c)$. From below, we show that $f(c)=Omega(c^{4/3})$. On the other hand, we also prove an analogous result for fractional dimension, and in this setting $f(c)$ is linear in $c$. Here the result is best possible up to the value of the multiplicative constant.

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

Recommendations

• Standard examples as subposets of posets.
• Random bipartite posets and extremal problems
• On an extremal problem for poset dimension
• Posets with large dimension and relatively few critical pairs
• On the fractional dimension of partially ordered sets

zbMATH Keywords

dimensionposetstandard examplewidth

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Combinatorics of partially ordered sets (06A07)

Cites Work

• Intransitive indifference with unequal indifference intervals
• On Dedekind's Problem: The Number of Isotone Boolean Functions. II
• Title not available (Why is that?)
• Partially Ordered Sets
• Dimension versus size
• The rank of a distributive lattice
• A combinatorial problem involving graphs and matrices
• The dimension of planar posets
• Maximal dimensional partially ordered sets. III: A characterization of Hiraguchi's inequality for interval dimension
• A bound on the dimension of interval orders
• The order dimension of the complete graph
• Dimension, graph and hypergraph coloring
• Fractional dimension of partial orders
• Standard examples as subposets of posets.
• The dimension of posets with planar cover graphs.
• Tree-width and dimension
• Maximal dimensional partially ordered sets. II: Characterization of 2n- element posets with dimension n
• A decomposition theorem for partially ordered sets
• Title not available (Why is that?)
• Large chromatic number and Ramsey graphs
• The dimension of random ordered sets
• Title not available (Why is that?)
• The proof of the removable pair conjecture for fractional dimension.
• Inequalities in Dimension Theory for Posets
• Title not available (Why is that?)
• Title not available (Why is that?)
• Dimension and matchings in comparability and incomparability graphs.
• On the size of maximal antichains and the number of pairwise disjoint maximal chains
• Adjacency posets of planar graphs

Cited In (6)

• Random bipartite posets and extremal problems
• On the fractional dimension of partially ordered sets
• Fractional local dimension
• Comparing Dushnik-Miller dimension, Boolean dimension and local dimension
• Trees and circle orders
• Dimension of posets with planar cover graphs excluding two long incomparable chains

This page was built for publication: Forcing posets with large dimension to contain large standard examples

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