Some greedy \(t\)-intersecting families of finite sequences
type: Item
instance of: scholarly article
title: Some greedy \(t\)-intersecting families of finite sequences
zbMATH Open document ID: 0882.05124
DOI: 10.1007/BF02029065
author: Shiquan Wu
published in: Acta Mathematicae Applicatae Sinica. English Series
publication date: 1998-02-04T00:00:00Z
review text: Let \(S(k_1,\dots,k_n)= \{a=(a_1,\dots, a_n)\mid a_i\in\{0,\dots,k_i\}\) for all \(i\}\). The \(p\)-support of \(a\) is defined to be \(s_p(a)= \{i\in\{1,\dots,n\}\mid a_i\geq p\}\). If \(F\subseteq S(k_1,\dots,k_n)\) then let \(s_p(F)=\{s_p(a)\mid a\in F\}\). For \(A\subseteq\{1,\dots,n\}\) let \(w_p(A)= p^{n-|A|}\prod_{i\in A} (a_i-p)\). A subset \(F\) of \(S(k_1,\dots,k_n)\) is called \(I^p_t\)-intersecting if for all \(a,b\in F\) there are at least \(t\) indices \(i\) with \(a_i\geq p\) and \(b_i\geq p\). Moreover, \(F\) is called greedy (resp. proper greedy) \(I^p_t\)-intersecting if it is \(I^p_t\)-intersecting and \(w_p(A)\geq w_p(B\cup A^c)\) (resp. \(w_p(A)> w_p(B\cup A^c)\)) for all \(A\in s_p(F)\) and all \(B\subseteq A\) with \(|B|= t-1\) (\(A^c\) is the complement of \(A\) in \(\{1,\dots,n\}\)). The author determines the maximum size of proper greedy \(I^p_t\)-intersecting families and, in the case \(k_1> k_2>\cdots> k_n\geq 2p\), the maximum size of greedy \(I^p_t\)-intersecting families.
Mathematics Subject Classification ID: 05D05
Mathematics Subject Classification ID: 06A07
zbMATH DE Number: 1062662
zbMATH Keywords: chain product
zbMATH Keywords: intersecting family
zbMATH Keywords: Erdös-Ko-Rado theorem
zbMATH Keywords: greedy
reviewed by: Konrad Engel
MaRDI profile type: Publication
cites work: Q3741626
cites work: Q3726125
cites work: Erdös–Ko–Rado Theorem—22 Years Later
cites work: An Erdős-Ko-Rado theorem for integer sequences of given rank
cites work: An extremal problem on the set of noncoprime divisors of a number
cites work: More on the Erdős-Ko-Rado theorem for integer sequences
cites work: An Intersection Theorem for a Collection of Families of Subsets of a Finite Set
cites work: Q4388460
cites work: Q3964569
full work available at URL: https://doi.org/10.1007/bf02029065
OpenAlex ID: W2323255273
description: scientific article; zbMATH DE number 1062662