%I #30 Oct 24 2024 12:33:10
%S 1,1,2,3,7,18,41,123,361,1257,4573
%N Number of connected graphs with n vertices which are realizable (in the sense of realizability of Gauss diagrams).
%C Consider a closed planar curve which crosses itself n times. Build a graph in which crossings are vertices, and two crossings c, d are not connected [connected] if respectively it is [is not] possible to travel along the curve from c to c without passing through d. A graph which can be produced in this way is called realizable. A classical related concept is that of a Gauss diagram (of a closed planar curve); realizable graphs are exactly the circle graphs of realizable Gauss diagrams.
%C The entries are produced by our code, and the entry for n=11 is corroborated by Section 4 in Bishler et al. which lists 6 pairs of alternating mutant knots of size 11. The entries for n=12, 13 are similarly corroborated by Stoimenow's data.
%D L. Bishler et al. "Distinguishing mutant knots." Journal of Geometry and Physics 159 (2021): 103928.
%H L. Bishler, et al., <a href="https://arxiv.org/abs/2007.12532">Distinguishing mutant knots</a>, arXiv:2007.12532 [hep-th], 2021.
%H Abdullah Khan, Alexei Lisitsa, Viktor Lopatkin, and Alexei Vernitski, <a href="https://arxiv.org/abs/2108.02873">Circle graphs (chord interlacement graphs) of Gauss diagrams: Descriptions of realizable Gauss diagrams, algorithms, enumeration</a>, arXiv:2108.02873 [math.GT], 2021.
%H Alexei Lisitsa, Abdullah Khan, and Alexei Vernitski, <a href="https://bcc2021.webspace.durham.ac.uk/wp-content/uploads/sites/84/2021/07/dayroomtime-2.pdf">An experimental approach to Gauss diagram realizability</a>, 28th British Comb. Conf., Durham Univ. (UK, 2021), p. 107.
%H Alexei Lisitsa and Alexei Vernitski, <a href="https://doi.org/10.1016/j.exco.2024.100162">Counting graphs induced by Gauss diagrams and families of mutant alternating knots</a>, Examples Counterex. (2024) Vol. 6, Art. No. 100162.
%H A. Stoimenow, <a href="http://stoimenov.net/stoimeno/homepage/ptab/">Knot data tables</a>.
%Y Cf. A002864, which starts with 1, 1, 2, 3, 7, 18, 41, 123, 367. This is because an alternating prime knot with 10 or fewer crossings is uniquely defined by the graph of the corresponding closed planar curve. Only starting from n=11 some alternating knots which share the same graph but are distinct knots (called "mutant knots") start appearing.
%Y Cf. A264759, which starts with 1, 1, 2, 3, 10; there is a mismatch starting from size 7. Indeed, starting from n=7 there are some planar curves which share the same graph but have distinct Gauss diagrams.
%K nonn,hard,more
%O 3,3
%A _Alexei Vernitski_, Apr 12 2021