Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Wikipedia teaches us that problems in Ramsey theory typically ask a question of the form: "how many elements of some structure must there be to guarantee that a particular property will hold?"

It also teaches us that "Extremal graph theory studies extremal (maximal or minimal) graphs which satisfy a certain property". This sounds very similar. Let's take Turan's theorem (the basic example of an EGT theorem) - it gives a bound on the number of edges in a clique-free graph (for a given clique size). Put differently, it tells us how many elements (edges) of a certain structure (graph with fixed number of vertices) must be there to guarantee that a particular property (existence of a clique of a specific size) will hold.

One can argue that in EGT we try to understand the structure of the extremal objects, but I don't see why Ramsey theory should not try to do the same thing, and also I don't see how this is done in the (beautiful) Erdős–Stone theorem which is considered a fundamental theorem of EGT.

So is there a real difference or is it just a matter of taste?

share|improve this question
1  
I think EGT is a subset of Ramsey theory. In Ramsey theory, we are concerned with structures other then graphs as well, for example in linear equations (Rado's theorem). –  Shahab Sep 1 '11 at 11:28
add comment

1 Answer

up vote 4 down vote accepted

I agree with Shahab's comment above. Ramsey theory is certainly more general, and is usually concerned with questions of unavoidable order contained within even the most chaotic structures. Some of these questions (and answers) can be stated (or solved) in a graph-theoretic context using the techniques of extremal graph theory.

Extremal graph theory tends to focus on graph-specific questions of minimality/maximality. Questions like how do I guarantee that every vertex in a subgraph has a given minimum degree? How many disjoint cycles must a graph of size $m$ have? Or given a $k$-regular graph what is its minimum/maximum girth? These are questions dealing with the explicit constructions and natures of the objects of graph theory. Sometimes the results that are obtained find applicability in "real" world applications, but often they simply help us to better understand the extremal nature of regular graphs.

I think that is the difference suggested at the end of your question. Extremal graph theory studies the extremal properties of regular graphs, while Ramsey theory is more concerned with the necessary (regular) properties of extremal graphs.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.