Qualitative independence and Sperner problems for directed graphs
type: Item
instance of: scholarly article
title: Qualitative independence and Sperner problems for directed graphs
zbMATH Open document ID: 0765.05007
DOI: 10.1016/0097-3165(92)90016-N
author: Luisa Gargano
author: János Körner
author: Ugo Vaccaro
published in: Journal of Combinatorial Theory. Series A
publication date: 1993-01-17T00:00:00Z
review text: Two \(k\)-partitions, \({\mathcal P}=\{P_ 1,\dots,P_ k\}\) and \({\mathcal P}'=\{P_ 1',\dots,P_ k'\}\) are called qualitatively independent, if \(P_ i\cap P_ j'\) is never empty. Let \(N(n,k)\) denote the largest size of a family of pairwise qualitative independent \(k\)-partitions on \(n\) elements. It is shown that \(\limsup_ n{1\over n}\log N(n,3)\geq.483\) and improved lower bounds are given also for \(4\leq k\leq 13\). The problem is related to that of the Shannon capacity of a graph.
Mathematics Subject Classification ID: 05A18
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05D05
zbMATH DE Number: 96571
zbMATH Keywords: qualitative independence
zbMATH Keywords: Sperner problems
zbMATH Keywords: directed graphs
zbMATH Keywords: Sperner family
zbMATH Keywords: \(k\)-partitions
zbMATH Keywords: Shannon capacity
reviewed by: László A. Székely
MaRDI profile type: Publication
cites work: Q4099676
cites work: Q5615282
cites work: On generalized graphs
cites work: Q5805073
cites work: Q3977587
cites work: A Sperner-type theorem and qualitative independence
cites work: On the Shannon capacity of a graph
cites work: On the maximum number of qualitative independent partitions
cites work: Q5298115
full work available at URL: 0097-3165(92)90016-n
OpenAlex ID: W2064830370
description: scientific article; zbMATH DE number 96571