Hamiltonian Paths in Distance Graphs

V. V. Utkin

Matematičeskie zametki, Tome 97 (2015) no. 6, pp. 904-916.

Résumé

The object of study is the graph $$ G(n,r,s)=(V(n,r),E(n,r,s)) $$ with \begin{align*} V(n,r)=\{v : v \subset \{1,\dots,n\}, \, |v|=r\}, \\ E(n,r,s)=\{\{v,u\} : v,u \in V(n,r), \, |v \cap u|=s\}; \end{align*} i.e., the vertices of the graph are $r$-subsets of the set $\mathcal{R}_n=\{1,\dots,n\}$, and two vertices are connected by an edge if these vertices intersect in precisely $s$ elements. Two-sided estimates for the number of Hamiltonian paths in the graph $G(n,k,1)$ as $n \to \infty$ are obtained.

Détail

Keywords: distance graph, Hamiltonian path, simple path, hypergraph.
Mots-clés : clique

Bibliographie

[1] F. Dzh. Mak-Vilyams, N. Dzh. A. Sloen, Teoriya kodov, ispravlyayuschikh oshibki, Radio i svyaz, M., 1979 | MR | MR | Zbl

[2] P. Brass, W. Moser, J. Pach, Research Problems in Discrete Geometry, Springer, New York, 2005 | MR | Zbl

[3] A. M. Raigorodskii, “Problema Borsuka i khromaticheskie chisla nekotorykh metricheskikh prostranstv”, UMN, 56:1 (2001), 107–146 | DOI | MR | Zbl

[4] A. M. Raigorodskii, “Coloring Distance Graphs and Graphs of Diameters”, Thirty Essays on Geometric Graph Theory, Springer, New York, 2013, 429–460 | MR | Zbl

[5] J. Pach, P. K. Agarwal, Combinatorial Geometry, Wiley-Intersci. Ser. Discrete Math. Optim., John Wiley and Sons, New York, 1995 | MR | Zbl

[6] A. M. Raigorodskii, “Problemy Borsuka i Gryunbauma dlya reshetchatykh mnogogrannikov”, Izv. RAN. Ser. matem., 69:3 (2005), 81–108 | DOI | MR | Zbl

[7] A. Soifer, The Mathematical Coloring Book. Mathematics of Coloring and the Colorful Life of its Creators, Springer, New York, 2009 | MR | Zbl

[8] A. M. Raigorodskii, “Problema Erdesha–Khadvigera i khromaticheskie chisla konechnykh geometricheskikh grafov”, Matem. sb., 196:1 (2005), 123–156 | DOI | MR | Zbl

[9] E. I. Ponomarenko, A. M. Raigorodskii, “Uluchshenie teoremy Frankla–Uilsona o chisle reber gipergrafa s zapretami na peresecheniya”, Dokl. RAN, 454:3 (2014), 268–269 | DOI | MR | Zbl

[10] E. I. Ponomarenko, A. M. Raigorodskii, “Novye otsenki v zadache o chisle reber gipergrafa s zapretami na peresecheniya”, Probl. peredachi inform., 49:4 (2013), 98–104 | MR

[11] L. A. Székely, “Erdős on unit distances and the Szemerédi–Trotter theorems”, Paul Erdős and his Mathematics, II, Bolyai Soc. Math. Stud., 11, János Bolyai Math. Soc., Budapest, 2002, 649–666 | MR | Zbl

[12] L. I. Bogolyubskii, A. S. Gusev, M. M. Pyaderkin, A. M. Raigorodskii, “Chisla nezavisimosti i khromaticheskie chisla sluchainykh podgrafov v nekotorykh posledovatelnostyakh grafov”, Dokl. RAN, 457:4 (2014), 383–387 | DOI | Zbl

[13] L. I. Bogolyubskii, A. S. Gusev, M. M. Pyaderkin, A. M. Raigorodskii, “Chisla nezavisimosti i khromaticheskie chisla sluchainykh podgrafov nekotorykh distantsionnykh grafov”, Matem. sb. (to appear)

[14] E. E. Demekhin, A. M. Raigorodskii, O. I. Rubanov, “Distantsionnye grafy, imeyuschie bolshoe khromaticheskoe chislo i ne soderzhaschie klik ili tsiklov zadannogo razmera”, Matem. sb., 204:4 (2013), 49–78 | DOI | MR | Zbl

[15] J. Balogh, A. Kostochka, A. Raigorodskii, “Coloring some finite sets in ${\mathbb R}^n$”, Discuss. Math. Graph Theory, 33:1 (2013), 25–31 | DOI | MR | Zbl

[16] A. M. Raigorodskii, “On the chromatic numbers of spheres in ${\mathbb R}^n$”, Combinatorica, 32:1 (2012), 111–123 | DOI | MR | Zbl

[17] V. Boltyanski, H. Martini, P. S. Soltan, Excursions into Combinatorial Geometry, Universitext, Springer-Verlag, Berlin, 1997 | MR | Zbl

[18] A. M. Raigorodskii, “Three lectures on the Borsuk partition problem”, Surveys in Contemporary Mathematics, London Math. Soc. Lecture Note Ser., 347, Cambridge Univ. Press, Cambridge, 2007, 202–247 | MR | Zbl

[19] A. M. Raigorodskii, “Vokrug gipotezy Borsuka”, Geometriya i mekhanika, SMFN, 23, RUDN, M., 2007, 147–164 | MR | Zbl

[20] Z. Baranyai, “On the factorization of the complete uniform hypergraph”, Infinite and Finite Sets, Vol. I, North-Holland, Amsterdam, 1975, 91–108 | MR | Zbl