Sperner's problem for G-independent families

DOI10.1017/S0963548314000558MaRDI QIDQ5364241zbMATH OpenOpenAlexFDO

Authors Victor Falgas-Ravry

Publication date 4 October 2017

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1302.6039

Mathematics Subject Classification ID

Extremal set theory (05D05)

Abstract: Given a graph G, let Q(G) denote the collection of all independent (edge-free) sets of vertices in G. We consider the problem of determining the size of a largest antichain in Q(G). When G is the edge-less graph, this problem is resolved by Sperner's Theorem. In this paper, we focus on the case where G is the path of length n-1, proving the size of a maximal antichain is of the same order as the size of a largest layer of Q(G).

Recommendations

• scientific article; zbMATH DE number 4083627
• scientific article; zbMATH DE number 4064987
• A generalization of the independence number
• Maximum antichains in random subsets of a finite set
• The poset on connected graphs is Sperner

Cites work

• A decomposition theorem for partially ordered sets
• A short proof of Sperner's lemma
• Distinct representatives of subsets
• Generalization of Sperner’s Theorem on the Number of Subsets of a Finite Set
• scientific article; zbMATH DE number 1186099 (Why is no real title available?)
• scientific article; zbMATH DE number 3672329 (Why is no real title available?)
• scientific article; zbMATH DE number 3489128 (Why is no real title available?)
• scientific article; zbMATH DE number 1016362 (Why is no real title available?)
• scientific article; zbMATH DE number 3189757 (Why is no real title available?)
• INTERSECTING FAMILIES OF SEPARATED SETS
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Logarithmic order of free distributive lattice
• On generalized graphs
• Skewincidence

Cited in

(1)

• A generalization of the independence number

This page was built for publication: Sperner's problem for \(G\)-independent families

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5364241)