Large independent sets in shift-invariant graphs (Q1100485)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Large independent sets in shift-invariant graphs
scientific article

    Statements

    Large independent sets in shift-invariant graphs (English)
    0 references
    1987
    0 references
    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\).
    0 references
    0 references
    independent set
    0 references
    shift invariant hypergraphs
    0 references
    independent hypergraphs
    0 references
    uniform hypergraphs
    0 references
    0 references

    Identifiers