Top

Published in:

2016 | OriginalPaper | Chapter

Recent Developments on the Edge Between Number Theory and Graph Theory

Authors : Jürgen Sander, Torsten Sander

Published in: From Arithmetic to Zeta-Functions

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

This article reflects some of the authors’ perspectives on and personal experiences with the interplay between number theory and graph theory. To start with, we touch on a few historical milestones of the rewarding relations between the two disciplines. Later on, we shall address more recent developments without any ambition to strive for completeness.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Idempotents and Congruence

next chapter The Leading Coefficients of Stern Polynomials

Who appreciated the use of footnotes. As a tribute to him, we pursue his habit with great pleasure. The first author met Wolfgang Schwarz for the first time at the DMV-Tagung (Meeting of the Deutsche Mathematiker-Vereinigung) in 1986 in Marburg, and from then on again and again at various conferences. Schwarz’s quiet and reflected, but also determined appearance left a lasting impression. One of the valuable memories still is the daily joint ‘hiking exercise’ after lunch up to the 8th floor of the maths building, when the first author had accepted Schwarz’s invitation as guest professor at Frankfurt University.

For a very readable discussion on the formation of number theory as a discipline we recommend the essay A book in search of a discipline by C. Goldstein and N. Schappacher in: The Shaping of Arithmetic after C.F. Gauss’s Disquisitiones Arithmeticae, C. Goldstein, N. Schappacher, J. Schwermer (eds.), Springer, 2007.

L. Euler, Solutio problematis ad geometriam situs pertinentis, Commentarii Academiae Scientiarum Imperialis Petropolitanae 8 (1736), 128–140 = Opera Omnia (1) 7 (1911–56), 1–10.

W. Hopkins, The Truth about Königsberg, The College Mathematics Journal 35 (2004), 198–207.

J.J. Sylvester, Chemistry and Algebra, Nature 17 (1878), 284–284.

J. Petersen, Die Theorie der regulären Graphs, Acta Mathematica 15 (1891), 193–220.

D. Kőnig, Theorie der endlichen und unendlichen Graphen. Kombinatorische Topologie der Streckenkomplexe, Math. u. ihre Anwendung in Monogr. u. Lehrbüchern 16, Akad. Verlagsgesellschaft, Leipzig, 1936.

F.P. Ramsey, On a problem of formal logic, Proceedings of the London Mathematical Society 30 (1) (1930), 264–286.

B.L. van der Waerden, Beweis einer Baudetschen Vermutung, Nieuw Arch. Wisk. 15 (1927), 212–216.

P. Erdős and P. Turàn, On some sequences of integers, Journal of the London Mathematical Society 11 (4) (1936), 261–264.

E. Szemerédi, On sets of integers containing no k elements in arithmetic progression, Acta Artithmetica 27 (1975), 199–245.

K. Roth, On certain sets of integers, Journal of the London Mathematical Society 28 (1) (1953), 104–109.

H. Furstenberg, Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions, Journal d’Analyse Math. 31 (1977), 204–256.

T. Gowers A new proof of Szemerédi’s theorem, Geom. Funct. Anal. 11 (3) (2001), 465–588.

T. Tao, The dichotomy between structure and randomness, arithmetic progressions, and the primes, pp. 581–608 in: M. Sanz-Solé, J. Soria, J.L. Varona et al., International Congress of Mathematicians Zürich, European Mathematical Society, Zürich, 2007.

B. Green and T. Tao, The primes contain arbitrarily long arithmetic progressions, Annals of Mathematics 167 (2) (2008), 481–547.

E.g. P. Erdős, Some applications of graph theory to number theory, pp. 77–82 in: The Many Facets of Graph Theory, Proc. Conf. Western Mich. Univ., Kalamazoo, Mich. 1968, Springer LNM, Berlin, 1969.

Cf. chapter Graphs on the integers, in: R.L. Graham, M. Grötschel, L. Lovász, Handbook of Combinatorics, Vol. 1, North-Holland, New York, 1995.

