Results 1 to 8 of 8

Math Help - Analytic Graph Theory?

  1. #1
    Newbie
    Joined
    Apr 2010
    From
    Florida
    Posts
    21

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2010
    From
    Florida
    Posts
    21
    Quote Originally Posted by awkward View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by Xian View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by Xian View Post
    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.

    [Edit] 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]
    Last edited by awkward; June 3rd 2010 at 02:28 PM. Reason: added a P.S.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Apr 2010
    From
    Florida
    Posts
    21
    Quote Originally Posted by Swlabr View Post
    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
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Apr 2010
    From
    Florida
    Posts
    21
    Quote Originally Posted by awkward View Post
    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.

    [Edit] 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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2011, 09:59 AM
  2. (Graph Theory)Prove that graph X is a tree.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 1st 2011, 03:30 AM
  3. Replies: 0
    Last Post: September 25th 2010, 05:59 AM
  4. Graph Theory - Size of a Line Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 25th 2010, 11:15 PM
  5. Apostol - Analytic Number Theory
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: February 13th 2009, 10:01 AM

Search Tags


/mathhelpforum @mathhelpforum