Decompositions of partially ordered sets into chains and antichains of given size
type: Item
instance of: scholarly article
title: Decompositions of partially ordered sets into chains and antichains of given size
zbMATH Open document ID: 0665.06002
DOI: 10.1007/BF00354892
author: Yair Caro
author: Zsolt Tuza
published in: Order
publication date: 1988-01-01T00:00:00Z
review text: 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.
reviewed by: Konrad Engel
Mathematics Subject Classification ID: 06A06
Mathematics Subject Classification ID: 05C55
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 4087722
zbMATH Keywords: monotone sequence
zbMATH Keywords: lower bounds for the size of structures
zbMATH Keywords: quasi-regular substructures
zbMATH Keywords: chains
zbMATH Keywords: antichains
zbMATH Keywords: sequences of distinct real numbers
zbMATH Keywords: increasing sequences of natural numbers
zbMATH Keywords: \(\Delta\)-systems in t-uniform set systems
zbMATH Keywords: \(\Delta\)-systems in graphs
zbMATH Keywords: rainbow subgraphs in sub-k colorings of graphs
zbMATH Keywords: independent sets in \(K_ t\)-free graphs
zbMATH Keywords: decomposition
MaRDI profile type: Publication
cites work: Decomposition of large combinatorial structures
cites work: A decomposition theorem for partially ordered sets
cites work: Some remarks on the theory of graphs
cites work: Intersection Theorems for Systems of Sets
cites work: Q5759552
cites work: Decomposition of large uniform hypergraphs
cites work: Q5618396
description: scientific article; zbMATH DE number 4087722