More about shifting techniques (Q1399692): Difference between revisions
From MaRDI portal
Removed claims |
Set OpenAlex properties. |
||
(3 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: Rudolf Ahlswede / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Harout Aydinian / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Levon H. Khachatrian / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Péter L. Erdős / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A simple proof of the Kruskal-Katona theorem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3770569 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4071752 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Combinatorial Problem in the k-Adic Number System / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/s0195-6698(03)00032-5 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2025473674 / rank | |||
Normal rank |
Latest revision as of 10:21, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | More about shifting techniques |
scientific article |
Statements
More about shifting techniques (English)
0 references
30 July 2003
0 references
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.
0 references
shifting
0 references
shadow
0 references
Kruskal-Katona theorem
0 references