More about shifting techniques (Q1399692): Difference between revisions

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.