C. Pomerance, On the longest simple path in the divisor graph, Congressus Numerantium 40 (1983), 291–304.

G. Chartrand, R. Muntean, V. Saenpholphat, and P. Zhang, Which graphs are divisor graphs?, Congressus Numerantium 151 (2001), 189–200.

Neighbour is synonymously used for adjacent vertex.

M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas, The strong perfect graph theorem, Annals of Mathematics 164 (1) (2006), 51–229.

S. Al-Addasi, O.A. AbuGhneim, and H. Al-Ezeh, Further new properties of divisor graphs, J. Comb. Math. Comb. Comput. 81 (2012), 261–272.

As also conjectured by Berge and shown by L. Lovász, (1972), A characterization of perfect graphs, Journal of Combinatorial Theory, Series B 13 (2) (1972), 95–98.

P. Erdős and G.N. Sárközy, On cycles in the coprime graph of integers, Electron. J. Comb. 4 (2) (1997), Research paper R8.

G.N. Sárközy, Complete tripartite subgraphs in the coprime graph of integers, Discrete Mathematics 202 (1999), 227–238.

This procedure is named coprime labelling or, rather unsuitably, prime labelling.

P. Haxell, O. Pikhurko, and A. Taraz, Primality of trees, J. Comb. 2 (4) (2011), 481–500.

See the survey article by S.N. Rao, A Creative Review on Coprime (Prime) Graphs, Lecture Notes, DST Work Shop (23–28 May 2011), WGTA, BHU, Varanasi, 2011.

F. Harary and A.J. Schwenk, Which graphs have integral spectra?, pp. 45–51 in: Graphs and Combinatorics, Springer, Berlin, 1974.

K. Balinska, D. Cvetkovic, Z. Radosavljevic, S. Simic, and D. Stevanovic, A survey on integral graphs. Publ. Elektroteh. Fak., Univ. Beogr., Ser. Mat. 13 (2002), 42–65.

J.W. Sander and T. Sander, On the kernel of the coprime graph of integers, Integers 9 (2009), 569–579.

G. Hahn and G. Sabidussi, Graph symmetry: algebraic methods and applications, Proceedings of the NATO Advanced Study Institute and séminaire de mathématiques supérieures, Montréal, Canada, July 1–12, 1996; Springer, New York, 1997.

C.H. Li, On isomorphisms of finite Cayley graphs—a survey, Discrete Mathematics 256 (1–2) (2002), 301–334.

Ph.J. Davis, Circulant matrices, Pure and applied Mathematics. Wiley-Interscience Publication, New York, 1979; 2nd ed., AMS Chelsea Publishing, 1994.

J. Turner, Point-Symmetric Graphs with a Prime Number of Points, Journal Comb. Theory 3 (1967), 136–145.

This is a result of Muzychuk, to be found in Hahn/Sabidussi.³³

M. Muzychuk, M. Klin, and R. Pöschel, The isomorphism problem for circulant graphs via Schur ring theory, (DIMACS workshop 1999), Ser. Discrete Math. Theor. Comput. Sci. 56 (2001), 241–264; and E. Dobson and J. Morris, Toida’s conjecture is true, Electron. J. Comb. 9 (1) (2002), Research paper R35.

C.K. Wong and D. Coppersmith, A combinatorial problem related to multimodule memory organizations, J. Assoc. Comput. Mach. 21 (1974), 392–402.

N. Saxena, S. Severini, and I.E. Shparlinski, Parameters of integral circulant graphs and periodic quantum dynamics, Int. J. Quantum Inf. 5 (3) (2007), 417–430.

W. So, Integral circulant graphs, Discrete Mathematics 306 (2005), 153–158.

See, e.g., P.J. McCarthy, Introduction to arithmetical functions, Universitext, Springer, New York, 1986.

W. Klotz and T. Sander, Integral Cayley graphs defined by greatest common divisors, Electron. J. Comb. 18 (1) (2011), Research paper P94.

W. Klotz and T. Sander, Integral Cayley graphs over Abelian groups, Electron. J. Comb. 17 (1) (2010), Research paper R81.

