An intersection theorem for weighted sets

C. Bey*

*Korrespondierende/r Autor/-in für diese Arbeit
6 Zitate (Scopus)

Abstract

A weight function ω: 2[n] → ℝ≥0 from the set of all subsets of [n] = {1,...,n} to the nonnegative real numbers is called shift-monotone in {m + 1,...,n} if ω({al,...,aj})≥ω({bl,...,b j}) holds for all {al,...,aj}, {bl,...,bj} ⊆ [n] with ai≤bi, i = 1,...,j, and if ω(A)≥ω(B) holds for all A, B ⊆ [n] with A ⊆ B and B\A⊆{m + 1,...,n}. A family ℱ ⊆ 2[n] is called intersecting in [m] if F ∩ G ∩ [m] ≠ ∅ for all F, G ∈ ℱ. Let ω(ℱ) = ΣF∈ℱ ω(F). We show that max {ω(ℱ): ℱ ⊆ 2[n], ℱ is intersecting in [n]} = max{ω(ℱ): ℱ ⊆ 2[n], ℱ is intersecting in [m]} provided that ⊆ is shift-monotone in {m + 1,...,n}. An application to the poset of colored subsets of a finite set is given.

OriginalspracheEnglisch
ZeitschriftDiscrete Mathematics
Jahrgang235
Ausgabenummer1-3
Seiten (von - bis)145-150
Seitenumfang6
ISSN0012-365X
DOIs
PublikationsstatusVeröffentlicht - 28.05.2001

Fingerprint

Untersuchen Sie die Forschungsthemen von „An intersection theorem for weighted sets“. Zusammen bilden sie einen einzigartigen Fingerprint.

Zitieren