Decompositions of partially ordered sets into chains and antichains of given size
In the paper under review the authors determine asymptotically best possible lower bounds for the size of structures which can be decomposed into quasi-regular substructures of given size. Example: Every poset P on at least \((l+o(l))n^ 3\) elements can be decomposed into subposets of size n that are ``almost'' chains or antichains and this lower bound on P is asymptotically best possible. Other examples are sequences of distinct real numbers, increasing sequences of natural numbers, \(\Delta\)-systems in t-uniform set systems, \(\Delta\)-systems in graphs, rainbow subgraphs in sub-k colorings of graphs and independent sets in \(K_ t\)-free graphs. The quasi-regularity is well defined and a decomposition lemma is fundamental for the proofs.
\(\Delta\)-systems in t-uniform set systems
rainbow subgraphs in sub-k colorings of graphs
independent sets in \(K_ t\)-free graphs
scientific article; zbMATH DE number 4087722