W. Klotz and T. Sander, Wie kommt Sudoku zu ganzzahligen Eigenwerten? (How does Sudoku acquire integral eigenvalues?), Math. Semesterber. 57 (2) (2010), 169–183.

Vertex transitive graphs are exactly those graphs whose automorphism group acts transitively on its vertex set. In other words, for any two vertices there needs to exist an automorphism mapping the first vertex to the second.

L. Lovász, Spectra of graphs with transitive groups, Period. Math. Hung. 6 (1975), 191–195.

I.e. the set of all vertices adjacent to v.

An element a of a lattice with associated partial order ≤ and least element 0 is an atom if 0 < a and no element x satisfies 0 < x < a. A lattice is atomic if, for every element b ≠ 0, we have a ≤ b for some atom a.

R.C. Alperin and B.L. Peterson, Integral sets and Cayley graphs of finite groups, Electron. J. Comb. 19 (1) (2012), Research paper P44.

R.C. Alperin and B.L. Peterson, Integral sets and the center of a finite group, Can. Math. Bull. 57 (1) (2014), 9–11.

A. Abdollahi and M. Jazaeri, Groups all of whose undirected Cayley graphs are integral, European Journal of Combinatorics 38 (2014), 102–109; and A. Ahmady, J.P. Bell, and B. Mohar, Integral Cayley graphs and groups, SIAM J. Discrete Math. 28 (2) (2014), 685–701.

W. Klotz and T. Sander, Distance powers and distance matrices of integral Cayley graphs over abelian groups, Electron. J. Comb. 19 (4) (2012), Research paper P25.

The d-th distance power G ^(d) of a graph G has the same vertex sets as G. Two vertices x ≠ y are joined by an edge if and only if their distance in G is at most d.

J.W. Sander and T. Sander, Adding generators in cyclic groups, J. Number Theory 133 (2) (2013), 705–718.

Q.-H. Yang and M. Tang, On the addition of squares of units and nonunits modulo n, J. Number Theory 155 (2015), 1–12.

M. Kreh, Adding generators in abelian groups, to appear in J. Algebra and Number Theory Acad.

This follows from the fact that trees, by definition, are the cyclefree graphs and must have leaves.

Here we disregard the technical obstacles of orientation and backtracks, but one can find all details of the precise definition of primes in graphs—and most of the other facts of this section—in A. Terras, Zeta Functions of Graphs—A Stroll through the Garden, Cambridge studies in advanced mathematics, Cambridge University Press, Cambridge, 2011, or the first author’s Arithmetical Topics in Algebraic Graph Theory, in: K. Bringmann, Y. Bugeaud, T. Hilberdink, J.W. Sander, Four Faces of Number Theory, European Mathematical Society, Lectures in Mathematics, Zürich, 2015.

Observe the = sign as opposed to ≤ in the prime counting function for integers.

Y. Ihara, On discrete subgroups of the two by two projective linear group over p-adic fields, J. Math. Soc. Japan. 18 (1966), 219–223.

= J.-P. Serre, Trees, Springer, New York, 1980.

Namely, as a zeta-function related to closed geodesics in graphs—compare this with Selberg zeta-functions.

T. Sunada, Riemannian coverings and isospectral manifolds, Ann. Math. 121 (1985), 169–186.

In fact, there exist several functional equations for ζ _G(u)

W _G is a 0-1-matrix indicating if a pair (e _i, e _j) of edges in G is a path (of length 2) in the graph or not. In other words, the edge adjacency matrix of G is the adjacency matrix of the line graph of G, which is obtained from G by exchanging the roles of vertices and edges. For a precise definition look into the books cited in footnote 60.

But with less difficulties and, therefore, much less effort.

For all the details, see the two books mentioned in footnote 60.

A graph is called q-regular if every vertex has exactly q neighbours.

I.e. given the spectrum of any regular graph, the spectrum of its line graph can be explicitly specified. This follows from a result of Sachs, see, e.g., Theorem 3.8 in: N. Biggs, Algebraic graph theory, 2nd ed., Cambridge University Press, Cambridge, 1993.

