Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userBoolean dimension and local dimension
66
0
0.0
(
0
)
Added by
Bartosz Walczak
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Dimension is a standard and well-studied measure of complexity of posets. Recent research has provided many new upper bounds on the dimension for various structurally restricted classes of posets. Bounded dimension gives a succinct representation of the poset, admitting constant response time for queries of the form is $x<y$?. This application motivates looking for stronger notions of dimension, possibly leading to succinct representations for more general classes of posets. We focus on two: boolean dimension, introduced in the 1980s and revisited in recent research, and local dimension, a very new one. We determine precisely which values of dimension/boolean dimension/local dimension imply that the two other parameters are bounded.
rate research
Read More
We study covering numbers and local covering numbers with respect to difference graphs and complete bipartite graphs. In particular we show that in every cover of a Young diagram with $binom{2k}{k}$ steps with generalized rectangles there is a row or a column in the diagram that is used by at least $k+1$ rectangles, and prove that this is best-possible. This answers two questions by Kim, Martin, Masa{v{r}}{i}k, Shull, Smith, Uzzell, and Wang (Europ. J. Comb. 2020), namely: - What is the local complete bipartite cover number of a difference graph? - Is there a sequence of graphs with constant local difference graph cover number and unbounded local complete bipartite cover number? We add to the study of these local covering numbers with a lower bound construction and some examples. Following Kim emph{et al.}, we use the results on local covering numbers to provide lower and upper bounds for the local dimension of partially ordered sets of height~2. We discuss the local dimension of some posets related to Boolean lattices and show that the poset induced by the first two layers of the Boolean lattice has local dimension $(1 + o(1))log_2log_2 n$. We conclude with some remarks on covering numbers for digraphs and Ferrers dimension.
The asymptotic dimension is an invariant of metric spaces introduced by Gromov in the context of geometric group theory. In this paper, we study the asymptotic dimension of metric spaces generated by graphs and their shortest path metric and show their applications to some continuous spaces. The asymptotic dimension of such graph metrics can be seen as a large scale generalisation of weak diameter network decomposition which has been extensively studied in computer science. We prove that every proper minor-closed family of graphs has asymptotic dimension at most 2, which gives optimal answers to a question of Fujiwara and Papasoglu and (in a strong form) to a problem raised by Ostrovskii and Rosenthal on minor excluded groups. For some special minor-closed families, such as the class of graphs embeddable in a surface of bounded Euler genus, we prove a stronger result and apply this to show that complete Riemannian surfaces have Assouad-Nagata dimension at most 2. Furthermore, our techniques allow us to prove optimal results for the asymptotic dimension of graphs of bounded layered treewidth and graphs of polynomial growth, which are graph classes that are defined by purely combinatorial notions and properly contain graph classes with some natural topological and geometric flavours.
In this note, we introduce a new poset parameter called local $t$-dimension. We also discuss the fractional variants of this and other dimension-like parameters.
We present the Boolean dimension of a graph, we relate it with the notions of inner, geometric and symplectic dimensions and the rank and minrank of a graph. We obtain an exact formula for the Boolean dimension of a tree in terms of a certain star decomposition. We relate the Boolean dimension with the inversion index of a tournament.
It has been known for more than 40 years that there are posets with planar cover graphs and arbitrarily large dimension. Recently, Streib and Trotter proved that such posets must have large height. In fact, all known constructions of such posets have two large disjoint chains with all points in one chain incomparable with all points in the other. Gutowski and Krawczyk conjectured that this feature is necessary. More formally, they conjectured that for every $kgeq 1$, there is a constant $d$ such that if $P$ is a poset with a planar cover graph and $P$ excludes $mathbf{k}+mathbf{k}$, then $dim(P)leq d$. We settle their conjecture in the affirmative. We also discuss possibilities of generalizing the result by relaxing the condition that the cover graph is planar.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
