Applications of Graph Theory (2007)

Applications of Graph Theory (2007)(dharwadker.org)

58 points by aoldoni 10 years ago | 12 comments

1971genocide 10 years ago |

As a mathematical peasant who does modelling.

# If you have a small data set - you set notation.

# If you have 100s of larger data set - try to formulate your problem as a graph theory problem - Its easy to walk small graphs.

# If you have 10,000 data points - start to think of your problem in terms of matrix.

I know there is going to strong disagreement about my rule of thumb but I found it useful for many problems.

sdenton4 10 years ago | |

Fair enough. Graph theory has a collection of quite well-known algorithms that run fast, which mostly come down to clever manipulations of depth-first and breadth-first search algorithms. These typically run in O(n+k), where n is the number of vertices and k is the number of edges. In large networks, it's still often the case that k is proportional to n (most people have less than 1000 facebook friends, so we can bound k by 1000n...), so this is still linear in n.

I tend to see lots of graph algorithms which run in O(n^3) time, which tends to be fine for medium-sized data sets, but yeah, breaks down when you get into the 10,000+ sized data sets.

And then there's 'matrix' methods you mention. These can often be tied to an area called algebraic graph theory, which looks at properties of matrices (like the adjacency matrix) to try to pull out information about the graph. Relaxing the graph problem and allowing the full range of matrix operations allows some fast linear algebraic methods to be used, though the final solution may need some massaging to make sense, and may not be perfectly optimal.

A great example of this is spectral clustering, which uses eigenvectors of a relative of the adjacency matrix to perform a clustering of the graph's nodes. The optimization that the clustering is solving is actually an (iirc) NP-hard problem; casting it as an eigenvalue problem gives an O(n^2) approximation of a solution, which then gets hammered into something we can live with...

amelius 10 years ago |

When reading the title, I was thinking more of real-world applications. For instance, the Cantor-Schröder-Bernstein theorem or the "Knight tour's" problems seem like rather abstract problems.

johnaspden 10 years ago |

Wow! I tried to prove Cantor-Schroder-Bernstein last year and couldn't get my head round it. This makes it obvious!

lifeisstillgood 10 years ago |

My positive takeaway from this is that "graph theory" which I see as a single lump of knowledge (that I don't have), is actually still developing and being used by practitioners - the paper several times in the summary mentions "rapidly growing fields etc). To me that signals the use of this is changing, and being a dumb ass who knows nothing is not so bad

sotojuan 10 years ago |

A bit off topic, but what are some good resources for studying graph theory?

pmiller2 10 years ago | |

I strongly recommend Introduction to Graph Theory, 2nd edition, by Doug West. It covers the basics right up through graduate-level material, and has excellent exercises.

chudi 10 years ago | |

Graph Theory and Its Applications by Gross and Yellen its a good book.

coliveira 10 years ago | |

A book: Graph Theory, by R. Diestel, Springer Verlag.

antonio-rt 10 years ago |

http://barabasi.com/networksciencebook/

gphilip 10 years ago |

From the home page (http://www.dharwadker.org/):

A new proof of the Four Colour Theorem, by Ashay Dharwadker.

Abstract

#########################################

We present a new proof of the famous four colour theorem using algebraic and topological methods. Recent research in physics shows that this proof directly implies the Grand Unification of the Standard Model with Quantum Gravity in its physical interpretation and conversely the existence of the standard model of particle physics shows that nature applies this proof of the four colour theorem at the most fundamental level, giving us a grand unified theory. In particular, we have shown how to use this theory to predict the Higgs Boson Mass [arXiv:0912.5189] with precision. Thus, nature itself demonstrates the logical completeness and consistency of the proof. This proof was first announced by the Canadian Mathematical Society in 2000. The proof appears as the twelfth chapter of the text book Graph Theory published by Orient Longman and Universities Press of India in 2008. This proof has also been published in the Euroacademy Series Baltic Horizons No. 14 (111) dedicated to Fundamental Research in Mathematics in 2010. Finally, the proof features in an exquisitely illustrated edition of The Four Colour Theorem published by Amazon in 2011. The Endowed Chair of the Institute of Mathematics in recognition of this achievement was bestowed in 2012.

#########################################

Title: Grand Unification of the Standard Model with Quantum Gravity Author: Ashay Dharwadker

Abstract:

#########################################

We show that the mathematical proof of the four colour theorem [1] directly implies the existence of the standard model, together with quantum gravity, in its physical interpretation. Conversely, the experimentally observable standard model and quantum gravity show that nature applies the mathematical proof of the four colour theorem, at the most fundamental level. We preserve all the established working theories of physics: Quantum Mechanics, Special and General Relativity, Quantum Electrodynamics (QED), the Electroweak model and Quantum Chromodynamics (QCD). We build upon these theories, unifying all of them with Einstein's law of gravity. Quantum gravity is a direct and unavoidable consequence of the theory. The main construction of the Steiner system in the proof of the four colour theorem already defines the gravitational fields of all the particles of the standard model. Our first goal is to construct all the particles constituting the classic standard model, in exact agreement with 't Hooft's table [8]. We are able to predict the exact mass of the Higgs particle and the CP violation and mixing angle of weak interactions. Our second goal is to construct the gauge groups and explicitly calculate the gauge coupling constants of the force fields. We show how the gauge groups are embedded in a sequence along the cosmological timeline in the grand unification. Finally, we calculate the mass ratios of the particles of the standard model. Thus, the mathematical proof of the four colour theorem shows that the grand unification of the standard model with quantum gravity is complete, and rules out the possibility of finding any other kinds of particles.

#########################################