This is an exercise in algebraic graph theory.

N. Alon, Eigenvalues and expanders, Combinatorica 6 (1986), 83–96, and R.B. Boppana, Eigenvalues and graph bisection: an average case analysis, pp. 280–285 in: Proc. 28th Annual Symp. Found. Comp. Sci., IEEE 1987.

For a survey, see M.R. Murty, Ramanujan graphs, J. Ramanujan Math. Soc. 18 (2003), 33–52.

Expander graphs have the following two competing properties: on the one hand, they are fairly sparse (in terms of number of edges as compared to the number of vertices), but on the other hand, they are highly connected. For a formal definition as well as results and applications, see S. Hoory, N. Linial, and A. Widgerson, Expander graphs and their applications, Bulletin (New series) of the American Mathematical Society 43 (4) (2006), 439–561.

F. Bien, Construction of Telephone Networks by Group Representations, Notices of the Amer. Math. Society 36 (1) (1989), 5–22.

See Hoory et al., footnote 75.

A. Lubotzky, R. Phillips, and P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988), 261–277.

M. Morgenstern, Existence and explicit constructions of q + 1 regular Ramanujan graphs for every prime power q, J. Combinatorial Theory, Series B 62 (1994), 44–62.

W. Schwarz and J. Spilker, Arithmetical functions: An Introduction to Elementary and Analytic Properties of Arithmetic Functions and to Some of their Almost-Periodic Properties, Cambridge University Press, Cambridge, 1994.

I. Gutman, The energy of a graph, in: Ber. Math.-Stat. Sekt. Forschungszent. Graz 103, Graz, 1978.

More precisely, the total π-electron energy can be calculated as the energy of an appropriate molecular graph. For connections between Hückel molecular orbital theory and graph spectral analysis, see R.B. Mallion, Some chemical applications of the eigenvalues and eigenvectors of certain finite, planar graphs, pp. 87–114 in: R.J. Wilson ed., Appl. of combinatorics, Shiva Math. Ser. 6, Shiva Publ., Nantwich, 1982.

For mathematical surveys, see R.A. Brualdi, Energy of a graph, AIM Workshop Notes, 2006 and I. Gutman, The energy of a graph: Old and new results, pp. 196–211 in: A. Betten, A. Kohnert, R. Laue, A. Wassermann eds., Algebraic Combinatorics and Applications, Springer-Verlag, Berlin, 2001.

As shown in Theorem 4.4.

J.W. Sander and T. Sander, The energy of integral circulant graphs with prime power order, App. Anal. Discrete Math. 5 (2011), 22–36.

J.W. Sander and T. Sander, The exact maximal energy of integral circulant graphs with prime power order, Contributions to Discrete Math. 8 (2) (2011), 19–40.

T.A. Le and J.W. Sander, Convolutions of Ramanujan sums and integral circulant graphs, Int. J. of Number Theory 8 (7) (2012), 1777–1788.

Theorem 4.1 in footnote 87.

T.A. Le and J.W. Sander, Extremal energies of integral circulant graphs via multiplicativity, Linear Alg. Appl. 437 (2012), 1408–1421.

Cf. preceding section.

T.A. Le and J.W. Sander, Integral circulant Ramanujan graphs of prime power order, Electronic J. Combinatorics 20 (2013), Research paper P35.

J.W. Sander, Integral circulant Ramanujan graphs via multiplicativity and ultrafriable integers, Linear Algebra Appl. 477 (2015), 21–41.

Title: Recent Developments on the Edge Between Number Theory and Graph Theory
Authors: Jürgen Sander
Torsten Sander
Publisher: Springer International Publishing
Book: From Arithmetic to Zeta-Functions
Print ISBN: 978-3-319-28202-2

Electronic ISBN: 978-3-319-28203-9

Copyright Year: 2016
DOI: https://doi.org/10.1007/978-3-319-28203-9_24

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner