More about shifting techniques
Let \(\mathcal B\) be a \(k\)-uniform set system on the set \([n]\) of the first \(n\) integers. For \(i,j \in [n]\) denote \(S_{ij}({\mathcal B})\) the well-known shifting (or exchange) operation on the set system. If \(i < j\) (\(i > j\)) then it is called left (right) shifting. A set system is left (right) shifted, if no left (right) shift changes the system. It is well known, that the shifting operations keep the cardinality of the set systems, and every system can be brought to a left (right) shifted family by successive left (right) shifting operations. The shifting operation plays a central role in the extremal set theory, especially in the proof of the Kruskal-Katona and Erdős-Ko-Rado theorems. This very important paper introduces a new type of shifting operation: the right-left shifting. For integers \(1 \leq j \leq i < u\) the RL-shift \(S_{ij|u}\) of a set system consists of two parts. First apply the right shift \(S_{ij}\) for the subsystem containing the element \(u,\) then apply iteratively the left shifts \(S_{ru}\) for all \(r=1,\dots , u-1.\) For an element \(u \in \bigcup {\mathcal A},\) the set system \(\mathcal A\) is called RL\(_u\)-stable, if any number of iteratively applied RL-shifts \(S_{ij|u}\) keep the cardinality of the set subsystem of \(\mathcal A\) containing \(u.\) Furthermore it is RL-stable, if it is \(\text{RL}_u\)-stable for every \(u.\) As it is shown in the paper, if a set system is RL-stable, then it is an initial segment of the colex order of all \(k\)-element subsets. Furthermore any \(k\)-uniform set system can be brought to an RL-stable set system with iterative RL-shiftings. Therefore the classical Kruskal-Katona theorem can be proved without any further argument using RL-shiftings. Finally the paper contains some other useful results as well.
- scientific article; zbMATH DE number 4029608
- Characterizing maximal shifted intersecting set systems and short injective proofs of the Erdős-Ko-Rado and Hilton-Milner theorems
- Beyond the Erdős-Ko-Rado theorem
- Stability theorems for some Kruskal-Katona type results
- scientific article; zbMATH DE number 736295
- Minimal families in terms of double-sided shadow in the Boolean cube layer
- scientific article; zbMATH DE number 4029608 (Why is no real title available?)
- Minimizing the weight of ideals in a layer of the Boolean cube
- Nonexistence of a Kruskal-Katona type theorem for double-sided shadow minimization in the Boolean cube layer
- On shift stable hypergraphs
This page was built for publication: More about shifting techniques
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1399692)
