Large independent sets in shift-invariant graphs
type: Item
instance of: scholarly article
title: Large independent sets in shift-invariant graphs
zbMATH Open document ID: 0641.05044
DOI: 10.1007/BF01788538
published in: Graphs and Combinatorics
publication date: 1987-01-01T00:00:00Z
review text: The author regards k-uniform hypergraphs \(G=(Z,E)\), where Z is the set of all integers. G is called shift-invariant if \(M\in E\to \{x+a/a\in M\}\in E\) for any \(a\in Z\). \(X\subseteq Z\) is called independent in G, if 2 \(X\cap E=\emptyset.\) The author proves that the Bergelsons theorem that for every shift invariant k-uniform hypergraph for every independent set X in G, \(d(X)=\lim_{n\to \infty}| X\cap [-n,n]| /(2n+1)=0\) is not valid. May be \(\mu (G)=\sup \{d(X)/d(X)\) exists and X is independent in \(G\}\). For \(k=2\) the author find a shift-invariant graph with \(\mu (G)>1/2-\epsilon\) for an arbitrary \(\epsilon >0\). For \(k'>k\) one can easily construct a k'-uniform G' with the same properties for any \(k'>k\).
reviewed by: G.Merkel
Mathematics Subject Classification ID: 05C65
zbMATH DE Number: 4043888
zbMATH Keywords: independent set
zbMATH Keywords: shift invariant hypergraphs
zbMATH Keywords: independent hypergraphs
zbMATH Keywords: uniform hypergraphs
author: Igor Kriz
MaRDI profile type: Publication
cites work: Kneser's conjecture, chromatic number, and homotopy
cites work: On sets of integers containing k elements in arithmetic progression
full work available at URL: https://doi.org/10.1007/bf01788538
OpenAlex ID: W2511975042
description: scientific article; zbMATH DE number 4043888