2
$\begingroup$

I need to visualize the combination "a from n to k" using a graph $KG_{n,k}$ and depict the following:

https://en.wikipedia.org/wiki/Kneser_graph#/media/File:Kneser_graph_KG(5,2).svg

As we know, the graph structure is determined by the number of vertices and the connection between them (which is described by the adjacency matrix or incidence matrix, etc.).

From the graph tutorial Graph, I did not see that it was possible to work with matrices, so I had to create this graph manually, but it remained unclear to me how to make it look like this graph from Wikipedia.

Can someone work with me on this and show how this is done?

And the second question: is it possible to use the Mathematica to study its properties?

$\endgroup$
13
  • 2
    $\begingroup$ That looks awfully like PetersenGraph[5, 3]. $\endgroup$ – J. M.'s ennui May 6 '20 at 13:59
  • $\begingroup$ I don't understand what the question is. Are you trying to construct a specific graph? Are you trying to create a specific visualization of a given graph? What are the precise requirements? The question is not nearly focused enough. $\endgroup$ – Szabolcs May 6 '20 at 14:01
  • 2
    $\begingroup$ kneserGraph[n_, k_] := RelationGraph[ DisjointQ, Subsets[Range[n], {k}] ] $\endgroup$ – Szabolcs May 6 '20 at 14:01
  • $\begingroup$ I am trying to create a specific graph structure and visualize it so that it looks like a graph from Wikipedia. I do not know what commands to use for this. $\endgroup$ – dtn May 6 '20 at 14:02
  • 2
    $\begingroup$ There is way too much in this question. I strongly suggest you break it down, and proceed step by step, especially since you're a beginner (you do not seem to be familiar with function definitions). There are different tasks: how to create a Kneser graph? how to lay it out nicely? Here you show a very common layout of the Petersen graph, but it's unclear how to generalize this (the only one I know that can is one of the GraphViz layouts). The vast majority of automated layout methods cannot recover this layout. Then there's the question of how to create custom visualizations for each vertex. $\endgroup$ – Szabolcs May 6 '20 at 14:17
3
$\begingroup$
ClearAll[vSF]
vSF[n_, r_: .1, ps_: 15] := Module[{cp = CirclePoints[r/2, n]}, 
    Translate[Function[x, Join[{White, Disk[{0, 0}, r], Gray, AbsolutePointSize[ps]}, 
        MapAt[{Red, #} &, Point /@ cp, List /@ x], 
        MapThread[Text[Style[#, Black], #2] &, {x, cp[[x]]}]]]@#2, #]] &;

subsets = RotateRight @ SortBy[-Subtract @@ # &]@Subsets[Range[5], {2}];

cpoints = CirclePoints[.2, 5];


RelationGraph[DisjointQ, subsets, 
 VertexCoordinates -> Join[5 cpoints, 10 RotateRight@cpoints ], 
 VertexShapeFunction -> vSF[5, .3]]

enter image description here

RelationGraph[DisjointQ, Subsets[Range[6], {2}], 
 VertexShapeFunction -> vSF[6, .10, 12], ImageSize -> Large, 
 GraphLayout -> "CircularEmbedding"]

enter image description here

RelationGraph[DisjointQ, Subsets[Range[6], {3}], 
 VertexShapeFunction -> vSF[6, .1, 12], ImageSize -> Large, 
 GraphLayout -> "CircularEmbedding"]

enter image description here

RelationGraph[DisjointQ, Subsets[Range[7], {3}], 
 VertexShapeFunction -> vSF[7, .075, 9], ImageSize -> Large, 
 GraphLayout -> "CircularEmbedding"]

enter image description here

$\endgroup$
7
  • $\begingroup$ Wow! This is similar to what I wanted to get. And can we use this command to build Kneser's graphs of a different structure, for example, $KG_{8,3}$? $\endgroup$ – dtn May 6 '20 at 14:20
  • $\begingroup$ Your code visualize the graph well, but do not quite correctly display its structure. cp = MapAt[{Red, AbsolutePointSize[10], #} &, Point /@ CirclePoints[.2, 6], List /@ #] & /@ Subsets[Range[6], {3}]; PetersenGraph[6, 3, VertexShapeFunction -> ({White, Disk[#, .35], Gray, AbsolutePointSize[10], Translate[cp[[#2]], #]} &)] Is the graph built by this code true? $\endgroup$ – dtn May 6 '20 at 14:25
  • $\begingroup$ @dtn, getting the vertex layout right is the challenge for the general case. $\endgroup$ – kglr May 6 '20 at 16:52
  • $\begingroup$ In general, maybe there are other ways to visualize combinations from "a from n by k" besides Kneser's graphs? $\endgroup$ – dtn May 6 '20 at 16:54
  • $\begingroup$ Why is graph $KG_{6,3}$ so strange? It seems that three lines should come from one node, but why does one come out for some reason? $\endgroup$ – dtn May 7 '20 at 5:25

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.