Graphs, Randomness and Computation
Prahladh Harsha, Tata Institute of Fundamental Research
Graphs are one of the most ubiquitous models of both natural and human-made structures. They are mathematical structures that model the pairwise relations between objects in a given set. Owing to their simplicity, almost anything can be modeled as graph: road networks, electrical circuits, internet, computation flows, neural networks, protein structures, social networks, inter-molecular behaviour etc.
Understanding properties of these graphs and developing algorithms to handle these structures is of particular interest to computer science.
In this talk, I will survey the area of graph theory, starting from the early works of Euler to recent advances in computation with graphs. These include applications in a wide variety of fields:
solving linear systems, understanding arithmetic progressions in primes (mathematics), understanding how information flows (internet, social networks, biological networks).