14 ms·

Matrices and Graph

205 points by jgrodziski 3y ago

yvdriess 3y ago
GraphBLAS completely revolves around this duality. Sparse linear algebra is really powerful. https://graphblas.org/ https://graphblas.org/
amai 3y ago
If expressed as adjacency matrix every graph is a square matrix. And every square matrix has a characteristic polynomial. So that means: Every graph is also a polynomial! see https://mathworld.wolfram.com/CharacteristicPolynomial.html https://mathworld.wolfram.com/CharacteristicPolynomial.html
luttik 3y ago
This is also the basis of process mining. And why process graphs are so easy to analyse.
bionhoward 3y ago
Beautiful illustrations, thank you for sharing.
duckqlz 3y ago
Does anyone know how the graph illustrations were created? I have driven myself mad with tikz and dot .
- TivadarDanka 3y ago
  Author here. I rendered (most of the) equations with QuickLaTeX (https://quicklatex.com/ https://quicklatex.com/), and put the illustrations together in Inkscape by hand (https://inkscape.org/ https://inkscape.org/).
- elliotwagner 3y ago
  I would like to know this too
- EsportToys 3y ago
  looks like Manim.
- sdkgames 3y ago
  graphviz? [0] [0] https://graphviz.org/gallery/ https://graphviz.org/gallery/
dustingetz 3y ago
what book to read to develop these concepts and intuitions with engineering level of math (not proofs)?
- dpflan 3y ago
  I don't know how proof heavy this course is and it is not specialized on graphs: "Computational Science and Engineering I" -- Gilbert Strang (MIT) https://ocw.mit.edu/courses/18-085-computational-science-and-engineering-i-fall-2008/pages/syllabus/ https://ocw.mit.edu/courses/18-085-computational-science-and...
  - algas 3y ago
    The textbook for this course is probably one of the finest Strang ever wrote. It's also worth looking at the original edition of the textbook, which was called "Introduction to Applied Mathematics" and has a much more thorough treatment of the parallels between matrices, graphs, and differential operators, and their use in optimization problems. CSE is much more practical for solving actual scientific computing problems, though, even if I find the layout somewhat less beautiful.
    - dustingetz 3y ago
      oh my, thanks! Ed 1 is the exact book i wanted
      - dpflan 3y ago
        Were you able to find a copy? I found this on archive.org -- https://archive.org/details/introductiontoap0000stra/page/n9/mode/2up https://archive.org/details/introductiontoap0000stra/page/n9...
- EsportToys 3y ago
  I highly recommend anything in Finite Element Methods, it gives you an immediate grounding to a concrete application. I personally really benefitted a lot in the following YouTube lecture series: https://www.math.colostate.edu/~bangerth/videos.html https://www.math.colostate.edu/~bangerth/videos.html
zmgsabst 3y ago
This is especially fascinating when you consider graphs/diagrams are a way to encode math.
- owlbite 3y ago
  The fact that you can represent a graph (the mathematical abstract object) as a diagram is sort of by-the-by here. The most important thing is that graph algorithms and concepts have a strong relation to numerical aspects of the linear algebra and can be used to accelerate computation. (You could of course argue that the act that graphs can be represented as a diagram helps humans come up with such algorithms, but that's basically equivalent to saying that you can represent a matrix as a block of numbers and that helps humans look at it).
  - zmgsabst 3y ago
    I was pointing out the other direction: Diagrams are how you encode categorical models of semantics, which naturally can be represented as graphs. Those graphs can in turn be encoded as matrices. So you have a way to encode semantic foundations as matrices — which you can then use graph algorithms to analyze. Being able to move your semantic models (eg, diagrams) into a computational framework (eg, linear algebra) is neat.
- meindnoch 3y ago
  Umm... What? Please show us the graph that "encodes" the fundamental theorem of algebra.
  - zmgsabst 3y ago
    https://en.wikipedia.org/wiki/Category_theory https://en.wikipedia.org/wiki/Category_theory The fundamental theorem of algebra is a fact about the diagram which relates polynomials via division by monomials. Every polynomial of degree n is n divisions of a monomial away from the empty product. - - - - This is probably easier to see the other direction: Polynomials of degree n are isomorphic to n-products of monomials, and you can build a graph of the assembly where each arrow represents a multiplication by a particular monomial. (Then reverse the arrows, to get my original diagram.)
EsportToys 3y ago
Fun fact: this is only valid for domains that have a notion of "selfness", i.e. that there is such thing as an "identity matrix" for the quantities. Consider the following square matrix: TSLA APPL GOOG MSFT Alice | 100 5 0 1 Bob | 0 30 100 5 Carol | 2 2 2 2 Dan | 0 0 0 1000 An input vector of stock prices gives an output vector of net worths. However, that is about the only way you can use this matrix. You cannot transform the table arbitrarily and still have it make sense, such as applying a rotation matrix -- it is nonsensical to speak of a rotation from Tesla-coordinates to Google-coordinates. The input and output vectors lacks tensor transformation symmmetries, so they are not tensors. This is also why Principal Component Analysis and other data science notions in the same vein are pseudoscience (unless you evaluate the logarithm of the quantities, but nobody seems to recognize the significance of unit dimensions and multiplicative vs additive quantities)
- FooBarBizBazz 3y ago
  I dunno, there are some semi-useful things you can do. For example, the transform from (Alive, Bob, Carol, Dan) to (Male, Female) is linear -- it's another matrix that you can compose with the individual-ownership one you have here. Or, call your individual-ownership matrix A, and say that P is the covariance of daily changes to prices of the four stocks listed. Then A P A' is the covariance of daily changes to the peoples' wealths. The framing as linear algebra hasn't been useless. I kinda get what you're saying though. Like, why would powers of this matrix be useful? It only makes sense if there's some implicit transform between prices and people, or vice versa, that happens to be an identity matrix. You can make up a story. Say the people can borrow on margin some fraction of their wealth. Then say that they use that borrowing to buy stock, and that that borrowing affects prices. Composing all these transforms, you could get from price to price, and then ask what the dynamics are as the function is iterated. But, ok, "I'm just going to do an SVD of the matrix and put it in a slide" isn't going to tell anybody much. Maybe there's a use for a rank-one approximation to this system? Like, "this is pretty close to a situation where there's a single ETF with those stocks in these proportions, and where the people own the following numbers of shares in the ETF"? Maybe if you have millions of people and millions of stocks and wanted to simulate this "stock market" at 100Hz on a TI-83? I dunno. You can make up stories.
mark_l_watson 3y ago
Beautifully done. I subscribe to the author’s Substack, lots of other really nice stuff there. A little off topic, but this is just one more example of beautifully done content on Substack. I have seriously considered setting my freedom.to settings to only allow accessing HN, FB, Twitter, Mastodon, etc., 1 or 2 mornings a week, and that time would mostly be for ensuring that I was always subscribed to a few good Substack channels. With the explosion of ‘tech stuff I should read’, I think I need a more extreme culling of what I spend my time on.
Scene_Cast2 3y ago
Another interesting mapping is that a vector is (or can be thought of as) a discrete function (f(x) = ....) over an interval, a dot product of two vectors is a discrete integral product, and a matrix is a discrete scalar field. I wonder what the continuous form of a graph is... Some sort of a manifold perhaps?
- krackers 3y ago
  >continuous form of a graph A graphon? Edit: This was already mentioned by meindnoch.
- enriquto 3y ago
  > I wonder what the continuous form of a graph is... Some sort of a manifold perhaps? Exactly! The correspondence between manifolds and graphs is very beautiful. What many folks call today "graph signal processing" has traditionally been called "discrete differential geometry". Scalar fields are functions defined on vertices, vector fields are functions defined on edges, the incidence matrix is the gradient operator, its transpose is the divergence, the Laplacian is the divergence of the gradient, integrals and fluxes are scalar products by indicator functions, the boundary operator is minus the gradient, Green's formula is just matrix transposition, etc. You can even go further in the analogy and define p-forms as functions defined on the p-cliques of the graph, and from that rebuild a whole discrete Hodge theory. The correspondence is almost perfect, except for the fact that you cannot write easily the product rule for derivatives (because you cannot multiply pointwise scalar fields with vector fields).
  - qsdf38100 3y ago
    And electromagnetism seems to be a by product of discrete differential geometry. Such a fascinating subject. Makes continuous treatment look like a mess.
- shakow 3y ago
  A bivariate function?
- meindnoch 3y ago
kmad 3y ago
This approach reminds me of RedisGraph[1] (which is now unfortunately EoL). "RedisGraph is the first queryable Property Graph database to use sparse matrices to represent the adjacency matrix in graphs and linear algebra to query the graph." 1. https://github.com/RedisGraph/RedisGraph https://github.com/RedisGraph/RedisGraph
- westurner 3y ago
  RDF-star and SPARQL-star are basically Property Graph interfaces if you don't validate with e.g. RDFS (schema.org,), SHACL, json-ld-schema (jsonschema+shacl), and/or OWL. Justify Linked Data; https://5stardata.info/ https://5stardata.info/ W3C RDF-star and SPARQL-star > 2.2 RDF-star Graph Examples: https://w3c.github.io/rdf-star/cg-spec/editors_draft.html#rdf-star-graph-examples https://w3c.github.io/rdf-star/cg-spec/editors_draft.html#rd... def to_matrices(g: rdflib.MultiDiGraph) -> Union[Matrix, Tensor] rdflib.MultiDiGraph: https://networkx.org/documentation/stable/reference/classes/multidigraph.html https://networkx.org/documentation/stable/reference/classes/... Multigraph: https://en.wikipedia.org/wiki/Multigraph https://en.wikipedia.org/wiki/Multigraph : > In mathematics, and more specifically in graph theory, a multigraph is a graph which is permitted to have multiple edges (also called parallel edges[1]), that is, edges that have the same end nodes. Thus two vertices may be connected by more than one edge ... [which requires multidimensional matrices, netcdf (pydata/xarray,), tensors, or a better implementation of a representation; and edge reification in RDF] From "Why tensors? A beginner's perspective" https://news.ycombinator.com/item?id=30629931 https://news.ycombinator.com/item?id=30629931 : > https://en.wikipedia.org/wiki/Tensor https://en.wikipedia.org/wiki/Tensor ... Tensor product of graphs: https://en.wikipedia.org/wiki/Tensor_product_of_graphs https://en.wikipedia.org/wiki/Tensor_product_of_graphs Hilbert space: https://en.wikipedia.org/wiki/Hilbert_space https://en.wikipedia.org/wiki/Hilbert_space : > The inner product between two state vectors is a complex number known as a probability amplitude.
enchiridion 3y ago
I think I’m misunderstanding. The node relabeling seems backwards. He says start with the highest order, which makes me think the neighborhood with order 3 would get the smaller node labels, and the neighborhoods with order 0 would get the highest. It looks like the opposite was done.
owlbite 3y ago
Sparse Linear Algebra is Graphs all the way down.
jfarmer 3y ago
If folks are looking for terms to Google, try "spectral graph theory" and "algebraic graph theory" https://en.wikipedia.org/wiki/Spectral_graph_theory https://en.wikipedia.org/wiki/Spectral_graph_theory https://en.wikipedia.org/wiki/Algebraic_graph_theory https://en.wikipedia.org/wiki/Algebraic_graph_theory Pretty much every field in math has a related field where you try to turn problems from the former into linear algebra problems. The "spectral theorem" (https://en.wikipedia.org/wiki/Spectral_theorem https://en.wikipedia.org/wiki/Spectral_theorem) is an important theorem in linear algebra that gives conditions for when a matrix can be diagonalized, which is closely related to what its eigenvalues/eigenvectors look like. The simplest version of the spectral theorem says that a symmetric matrix with real-number entries has real-number eigenvalues. The eigenvalues of a matrix are called the "spectrum of the matrix", hence "spectral theorem" and "spectral graph theory". The adjacency matrix of any undirected graph is real symmetric, so its eigenvalues are all real numbers and it's natural to ask whether they say anything about the underlying graph. Lucky for us, there are lots of surprising connections! For example, say G is an finite undirected graph. The chromatic number of G, denoted χ(G), is the fewest number of colors needed to color its vertexes so that no two adjacent vertexes have the same color. If λ₁ is the largest eigenvalue of G's adjacency matrix then there's a theorem (Wilf's theorem) that says χ(G) ≤ 1 + ⌊λ₁⌋ That is, you can always color a graph with 1 + ⌊λ₁⌋ colors, where ⌊x⌋ is the floor of x. And there are some (finite, undirected) graphs that require exactly 1 + ⌊λ₁⌋ colors, so we're not doing any better unless we can say something more specific about the graph. Wilf's Theorem: https://www2.math.upenn.edu/~wilf/website/Eigenvalues%20of%20a%20graph.pdf https://www2.math.upenn.edu/~wilf/website/Eigenvalues%20of%2... https://www2.math.upenn.edu/~wilf/website/Inequality%20for%20Chromatic%20Number.pdf https://www2.math.upenn.edu/~wilf/website/Inequality%20for%2...

205 points by jgrodziski 3y ago

GraphBLAS completely revolves around this duality. Sparse linear algebra is really powerful. https://graphblas.org/ https://graphblas.org/

amai 3y ago

If expressed as adjacency matrix every graph is a square matrix. And every square matrix has a characteristic polynomial. So that means: Every graph is also a polynomial! see https://mathworld.wolfram.com/CharacteristicPolynomial.html https://mathworld.wolfram.com/CharacteristicPolynomial.html

luttik 3y ago

This is also the basis of process mining. And why process graphs are so easy to analyse.

bionhoward 3y ago

Beautiful illustrations, thank you for sharing.

duckqlz 3y ago

Does anyone know how the graph illustrations were created? I have driven myself mad with tikz and dot .

TivadarDanka 3y ago
Author here. I rendered (most of the) equations with QuickLaTeX (https://quicklatex.com/ https://quicklatex.com/), and put the illustrations together in Inkscape by hand (https://inkscape.org/ https://inkscape.org/).
elliotwagner 3y ago
I would like to know this too
EsportToys 3y ago
looks like Manim.
sdkgames 3y ago
graphviz? [0] [0] https://graphviz.org/gallery/ https://graphviz.org/gallery/

dustingetz 3y ago

what book to read to develop these concepts and intuitions with engineering level of math (not proofs)?

dpflan 3y ago
I don't know how proof heavy this course is and it is not specialized on graphs: "Computational Science and Engineering I" -- Gilbert Strang (MIT) https://ocw.mit.edu/courses/18-085-computational-science-and-engineering-i-fall-2008/pages/syllabus/ https://ocw.mit.edu/courses/18-085-computational-science-and...
- algas 3y ago
  The textbook for this course is probably one of the finest Strang ever wrote. It's also worth looking at the original edition of the textbook, which was called "Introduction to Applied Mathematics" and has a much more thorough treatment of the parallels between matrices, graphs, and differential operators, and their use in optimization problems. CSE is much more practical for solving actual scientific computing problems, though, even if I find the layout somewhat less beautiful.
  - dustingetz 3y ago
    oh my, thanks! Ed 1 is the exact book i wanted
    - dpflan 3y ago
      Were you able to find a copy? I found this on archive.org -- https://archive.org/details/introductiontoap0000stra/page/n9/mode/2up https://archive.org/details/introductiontoap0000stra/page/n9...
EsportToys 3y ago
I highly recommend anything in Finite Element Methods, it gives you an immediate grounding to a concrete application. I personally really benefitted a lot in the following YouTube lecture series: https://www.math.colostate.edu/~bangerth/videos.html https://www.math.colostate.edu/~bangerth/videos.html

zmgsabst 3y ago

This is especially fascinating when you consider graphs/diagrams are a way to encode math.

owlbite 3y ago
The fact that you can represent a graph (the mathematical abstract object) as a diagram is sort of by-the-by here. The most important thing is that graph algorithms and concepts have a strong relation to numerical aspects of the linear algebra and can be used to accelerate computation. (You could of course argue that the act that graphs can be represented as a diagram helps humans come up with such algorithms, but that's basically equivalent to saying that you can represent a matrix as a block of numbers and that helps humans look at it).
- zmgsabst 3y ago
  I was pointing out the other direction: Diagrams are how you encode categorical models of semantics, which naturally can be represented as graphs. Those graphs can in turn be encoded as matrices. So you have a way to encode semantic foundations as matrices — which you can then use graph algorithms to analyze. Being able to move your semantic models (eg, diagrams) into a computational framework (eg, linear algebra) is neat.
meindnoch 3y ago
Umm... What? Please show us the graph that "encodes" the fundamental theorem of algebra.
- zmgsabst 3y ago
  https://en.wikipedia.org/wiki/Category_theory https://en.wikipedia.org/wiki/Category_theory The fundamental theorem of algebra is a fact about the diagram which relates polynomials via division by monomials. Every polynomial of degree n is n divisions of a monomial away from the empty product. - - - - This is probably easier to see the other direction: Polynomials of degree n are isomorphic to n-products of monomials, and you can build a graph of the assembly where each arrow represents a multiplication by a particular monomial. (Then reverse the arrows, to get my original diagram.)

EsportToys 3y ago

Fun fact: this is only valid for domains that have a notion of "selfness", i.e. that there is such thing as an "identity matrix" for the quantities. Consider the following square matrix: TSLA APPL GOOG MSFT Alice | 100 5 0 1 Bob | 0 30 100 5 Carol | 2 2 2 2 Dan | 0 0 0 1000 An input vector of stock prices gives an output vector of net worths. However, that is about the only way you can use this matrix. You cannot transform the table arbitrarily and still have it make sense, such as applying a rotation matrix -- it is nonsensical to speak of a rotation from Tesla-coordinates to Google-coordinates. The input and output vectors lacks tensor transformation symmmetries, so they are not tensors. This is also why Principal Component Analysis and other data science notions in the same vein are pseudoscience (unless you evaluate the logarithm of the quantities, but nobody seems to recognize the significance of unit dimensions and multiplicative vs additive quantities)

FooBarBizBazz 3y ago
I dunno, there are some semi-useful things you can do. For example, the transform from (Alive, Bob, Carol, Dan) to (Male, Female) is linear -- it's another matrix that you can compose with the individual-ownership one you have here. Or, call your individual-ownership matrix A, and say that P is the covariance of daily changes to prices of the four stocks listed. Then A P A' is the covariance of daily changes to the peoples' wealths. The framing as linear algebra hasn't been useless. I kinda get what you're saying though. Like, why would powers of this matrix be useful? It only makes sense if there's some implicit transform between prices and people, or vice versa, that happens to be an identity matrix. You can make up a story. Say the people can borrow on margin some fraction of their wealth. Then say that they use that borrowing to buy stock, and that that borrowing affects prices. Composing all these transforms, you could get from price to price, and then ask what the dynamics are as the function is iterated. But, ok, "I'm just going to do an SVD of the matrix and put it in a slide" isn't going to tell anybody much. Maybe there's a use for a rank-one approximation to this system? Like, "this is pretty close to a situation where there's a single ETF with those stocks in these proportions, and where the people own the following numbers of shares in the ETF"? Maybe if you have millions of people and millions of stocks and wanted to simulate this "stock market" at 100Hz on a TI-83? I dunno. You can make up stories.

mark_l_watson 3y ago

Beautifully done. I subscribe to the author’s Substack, lots of other really nice stuff there. A little off topic, but this is just one more example of beautifully done content on Substack. I have seriously considered setting my freedom.to settings to only allow accessing HN, FB, Twitter, Mastodon, etc., 1 or 2 mornings a week, and that time would mostly be for ensuring that I was always subscribed to a few good Substack channels. With the explosion of ‘tech stuff I should read’, I think I need a more extreme culling of what I spend my time on.

Scene_Cast2 3y ago

Another interesting mapping is that a vector is (or can be thought of as) a discrete function (f(x) = ....) over an interval, a dot product of two vectors is a discrete integral product, and a matrix is a discrete scalar field. I wonder what the continuous form of a graph is... Some sort of a manifold perhaps?

krackers 3y ago
>continuous form of a graph A graphon? Edit: This was already mentioned by meindnoch.
enriquto 3y ago
> I wonder what the continuous form of a graph is... Some sort of a manifold perhaps? Exactly! The correspondence between manifolds and graphs is very beautiful. What many folks call today "graph signal processing" has traditionally been called "discrete differential geometry". Scalar fields are functions defined on vertices, vector fields are functions defined on edges, the incidence matrix is the gradient operator, its transpose is the divergence, the Laplacian is the divergence of the gradient, integrals and fluxes are scalar products by indicator functions, the boundary operator is minus the gradient, Green's formula is just matrix transposition, etc. You can even go further in the analogy and define p-forms as functions defined on the p-cliques of the graph, and from that rebuild a whole discrete Hodge theory. The correspondence is almost perfect, except for the fact that you cannot write easily the product rule for derivatives (because you cannot multiply pointwise scalar fields with vector fields).
- qsdf38100 3y ago
  And electromagnetism seems to be a by product of discrete differential geometry. Such a fascinating subject. Makes continuous treatment look like a mess.
shakow 3y ago
A bivariate function?
meindnoch 3y ago

kmad 3y ago

This approach reminds me of RedisGraph[1] (which is now unfortunately EoL). "RedisGraph is the first queryable Property Graph database to use sparse matrices to represent the adjacency matrix in graphs and linear algebra to query the graph." 1. https://github.com/RedisGraph/RedisGraph https://github.com/RedisGraph/RedisGraph

westurner 3y ago
RDF-star and SPARQL-star are basically Property Graph interfaces if you don't validate with e.g. RDFS (schema.org,), SHACL, json-ld-schema (jsonschema+shacl), and/or OWL. Justify Linked Data; https://5stardata.info/ https://5stardata.info/ W3C RDF-star and SPARQL-star > 2.2 RDF-star Graph Examples: https://w3c.github.io/rdf-star/cg-spec/editors_draft.html#rdf-star-graph-examples https://w3c.github.io/rdf-star/cg-spec/editors_draft.html#rd... def to_matrices(g: rdflib.MultiDiGraph) -> Union[Matrix, Tensor] rdflib.MultiDiGraph: https://networkx.org/documentation/stable/reference/classes/multidigraph.html https://networkx.org/documentation/stable/reference/classes/... Multigraph: https://en.wikipedia.org/wiki/Multigraph https://en.wikipedia.org/wiki/Multigraph : > In mathematics, and more specifically in graph theory, a multigraph is a graph which is permitted to have multiple edges (also called parallel edges[1]), that is, edges that have the same end nodes. Thus two vertices may be connected by more than one edge ... [which requires multidimensional matrices, netcdf (pydata/xarray,), tensors, or a better implementation of a representation; and edge reification in RDF] From "Why tensors? A beginner's perspective" https://news.ycombinator.com/item?id=30629931 https://news.ycombinator.com/item?id=30629931 : > https://en.wikipedia.org/wiki/Tensor https://en.wikipedia.org/wiki/Tensor ... Tensor product of graphs: https://en.wikipedia.org/wiki/Tensor_product_of_graphs https://en.wikipedia.org/wiki/Tensor_product_of_graphs Hilbert space: https://en.wikipedia.org/wiki/Hilbert_space https://en.wikipedia.org/wiki/Hilbert_space : > The inner product between two state vectors is a complex number known as a probability amplitude.

enchiridion 3y ago

I think I’m misunderstanding. The node relabeling seems backwards. He says start with the highest order, which makes me think the neighborhood with order 3 would get the smaller node labels, and the neighborhoods with order 0 would get the highest. It looks like the opposite was done.

owlbite 3y ago

Sparse Linear Algebra is Graphs all the way down.

jfarmer 3y ago

If folks are looking for terms to Google, try "spectral graph theory" and "algebraic graph theory" https://en.wikipedia.org/wiki/Spectral_graph_theory https://en.wikipedia.org/wiki/Spectral_graph_theory https://en.wikipedia.org/wiki/Algebraic_graph_theory https://en.wikipedia.org/wiki/Algebraic_graph_theory Pretty much every field in math has a related field where you try to turn problems from the former into linear algebra problems. The "spectral theorem" (https://en.wikipedia.org/wiki/Spectral_theorem https://en.wikipedia.org/wiki/Spectral_theorem) is an important theorem in linear algebra that gives conditions for when a matrix can be diagonalized, which is closely related to what its eigenvalues/eigenvectors look like. The simplest version of the spectral theorem says that a symmetric matrix with real-number entries has real-number eigenvalues. The eigenvalues of a matrix are called the "spectrum of the matrix", hence "spectral theorem" and "spectral graph theory". The adjacency matrix of any undirected graph is real symmetric, so its eigenvalues are all real numbers and it's natural to ask whether they say anything about the underlying graph. Lucky for us, there are lots of surprising connections! For example, say G is an finite undirected graph. The chromatic number of G, denoted χ(G), is the fewest number of colors needed to color its vertexes so that no two adjacent vertexes have the same color. If λ₁ is the largest eigenvalue of G's adjacency matrix then there's a theorem (Wilf's theorem) that says χ(G) ≤ 1 + ⌊λ₁⌋ That is, you can always color a graph with 1 + ⌊λ₁⌋ colors, where ⌊x⌋ is the floor of x. And there are some (finite, undirected) graphs that require exactly 1 + ⌊λ₁⌋ colors, so we're not doing any better unless we can say something more specific about the graph. Wilf's Theorem: https://www2.math.upenn.edu/~wilf/website/Eigenvalues%20of%20a%20graph.pdf https://www2.math.upenn.edu/~wilf/website/Eigenvalues%20of%2... https://www2.math.upenn.edu/~wilf/website/Inequality%20for%20Chromatic%20Number.pdf https://www2.math.upenn.edu/~wilf/website/Inequality%20for%2...