1. ## Analytic Graph Theory?

I was just wondering if anyone knew...

Is there a field in which analysis is used to solve graph theoretic problems? I've tried quite hard to find such a thing on google but most things that turn up are related to analysis of graphs and social network analysis and the such. This is not what I want.

I know that probability theory has been used to some extant for existence proof (e.g. Erdos), but I haven't seen anything like hard core analysis being used.

There exist Analytic Number Theory, but no Analytic Graph Theory?
Is there really such a gaping vacuum?

2. Generating functions are often used to analyze graphs, often in conjunction with tools of analysis-- in order to obtain asymptotic estimates of rates of growth, for example.

3. Originally Posted by awkward
Generating functions are often used to analyze graphs, often in conjunction with tools of analysis-- in order to obtain asymptotic estimates of rates of growth, for example.
Hmm, interesting. Would you be able to direct me to any resources? Even so, it seems as though analytic graph theory is still in its infancy.

4. Originally Posted by Xian
I was just wondering if anyone knew...

Is there a field in which analysis is used to solve graph theoretic problems? I've tried quite hard to find such a thing on google but most things that turn up are related to analysis of graphs and social network analysis and the such. This is not what I want.

I know that probability theory has been used to some extant for existence proof (e.g. Erdos), but I haven't seen anything like hard core analysis being used.

There exist Analytic Number Theory, but no Analytic Graph Theory?
Is there really such a gaping vacuum?
I know very little about graph theory. However, as I understand it it is a subject which is much studied by computer scientists and less so by mathematicians (I met a graph theorist at a conference recently who spent most of his time in a computer science conference that was going on across the road). Computer scientist are not mathematicians, and so analysis is not something they would necessarily feel comfortable with.

However, graphs are used in mathematics to study things, and often then analysis is used. For example, look up "ends of groups" - an end is the limit of a connected component of the cayley graph of a tree, and they are, I suppose, well understood (in the sense that a classification exists for them).

Analysis is also used in group theory to study, for example, amenability.

5. Originally Posted by Xian
Hmm, interesting. Would you be able to direct me to any resources? Even so, it seems as though analytic graph theory is still in its infancy.
One good source is "A Course in Combinatorics, Second Edition" by van Lint and Wilson.

There are also many examples of application of generating functions to graphs in "Enumerative Combinatorics" (two volumes) by Stanley, and "Analytic Combinatorics" by Flajolet and Sedgewick. However, the graph theory tends to be spread throughout these books, whereas the book by van Lint and Wilson has some chapters devoted to graph theory.

 You might also look up the Polya Enumeration Theorem (PET), also known as Polya's Theory of Counting, which was invented for the purpose of investigating graph-theoretic structures via generating functions. [/Edit]

6. Originally Posted by Swlabr
I know very little about graph theory. However, as I understand it it is a subject which is much studied by computer scientists and less so by mathematicians (I met a graph theorist at a conference recently who spent most of his time in a computer science conference that was going on across the road). Computer scientist are not mathematicians, and so analysis is not something they would necessarily feel comfortable with.

However, graphs are used in mathematics to study things, and often then analysis is used. For example, look up "ends of groups" - an end is the limit of a connected component of the cayley graph of a tree, and they are, I suppose, well understood (in the sense that a classification exists for them).

Analysis is also used in group theory to study, for example, amenability.
Thanks for the tip on ends of groups. I've recently started developing an interestnig geometric group theory and this sounds like a very neat things indeed

7. Originally Posted by awkward
One good source is "A Course in Combinatorics, Second Edition" by van Lint and Wilson.

There are also many examples of application of generating functions to graphs in "Enumerative Combinatorics" (two volumes) by Stanley, and "Analytic Combinatorics" by Flajolet and Sedgewick. However, the graph theory tends to be spread throughout these books, whereas the book by van Lint and Wilson has some chapters devoted to graph theory.

 You might also look up the Polya Enumeration Theorem (PET), also known as Polya's Theory of Counting, which was invented for the purpose of investigating graph-theoretic structures via generating functions. [/Edit]
Thanks for the tip. I'll look into the book at my school's library. The PET suggestion is definitely something interesting, looks powerful (though extremely technical). Thanks man.

8. Good stuff!

You may also want to look up quasi-isometries of groups. This is basically an attempt at a classification of groups by their Cayley graphs. Essentially, two groups are quasi-isometric if when you zoom out far enough your cayley graphs still look the same (so, for example, ends of groups will be invarient under quasi-isometries. So if two groups are quasi-isometric then they have the same number of ends).

You will definatly want to look up Hyperbolic groups (aka Word Hyperbolic, Gromov hyperbolic, negatively curved group etc.). A hyperbolic group is a group where one can define something called a Hyperbolic metric on its Cayley graph in a nice way. These groups have some very neat properties (one can always tell, in finite time, if two given elements are conjugate, and if two given hyperbolic groups are isomorphic. Neither of these two questions is answerable for an arbitrary group) and are studied extensively.