Geodesic
Turán type results for distance graphs in infinitesimal plane layer
Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part IX, Tome 464 (2017), pp. 132-168 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

In this paper we obtain the lower bound of number of edges in a unit distance graph $\Gamma$ in an infinitesimal plane layer $\mathbb R^2\times[0,\varepsilon]^d$ which compares number of edges $e(\Gamma)$, number of vertices $\nu(\Gamma)$ and independence number $\alpha(\Gamma)$. Our bound $e(\Gamma)\ge\frac{19\nu\Gamma)-50\alpha(\Gamma)}3$ is generalizing of previous bound for distance graphs in plane and a strong upgrade of Turán's bound when $\frac15\le\frac{\alpha(\Gamma)}{\nu(\Gamma)}\le\frac27$. 
@article{ZNSL_2017_464_a7,
     author = {L. E. Shabanov},
     title = {Tur\'an type results for distance graphs in infinitesimal plane layer},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {132--168},
     year = {2017},
     volume = {464},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2017_464_a7/}
}
TY  - JOUR
AU  - L. E. Shabanov
TI  - Turán type results for distance graphs in infinitesimal plane layer
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2017
SP  - 132
EP  - 168
VL  - 464
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2017_464_a7/
LA  - ru
ID  - ZNSL_2017_464_a7
ER  - 
%0 Journal Article
%A L. E. Shabanov
%T Turán type results for distance graphs in infinitesimal plane layer
%J Zapiski Nauchnykh Seminarov POMI
%D 2017
%P 132-168
%V 464
%U http://geodesic.mathdoc.fr/item/ZNSL_2017_464_a7/
%G ru
%F ZNSL_2017_464_a7
L. E. Shabanov. Turán type results for distance graphs in infinitesimal plane layer. Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part IX, Tome 464 (2017), pp. 132-168. http://geodesic.mathdoc.fr/item/ZNSL_2017_464_a7/

[1] P. Brass, W. Moser, J. Pach, Research problems in discrete geometry, Springer, 2005 | MR | Zbl

[2] A. Dainyak, A. Sapozhenko, “Independent sets in graphs”, Discret. Math. Appl., 26:6 (2016), 323–346 | MR | Zbl

[3] P. Erdős, “On sets of distances of $n$ points”, Amer. Math. Monthly, 53 (1946), 248–250 | DOI | MR | Zbl

[4] A. M. Raigorodskii, “Cliques and cycles in distance graphs and graphs of diameters”, Discrete Geometry and Algebraic Combinatorics, Contemporary Mathematics, 625, AMS, 2014, 93–109 | DOI | MR | Zbl

[5] A. M. Raigorodskii, “Coloring Distance Graphs and Graphs of Diameters”, Thirty Essays on Geometric Graph Theory, ed. J. Pach, Springer, 2013, 429–460 | DOI | MR | Zbl

[6] A. M. Raigorodskii, “Combinatorial geometry and coding theory”, Fundamenta Informatica, 145 (2016), 359–369 | DOI | MR | Zbl

[7] L. E. Shabanov, A. M. Raigorodskii, “Turán type results for distance graphs”, Discrete and Computational Geometry, 56:3 (2016), 814–832 | DOI | MR

[8] A. Soifer, Mathemetical coloring book, Springer, 2009 | MR

[9] M. Tikhomirov, “On computational complexity of length embeddability of graphs”, Discret. Math., 339:11 (2016), 2605–2612 | DOI | MR | Zbl

[10] P. Turán, “On an extremal problem in graph theory”, Matematikai Fizikai Lapok, 48 (1941), 436–452 (in Hungarian) | MR | Zbl

[11] A. E. Guterman, V. K. Lyubimov, A. M. Raigorodskii, A. S. Usachev, “O chislakh nezavisimosti distantsionnykh grafov s vershinami v $\{-1,0,1\}^n$”, Mat. zametki, 86:5 (2009), 794–796 | DOI | MR | Zbl

[12] A. Ya. Kanel-Belov, V. A. Voronov, D. D. Cherkashin, “O khromaticheskom chisle ploskosti”, Algebra i analiz, 29:5 (2017), 68–89 | MR

[13] V. K. Lyubimov, A. M. Raigorodskii, “O nizhnikh otsenkakh chisel nezavisimosti distantsionnykh grafov s vershinami v $\{-1,0,1\}^n$”, Doklady RAN, 427:4 (2009), 458–460 | MR | Zbl

[14] E. I. Ponomarenko, A. M. Raigorodskii, “Novye verkhnie otsenki chisel nezavisimosti grafov s vershinami v $\{-1,0,1\}^n$ i ikh prilozheniya v zadachakh o khromaticheskikh chislakh distantsionnykh grafov”, Matem. zametki, 96:1 (2014), 138–147 | DOI | MR | Zbl

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

[16] A. A. Sagdeev, A. M. Raigorodskii, “O khromaticheskom chisle prostranstva s zapreschennym pravilnym simpleksom”, Dokl. RAN, 472:2 (2017), 127–129 | Zbl

[17] M. Tikhomirov, “O zadache proverki distantsionnoi i multidistantsionnoi vlozhimosti grafa”, Dokl. Akad. Nauk, 468:3 (2016), 261–263 | DOI | Zbl

[18] D. D. Cherkashin, A. M. Raigorodskii, “O khromaticheskikh chislakh prostranstv maloi razmernosti”, Dokl. RAN, 472:1 (2017), 11–12 | DOI | MR | Zbl