On the extremal combinatorics of the Hamming space
type: Item
instance of: scholarly article
title: On the extremal combinatorics of the Hamming space
zbMATH Open document ID: 0826.05054
DOI: 10.1016/0097-3165(95)90019-5
author: János Körner
published in: Journal of Combinatorial Theory. Series A
publication date: 1995-11-26T00:00:00Z
review text: In \(n\)-dimensional Hamming space three points are on a line, if they satisfy the triangle inequality with equality. The paper introduces the following problem: How many different points can be found in the Hamming space so that no three of them are on a line (that is they are in general position)? This maximum value is \(A(n)\). The paper surveys the relation among \(A(n)\) and a number of well-known quantities from Hamming spaces and extremal set theory. Furthermore, the paper establishes inequalities for the exponential asymptotics \[ \alpha= \limsup_{n\to\infty} \textstyle{{1\over n}}\log A(n) \] showing that \(0,21\leq \alpha\leq 1/2\), improving some well-known older results.
Mathematics Subject Classification ID: 05D05
zbMATH DE Number: 774648
zbMATH Keywords: extremal combinatorics
zbMATH Keywords: (1,2)-separation
zbMATH Keywords: qualitative independence
zbMATH Keywords: Hamming space
zbMATH Keywords: triangle inequality
zbMATH Keywords: general position
zbMATH Keywords: extremal set theory
reviewed by: Péter L. Erdős
MaRDI profile type: Publication
full work available at URL: 0097-3165(95)90019-5
OpenAlex ID: W2017050610
cites work: How robust is the n-cube?
cites work: Q3977587
cites work: Q4745752
cites work: Families of finite sets in which no set is covered by the union of two others
cites work: Families of finite sets in which no set is covered by the union of \(r\) others
cites work: Combinatorial properties of systems of sets
cites work: Union-free hypergraphs and probability theory
cites work: A density version of the Hales-Jewett theorem
cites work: Qualitative independence and Sperner problems for directed graphs
cites work: Sperner capacities
cites work: Capacities: From information theory to extremal set theory
cites work: Subcube fault-tolerance in hypercubes
cites work: Optimal numberings and isoperimetric problems on graphs
cites work: Q3780312
cites work: Q4052170
cites work: Extremal problems for finite sets and convex hulls---a survey
cites work: Two applications (for search theory and truth functions) of Sperner type theorems
cites work: Q4140999
cites work: Q5525916
cites work: Nonrandom binary superimposed codes
cites work: Families of \(k\)-independent sets
cites work: Q4053473
cites work: Fredman–Komlós bounds and information theory
cites work: Intersection number and capacities of graphs
cites work: Compressing inconsistent data
cites work: New bounds for perfect hashing via information theory
cites work: Separating Partition Systems and Locally Different Sequences
cites work: A Sperner-type theorem and qualitative independence
cites work: Q4878288
cites work: Q5726070
cites work: Locality in Distributed Graph Algorithms
cites work: New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities
cites work: Small-Bias Probability Spaces: Efficient Constructions and Applications
cites work: Q3933030
cites work: On qualitatively independent partitions and related problems
cites work: Orthogonal partitions and covering of graphs
cites work: On the maximum number of qualitative independent partitions
cites work: Q5298115
cites work: On the upper bound of the size of the \(r\)-cover-free families
cites work: Vector sets for exhaustive testing of logic circuits
cites work: On restricted colourings of \(K_ n\)
cites work: Covering arrays and intersecting codes
cites work: Locality based graph coloring
cites work: On sets of integers containing k elements in arithmetic progression
cites work: Modular curves, Shimura curves, and Goppa codes, better than Varshamov-Gilbert bound
cites work: Coloring graphs with locally few colors
description: scientific article; zbMATH DE number 774648