Along some geometrical speculations, I came across a graph $\Gamma$ defined as follows:

Let $S$ be the set of vertices of a regular $n$-gon. Then the "vertices" of $\Gamma$ are the nonempty subsets of $S$ of fixed cardinality $k\leq n$. Two vertices $A,B\subset S$ are connected by an edge in $\Gamma$ iff $$Co(A)\cap Co(B)\neq\emptyset$$

where $Co(X)$ is the convex hull of $X$. So, $A$ and $B$ are connected if either they have a nonempty intersection, or they are "linked" in $\mathbb{S}^{1}$. In such a way, we get some graph $\Gamma(n,k)$.

My question: Does this graph have a name? Does it have some interesting properties? It seems pretty symmetric to me, in some sense.

Note that the graph $\Gamma(n,k)$ is "interesting" only for $k\leq\left[ \frac{n}{2}\right] $, otherwise it is a clique.

  • 3
    $\begingroup$ A maximal independent set on the graph that includes sets of all cardinality is a "noncrossing partition". And the relation you describe is the complement of the "noncrossing" relation. This paper seems to have something to say about the algebraic properties of this relation: arxiv.org/abs/1403.8133 $\endgroup$ – Yoav Kallus Oct 23 '16 at 21:25
  • $\begingroup$ This seems to be a special case of polygon-circle graph en.m.wikipedia.org/wiki/Polygon-circle_graph $\endgroup$ – Victor Oct 26 '16 at 13:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.