اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدLocal to global high dimensional expansion and Garlands method for general posets
154
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
In simplicial complexes it is well known that many of the global properties of the complex, can be deduced from expansion properties of its links. This phenomenon was first discovered by Garland [G]. In this work we develop a local to global machinery for general posets. We first show that the basic localization principle of Garland generalizes to more general posets. We then show that notable local to global theorems for simplicial complexes arise from general principles for general posets with expanding links. Specifically, we prove the following theorems for general posets satisfying some assumptions: Expanding links (one sided expansion) imply fast convergence of high dimensional random walks (generalization [KO,AL]); Expanding links imply Trickling down theorem (generalizing [O]); and a poset has expanding links (with two sided expansion) iff it satisfies a global random walk convergence property (generalization [DDFH]). We axiomatize general conditions on posets that imply local to global theorems. By developing this local to global machinery for general posets we discover that some posets behave better than simplicial complexes with respect to local to global implications. Specifically, we get a trickling down theorem for some posets (e.g. the Grassmanian poset) which is better behaved than the trickling down theorem known for simplicial complexes. In addition to this machinery, we also present a method to construct a new poset out of a pair of an initial poset and an auxiliary simplicial complex. By applying this procedure to the case where the pair is the Grassmanian poset and a bounded degree high dimensional expander, we obtain a bounded degree Grassmanian poset. We prove, using the tools described above, that this poset is a bounded degree expanding Grassmanian poset, partially proving a conjecture of [DDFH].
قيم البحث
اقرأ أيضاً
Motivated by generalizing Khovanovs categorification of the Jones polynomial, we study functors $F$ from thin posets $P$ to abelian categories $mathcal{A}$. Such functors $F$ produce cohomology theories $H^*(P,mathcal{A},F)$. We find that CW posets,
that is, face posets of regular CW complexes, satisfy conditions making them particularly suitable for the construction of such cohomology theories. We consider a category of tuples $(P,mathcal{A},F,c)$, where $c$ is a certain ${1,-1}$-coloring of the cover relations in $P$, and show the cohomology arising from a tuple $(P,mathcal{A},F,c)$ is functorial, and independent of the coloring $c$ up to natural isomorphism. Such a construction provides a framework for the categorification of a variety of familiar topological/combinatorial invariants: anything expressible as a rank-alternating sum over a thin poset.
We wish to renew the discussion over recent combinatorial structures that are 3-uniform hypergraph expanders, viewing them in a more general perspective, shedding light on a previously unknown relation to the zig-zag product. We do so by introducing
a new structure called triplet structure, that maintains the same local environment around each vertex. The structure is expected to yield, in some cases, a bounded family of hypergraph expanders whose 2-dimensional random walk converges. We have applied the results obtained here to several known constructions, obtaining a better expansion rate than previously known. Namely, we did so in the case of Conlons construction and the $S=[1,1,0]$ construction by Chapman, Linal and Peled.
In this work we show that high dimensional expansion implies locally testable code. Specifically, we define a notion that we call high-dimensional-expanding-system (HDE-system). This is a set system defined by incidence relations with certain high di
mensional expansion relations between its sets. We say that a linear code is modelled over HDE-system, if the collection of linear constraints that the code satisfies could by described via the HDE-system. We show that a code that can be modelled over HDE-system is locally testable. This implies that high dimensional expansion phenomenon solely implies local testability of codes. Prior work had to rely to local notions of local testability to get some global forms of testability (e.g. co-systolic expansion from local one, global agreement from local one), while our work infers global testability directly from high dimensional expansion without relying on some local form of testability. The local testability result that we obtain from HDE-systems is, in fact, stronger than standard one, and we term it amplified local testability. We further show that most of the well studied locally testable codes as Reed-Muller codes and more generally affine invariant codes with single-orbit property fall into our framework. Namely, it is possible to show that they are modelled over an HDE-system, and hence the family of all p-ary affine invariant codes is amplified locally testable. This yields the strongest known testing results for affine invariant codes with single orbit, strengthening the work of Kaufman and Sudan.
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.
We discuss the theory of certain partially ordered sets that capture the structure of commutation classes of words in monoids. As a first application, it follows readily that counting words in commutation classes is #P-complete. We then apply the par
tially ordered sets to Coxeter groups. Some results are a proof that enumerating the reduced words of elements of Coxeter groups is #P-complete, a recursive formula for computing the number of commutation classes of reduced words, as well as stronger bounds on the maximum number of commutation classes than were previously known. This also allows us to improve the known bounds on the number of primitive sorting networks.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
