5
$\begingroup$

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.

$\endgroup$
2
  • 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$ Oct 23, 2016 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, 2016 at 13:58

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.