No label defined (Q4400627)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1182557
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 1182557

      Statements

      0 references
      28 October 1998
      0 references
      Ramanujan graph
      0 references
      isoperimetric constant
      0 references
      adjacency matrix
      0 references
      A finite, connected, \(k\)-valent graph is called a Ramanujan graph if every eigenvalue \(\mu\) of its adjacency matrix, with the exception of \(\mu=\pm k\), satisfies \(| \mu| \leq 2\sqrt{k-1}\). A substantial part of this expository article describes various constructions of infinite families of Ramanujan graphs. For a graph \(X\) with vertex set \(X^0\) and \(A\subset X^0\), define \(\partial A\) to be the set of edges incident with one vertex in \(A\) and one vertex in \(X^0\backslash A\). One defines the isoperimetric constant of \(X\) by \(h(X)=\{| \partial A| /| A| :A\subset X^0; 0<| A| \leq | X^0| /2\}\). What the author calls the ``fundamental problem'' is to give, for a fixed positive integer \(k\), an explicit construction of an infinite family \((X_m)_{m=1}^\infty\) of finite, connected, \(k\)-valent graphs whose isoperimetric values \(h(X_m)\) are uniformly bounded away from zero. The Ramanujan graphs would provide a solution to this fundamental problem, with perimetric numbers satisfying \(h\geq(k-2\sqrt{k-1})/2\). Upper bounds in terms of \(k\) are presented for the diameter and the independence number of a \(k\)-valent Ramanujan graph, and a lower bound is presented for the chromatic number. The article concludes with a section on further applications of Ramanujan graphs and a bibliography containing 76 items. For the entire collection see [Zbl 0910.00034].
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references