Light structures in infinite planar graphs without the strong isoperimetric property
HTML articles powered by AMS MathViewer
- by Bojan Mohar
- Trans. Amer. Math. Soc. 354 (2002), 3059-3074
- DOI: https://doi.org/10.1090/S0002-9947-02-03004-0
- Published electronically: April 2, 2002
- PDF | Request permission
Abstract:
It is shown that the discharging method can be successfully applied on infinite planar graphs of subexponential growth and even on those graphs that do not satisfy the strong edge isoperimetric inequality. The general outline of the method is presented and the following applications are given: Planar graphs with only finitely many vertices of degree $\le 5$ and with subexponential growth contain arbitrarily large finite submaps of the tessellation of the plane or of some tessellation of the cylinder by equilateral triangles. Every planar graph with isoperimetric number zero and with essential minimum degree $\ge 3$ has infinitely many edges whose degree sum is at most 15. In particular, this holds for all graphs with minimum degree $\ge 3$ and with subexponential growth. The cases without infinitely many edges whose degree sum is $\le 14$ (or, similarly, $\le 13$ or $\le 12$) are also considered. Several further results are obtained.References
- Amos Altshuler, Hamiltonian circuits in some maps on the torus, Discrete Math. 1 (1972), no. 4, 299–314. MR 297597, DOI 10.1016/0012-365X(72)90037-4
- K. Appel and W. Haken, Every planar map is four colorable. I. Discharging, Illinois J. Math. 21 (1977), no. 3, 429–490. MR 543792
- O. Baues and N. Peyerimhoff, Curvature and geometry of tessellating plane graphs, Discrete Comput. Geom. 25 (2001), no. 1, 141–159. MR 1797301, DOI 10.1007/s004540010076
- O. V. Borodin, A generalization of Kotzig’s theorem and prescribed edge coloring of planar graphs, Mat. Zametki 48 (1990), no. 6, 22–28, 160 (Russian); English transl., Math. Notes 48 (1990), no. 5-6, 1186–1190 (1991). MR 1102617, DOI 10.1007/BF01240258
- A. Calogero, Strong isoperimetric inequality for the edge graph of a tiling of the plane, Arch. Math. (Basel) 61 (1993), no. 6, 584–595. MR 1254071, DOI 10.1007/BF01196597
- Jozef Dodziuk, Difference equations, isoperimetric inequality and transience of certain random walks, Trans. Amer. Math. Soc. 284 (1984), no. 2, 787–794. MR 743744, DOI 10.1090/S0002-9947-1984-0743744-X
- Igor Fabrici and Stanislav Jendroľ, Subgraphs with restricted degrees of their vertices in planar $3$-connected graphs, Graphs Combin. 13 (1997), no. 3, 245–250. MR 1469824, DOI 10.1007/BF03353001
- Peter Gerl, Random walks on graphs with a strong isoperimetric property, J. Theoret. Probab. 1 (1988), no. 2, 171–187. MR 938257, DOI 10.1007/BF01046933
- Michael Gromov, Hyperbolic manifolds (according to Thurston and Jørgensen), Bourbaki Seminar, Vol. 1979/80, Lecture Notes in Math., vol. 842, Springer, Berlin-New York, 1981, pp. 40–53. MR 636516
- M. Gromov, Hyperbolic groups, Essays in group theory, Math. Sci. Res. Inst. Publ., vol. 8, Springer, New York, 1987, pp. 75–263. MR 919829, DOI 10.1007/978-1-4613-9586-7_{3}
- Branko Grünbaum and G. C. Shephard, Analogues for tilings of Kotzig’s theorem on minimal weights of edges, Theory and practice of combinatorics, North-Holland Math. Stud., vol. 60, North-Holland, Amsterdam, 1982, pp. 129–140. MR 806977
- Neil Robertson, Daniel Sanders, Paul Seymour, and Robin Thomas, The four-colour theorem, J. Combin. Theory Ser. B 70 (1997), no. 1, 2–44. MR 1441258, DOI 10.1006/jctb.1997.1750
- Zheng-Xu He and O. Schramm, Hyperbolic and parabolic packings, Discrete Comput. Geom. 14 (1995), no. 2, 123–149. MR 1331923, DOI 10.1007/BF02570699
- O. Häggström, J. Jonasson, R. Lyons, Explicit isoperimetric constants, phase transitions in the random-cluster, and Bernoullicity, preprint, 2001.
- Anton Kotzig, On the theory of Euler polyhedra, Mat.-Fyz. Časopis. Sloven. Akad. Vied. 13 (1963), 20–31 (Russian, with English summary). MR 162176
- R. Lyons, Y. Peres, Probability on trees and networks, book manuscript, 2000.
- Bojan Mohar, Isoperimetric inequalities, growth, and the spectrum of graphs, Linear Algebra Appl. 103 (1988), 119–131. MR 943998, DOI 10.1016/0024-3795(88)90224-8
- John R. Stembridge, On Schur’s $Q$-functions and the primitive idempotents of a commutative Hecke algebra, J. Algebraic Combin. 1 (1992), no. 1, 71–95. MR 1162642, DOI 10.1023/A:1022485331028
- M. R. T. Dale and J. W. Moon, The permuted analogues of three Catalan sets, J. Statist. Plann. Inference 34 (1993), no. 1, 75–87. MR 1209991, DOI 10.1016/0378-3758(93)90035-5
- P. M. Soardi, Recurrence and transience of the edge graph of a tiling of the Euclidean plane, Math. Ann. 287 (1990), no. 4, 613–626. MR 1066818, DOI 10.1007/BF01446917
- Thomas Stehling, Über des Kotziggewicht normaler Pflasterungen, Results Math. 18 (1990), no. 3-4, 347–354 (German, with English summary). MR 1078431, DOI 10.1007/BF03323179
- Wolfgang Woess, A note on tilings and strong isoperimetric inequality, Math. Proc. Cambridge Philos. Soc. 124 (1998), no. 3, 385–393. MR 1636552, DOI 10.1017/S0305004197002429
- Andrzej Żuk, On the norms of the random walks on planar graphs, Ann. Inst. Fourier (Grenoble) 47 (1997), no. 5, 1463–1490 (English, with English and French summaries). MR 1600371
Bibliographic Information
- Bojan Mohar
- Affiliation: Department of Mathematics, University of Ljubljana, 1111 Ljubljana, Slovenia
- MR Author ID: 126065
- ORCID: 0000-0002-7408-6148
- Email: bojan.mohar@uni-lj.si
- Received by editor(s): March 19, 2001
- Published electronically: April 2, 2002
- Additional Notes: Supported in part by the Ministry of Science and Technology of Slovenia, Research Project J1–0502–0101–00.
- © Copyright 2002 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 354 (2002), 3059-3074
- MSC (2000): Primary 05B45, 52B60, 52C20, 60J10
- DOI: https://doi.org/10.1090/S0002-9947-02-03004-0
- MathSciNet review: 1897390