On the maximum size of \((p,Q)\)-free families
type: Item
instance of: scholarly article
title: On the maximum size of \((p,Q)\)-free families
zbMATH Open document ID: 1012.05119
DOI: 10.1016/S0012-365X(02)00437-5
author: Miklós Ruszinkó
author: Zoltán Füredi
author: András Gyárfás
published in: Discrete Mathematics
publication date: 2002-12-02T00:00:00Z
review text: For a given integer \(p\) and a subset \(Q\) of \(\{0,1,\dots,p\}\), a family \(\{A_1,\dots,A_p\}\) of subsets of a set \(X\) is called a \((p,Q)\)-system, if \(|\{i\mid x\in A_i\}|\in Q\). A family \(\mathcal F\) on a set \(X\) is called \((p,Q)\)-free if no \(p\) sets of \(\mathcal F\) form a \((p,Q)\)-system. Denote \(f(n,p,Q)=\max|\mathcal F|\), where \(n=|X|\) and the maximum is running over all \((p,Q)\)-free families on \(X\). The authors survey the known results for the cases \(f(n,p,Q)=o(2^n)\) and \(2^n-(2-c)^n < f(n,p,Q)\) and emphasize the middle zone \(2^{n-1}\leq f(n,p,Q) \leq (1-c)2^n\). They provide a number of lower and upper bounds for particular \(Q\)'s and also several sharp results.
reviewed by: Sergej L. Bezrukov
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05D05
zbMATH DE Number: 1839000
zbMATH Keywords: hypergraph
zbMATH Keywords: degree
zbMATH Keywords: regular
MaRDI profile type: Publication
full work available at URL: s0012-365x(02)00437-5
OpenAlex ID: W2161189394
description: scientific article; zbMATH DE number 1839000