The hardness of the independence and matching clutter of a graph
Sasun Hambardzumyan, Vahan Mkrtchyan, Vahe L. Musoyan, Hovhannes Sargsyan · Opuscula Mathematica · 2016
A clutter (or antichain or Sperner family) L is a pair (V, E), where V is a finite set and E is a family of subsets of V none of which is a subset of another.Usually, the elements of V are called vertices of L, and the elements of E are called edges of L. A subset se of an edge e of a clutter is called recognizing for e, if se is not a subset of another edge.The hardness of an edge e of a clutter is the ratio of the size of e's smallest recognizing subset to the size of e.The hardness of a clutter is the maximum hardness of its edges.We study the hardness of clutters arising from independent sets and matchings of graphs.