Intersecting balanced families of sets
type: Item
instance of: scholarly article
title: Intersecting balanced families of sets
zbMATH Open document ID: 0972.05051
author: Adam Idzik
author: Rajiv Vohra
author: Gyula O. H. Katona
published in: Journal of Combinatorial Theory. Series A
publication date: 2001-11-09T00:00:00Z
full work available at URL: paper 90.pdf
review text: Let \(N\) be an \(n\)-element set and \({\mathcal A}\subseteq 2^N\). For \(A\in \mathcal A\) denote by \(\chi(A)\) the characteristic vector of \(A\). The family \(\mathcal A\) is called balanced, if \(\sum_{A\in\mathcal A} \chi(A)=(1,1,\dots,1)\). The authors study balanced families in which the intersection of any \(t\geq 2\) sets consists of at least \(k\geq 1\) elements. The main result is that the maximum size of a set \(A\) in \(\mathcal A\) is at least \(k^{1/t}b^{1-1/t}\). This bound follows from counting arguments. An algebraic construction is provided that shows that this lower bound is asymptotically sharp.
reviewed by: Sergej L. Bezrukov
Mathematics Subject Classification ID: 05D05
zbMATH DE Number: 1587279
zbMATH Keywords: intersecting family
zbMATH Keywords: balanced family
MaRDI profile type: Publication
OpenAlex ID: W2035703987
cites work: Long cycles in vertex-transitive graphs
cites work: Q5734002
cites work: Q4708452
cites work: Q3674431
cites work: Theorems on closed coverings of a simplex and their applications to cooperative game theory
cites work: Q4002255
cites work: Q4180391
cites work: The inequalities that determine the bargaining set \({\mathcal M}_ 1^ {(1)}\).
cites work: The kernel and bargaining set for convex games
cites work: The Core of an N Person Game
cites work: An existence theorem for a bargaining set
DOI: 10.1006/JCTA.2000.3078
description: scientific article; zbMATH DE number 1587279