Fractional Local Dimension

DOI10.1007/S11083-020-09543-2MaRDI QIDQ6320475arXivFDO

Authors Heather Smith, William T. Trotter

Publication date 13 June 2019

Published in arXiv

Full work available at URL https://doi.org/10.1007/S11083-020-09543-2

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorics of partially ordered sets (06A07)

arXiv classification

math.CO

Abstract: The original notion of dimension for posets was introduced by Dushnik and Miller in 1941 and has been studied extensively in the literature. In 1992, Brightwell and Scheinerman developed the notion of fractional dimension as the natural linear programming relaxation of the Dushnik-Miller concept. In 2016, Ueckerdt introduced the concept of local dimension, and in just three years, several research papers studying this new parameter have been published. In this paper, we introduce and study fractional local dimension. As suggested by the terminology, our parameter is a common generalization of fractional dimension and local dimension. For a pair $(n,d)$ with $2led<n$, we consider the poset $P(1,d;n)$ consisting of all $1$-element and $d$-element subsets of $1,dots,n$ partially ordered by inclusion. This poset has fractional dimension $d+1$, but for fixed $dge2$, its local dimension goes to infinity with $n$. On the other hand, we show that as $n$ tends to infinity, the fractional local dimension of $P(1,d;n)$ tends to a value $extFLD(d)$ which we will be able to determine exactly. For all $dge2$, $extFLD(d)$ is strictly less than $d+1$, and for large $d$, $extFLD(d)simd/(logd-loglogd-o(1))$. As an immediate corollary, we show that if $P$ is a poset, and $d$ is the maximum degree of a vertex in the comparability graph of $P$, then the fractional local dimension of $P$, is at most $2+extFLD(d).$ Our arguments use both discrete and continuous methods.

This page was built for publication: Fractional Local Dimension

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