scientific article; zbMATH DE number 1075005
Boolean latticecomplexityextremal configurationextremal graphextremal problems on posetsextremal setsforbidden substructuresintersecting familyKruskal-Katona type problemlinear latticemaximal cardinalityminimal cardinalityposetshadow-elementsshifting techniqueSperner theorysymmetric chain ordersTurán graphvector space
Our main result in Chapter 1 is a partial solution of the Kruskal-Katona type problem in the linear lattice \(L_n(2)\). One refers to a linear lattice \(L_n(q)\) as the poset of all subspaces of an \(n\)-dimensional vector space over a finite field \(F=\text{GF}(q)\) of \(q\) elements, ordered by inclusion. The shadow-elements in linear lattices are \((k-1)\)-dimensional subspaces and each of them is a subspace of at least one of the \(k\)-dimensional spaces in the family. We show how to minimize the cardinality of the shadow of two-dimensional spaces. The corresponding theorem has the following appearance. Theorem 0.4: For all \(m\in\mathbb{N}\) with \(m\leq{n\choose 2}_2\) and for all \(M\subseteq[n,2]_2\), where \(|M|=m\), the set of the \(m\) smallest elements with respect to \(<_{lex2}\), denoted by \(M^m_{lex2}\), satisfies: \(|\Delta M|\geq|\Delta M^m_{lex2}|\). We would like to mention that Theorem 0.4 and a dual version of it were conjectured by Bolze. She proved Theorem 0.4 for the special cases \(m={i\choose 2}_2\) where \(i\in\{2,3,\dots, n\}\). In order to prove Theorem 0.4 for all \(m\leq{n\choose 2}_2\) we apply some novel kind of shifting technique by using linear functions that operate on some subspaces of \(\text{GF}(2)^n\). Because of the known results in Sperner theory we focus our attention to so-called symmetric chain orders. In Chapter 3 we formulate and investigate a new problem for this class of posets. The investigation of a relaxation of this problem is the main task of Chapter 2. We decided to use this order for the chapters since the results of Chapter 2 are needed to prove some statements in Chapter 3. The new problem can be paraphrased in the following way: Let \(k,l\in\mathbb{N}\) be given. The forbidden substructures are chains \(C_k\) of size \(k\) and antichains \(A_l\) of size \(l\). Which symmetric chain orders, denoted by SCO, satisfy the following? There exists a maximal subposet of SCO with respect to cardinality which does not contain \(C_k\) or \(A_l\) and is ``induced by certain symmetric chains. Since symmetric chains have a simple structure, there will be no problem to describe the extremal sets. In Chapter 3 we show that the poset consisting of the product of two chains is such a symmetric chain order. In order to obtain an impression about the type of results concerning the new problem, we state a theorem about products of two chains. Theorem 0.6: For all \(k_1,k_2,k,l\in\mathbb{N}\) satisfying \(1<l\leq W\left(\left\lfloor{k_1+ k_2\over 2}\right\rfloor, S(k_1,k_2)\right)+ 1\) and \(1<k\leq k_1+k_2+ 2\) the following holds: \(f(S(k_1,k_2),k,l)=|\bigcup{\mathcal C}(S(k_1,k_2),l- 1,k-1)|\). In Theorem 0.6, \(\bigcup{\mathcal C}(S(k_1,k_2),l- 1,k- 1)\) denotes a maximal \(k,l\)-free subposet according to cardinality in the product of two chains \(S(k_1,k_2)\) of sizes \(k_1+1\) and \(k_2+1\). Furthermore we give several partial results in Chapters 2 and 3 concerning the Boolean lattice and arbitrary symmetric chain orders. For the complexity of the problems introduced and their classification in Sperner theory we refer to the beginnings of Chapters 2 and 3.
- Symmetric chain partitions of orthocomplemented posets
- Maximal chains in the fundamental order
- CONFIGURATIONS OF EXTREMAL EVEN UNIMODULAR LATTICES
- CONFIGURATIONS OF HIGHER ORDERS
- A weighted enumeration of maximal chains in the Bruhat order
- Counting weighted maximal chains in the circular Bruhat order
- Extremal polyomino chains with respect to Zagreb indices
- Symmetric chain decomposition of necklace posets
- On orthogonal symmetric chain decompositions
- On the symmetry and asymmetry of combinatorial structures
- A Kruskal-Katona type theorem for the linear lattice
- Typical values of extremal-weight combinatorial structures with independent symmetric weights
- On forbidden poset problems in the linear lattice
- Counting weighted maximal chains in the circular Bruhat order
- scientific article; zbMATH DE number 7217243 (Why is no real title available?)
- Optimal shadows and ideals in submatrix orders
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4359484)
