Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLocal $t$-dimension
52
0
0.0
(
0
)
Authors
David Lewis
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
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 $q,t$-Catalan number $mathrm{Cat}_n(q,t)$ enumerates integer partitions contained in an $ntimes n$ triangle by their dinv and external area statistics. The paper [LLL18 (Lee, Li, Loehr, SIAM J. Discrete Math. 32(2018))] proposed a new approach to understanding the symmetry property $mathrm{Cat}_n(q,t)=mathrm{Cat}_n(t,q)$ based on decomposing the set of all integer partitions into infinite chains. Each such global chain $mathcal{C}_{mu}$ has an opposite chain $mathcal{C}_{mu^*}$; these combine to give a new small slice of $mathrm{Cat}_n(q,t)$ that is symmetric in $q$ and $t$. Here we advance the agenda of [LLL18] by developing a new general method for building the global chains $mathcal{C}_{mu}$ from smaller elements called local chains. We define a local opposite property for local chains that implies the needed opposite property of the global chains. This local property is much easier to verify in specific cases compared to the corresponding global property. We apply this machinery to construct all global chains for partitions with deficit at most $11$. This proves that for all $n$, the terms in $mathrm{Cat}_n(q,t)$ of degree at least $binom{n}{2}-11$ are symmetric in $q$ and $t$.
In many proofs concerning extremal parameters of Berge hypergraphs one starts with analyzing that part of that shadow graph which is contained in many hyperedges. Capturing this phenomenon we introduce two new types of hypergraphs. A hypergraph $mathcal{H}$ is a $t$-heavy copy of a graph $F$ if there is a copy of $F$ on its vertex set such that each edge of $F$ is contained in at least $t$ hyperedges of $mathcal{H}$. $mathcal{H}$ is a $t$-wise Berge copy of $F$ if additionally for distinct edges of $F$ those $t$ hyperedges are distinct. We extend known upper bounds on the Turan number of Berge hypergraphs to the $t$-wise Berge hypergraphs case. We asymptotically determine the Turan number of $t$-heavy and $t$-wise Berge copies of long paths and cycles and exactly determine the Turan number of $t$-heavy and $t$-wise Berge copies of cliques. In the case of 3-uniform hypergraphs, we consider the problem in more details and obtain additional results.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
