Bounding one-way differences
type: Item
instance of: scholarly article
title: Bounding one-way differences
zbMATH Open document ID: 0663.05003
DOI: 10.1007/BF01788556
author: János Pach
author: Peter Frankl
author: Zoltán Füredi
published in: Graphs and Combinatorics
publication date: 1987-01-01T00:00:00Z
review text: Let f(n,k) denote the maximum length of a sequence \((F_ 1,F_ 2,...)\) of distinct subsets of an n-element set with the property that \(| F_ i\setminus F_ j| <k\) for all \(i<j\). We determine the exact values of f(n,2) and characterize all the extremal sequences. For \(k\geq 3\) we prove that \(f(n,k)=(1+o(1))\left( \begin{matrix} n\\ k\end{matrix} \right).\) Some related problems are also considered.
Mathematics Subject Classification ID: 05A05
Mathematics Subject Classification ID: 05B10
zbMATH DE Number: 4083628
zbMATH Keywords: maximum length
zbMATH Keywords: distinct subsets
zbMATH Keywords: exact values
zbMATH Keywords: extremal sequences
MaRDI profile type: Publication
cites work: General forbidden configuration theorems
cites work: Forbidden submatrices
cites work: INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
cites work: Families of finite sets satisfying a union condition
cites work: Q4184835
cites work: Q4724635
cites work: On the trace of finite sets
cites work: On the number of sets in a null t-design
cites work: Intersection theorems with geometric consequences
cites work: On the density of families of sets
cites work: A combinatorial problem; stability and order for models and theories in infinitary languages
full work available at URL: https://doi.org/10.1007/bf01788556
OpenAlex ID: W2021769154
Recommended article: Q3496342
Recommended article: On the Method of Typical Bounded Differences
Recommended article: Q4208448
Recommended article: One-Sided Simultaneous Bounds in Linear Regression
Recommended article: Q4821463
Recommended article: Estimating one of two normal means when their difference is bounded
Recommended article: Bounding differences in Jager pairs
Recommended article: One-sided confidence intervals in discrete distributions
description: scientific article; zbMATH DE number 4083628