Existence of Ramsey Numbers

Loading...

En provenance du cours de University of California San Diego

Introduction to Graph Theory

100 notes

University of California San Diego

Introduction to Graph Theory

100 notes

Cours 3 sur 5 dans Specialization Introduction to Discrete Mathematics for Computer Science

We invite you to a fascinating journey into Graph Theory — an area which connects the elegance of painting and the rigor of mathematics; is simple, but not unsophisticated. Graph Theory gives us, both an easy way to pictorially represent many major mathematical results, and insights into the deep theories behind them. In this course, among other intriguing applications, we will see how GPS systems find shortest routes, how engineers design integrated circuits, how biologists assemble genomes, why a political map can always be colored using a few colors. We will study Ramsey Theory which proves that in a large system, complete disorder is impossible! By the end of the course, we will implement an algorithm which finds an optimal assignment of students to schools. This algorithm, developed by David Gale and Lloyd S. Shapley, was later recognized by the conferral of Nobel Prize in Economics. As prerequisites we assume only basic math (e.g., we expect you to know what is a square or how to add fractions), basic programming in python (functions, loops, recursion), common sense and curiosity. Our intended audience are all people that work or plan to work in IT, starting from motivated high school students.

À partir de la leçon

Graph Parameters

We'll focus on the graph parameters and related problems. First, we'll define graph colorings, and see why political maps can be colored in just four colors. Then we will see how cliques and independent sets are related in graphs. Using these notions, we'll prove Ramsey Theorem which states that in a large system, complete disorder is impossible! Finally, we'll study vertex covers, and learn how to find the minimum number of computers which control all network connections.

Balanced Graphs2:30

Ramsey Numbers2:17

Existence of Ramsey Numbers5:56

Rencontrer les enseignants

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering

How do we know that Ramsey numbers exist?

How do I know that for every values of k and l that exist,

a Ramsey number of k and l.

This would mean that whatever values for k and l you pick,

large enough graphs always contain, either a large clique or a large Independent set.

Well, we know that for small values of k and l, the Ramsey numbers do exist.

For example, if k and l are both at most 3 then yes.

Numbers do exist.

We will know them.

And later, we will prove that R(k,l) is less than or

equal to R(k-1) of l plus R of k and l minus 1.

Which gives us an upper bound on the Ramsey number for

all values of k and l, which means that for every variable of k and

for every variable of l, there exists a Ramsey number R(k,l).

Which means whatever radius you fix for k and l,

large enough graphs will always contain either a clique of size k,

or an independent set of size l.

Let us now prove this inequality.

This is the main theorem in Ramsey's Theorem.

So we want to prove that R(k,l) is less than or

equal to than R(k-1,l)+R(k,l-1).

How do we do this?

Consider a graph g on that many vertices.

Note that so that it either contains a Clique of size k or

an Independent set of size l In order to do so, we fix on vertex v.

And let A denote the set of neighbors of v and

B denote the remaining vertices.

So v is connected to all vertices in A, and is not connected to any vertex in B.

Now whenever the total number of vertices in this graph is a size of A plus

the size of B plus 1, we're going to count the vertex v itself.

On the other hand, the number of vertices in this

graph is R(k- 1,l) + R(k, l- 1).

From this, we can conclude that either A is greater than

R of k minus 1 and or B is greater than R of k and l minus one.

Indeed, assume what?

Assume both of them are less than their sum plus one will

be smaller than R o (k-1) and l plus R(kl-1).

So just one of these inequalities must hold.

Let us now assume that the first inequality holds,

namely that A is greater than or equal to R(k- 1,l).

By the definition of this Ramsey number, it means that either

the subgraph on on A vertices contains an independent set of size l.

In which case, we are done because it means that our original graph contains

an independent set of size l.

That's exactly what we want to prove.

Or maybe this graph on A only contains a clique of size k- 1.

But this case is also good for us, because now we can add v to these vertices from A.

And since v is connected to all vertices from A,

they all together form a clique of size k.

Which is, again, exactly what we want to prove.

So in one case, we show that there exists a large independent set.

In the other case we show that there exists a large clique.

This was the first case.

The second case is when B is greater than or equal to a power k(l-1).

And again, the definition of the Ramsey number,

this means that either B has a k-clique, which is good for us, we're done.

Our original class is k-clique.

Or maybe B contains an independent set of size only l-1.

But now, again, we join the set b with our vertex v.

Since v is not connected to anything in B, it altogether form

an independent set of size l, exactly what we wanted to find.

Now, let's see how this proof works on an example.

Let me draw all the labels of the vertex B, on the left, and

all the vertices which are not connected to B, on the right.

So the left, I have this part of the graph we check called A in the proof, and

on the right, I have this part of the graph which I call B in the proof.

In those two cases, I assert A is greater than R(k -1, l) or

B is greater than R of k l minus 1.

Consider the first case.

But the definition of this Ramsey number (k-1,l)

either A contains an independent set of size l.

Which means our graph contains an independent set of size l and better.

Or A contains a Clique of size k-1.

But then, we're going to add this word XV to the clique, and

we'll have a clique of size K which is good.

This is exactly what we wanted to find.

If that's the case, if B is large,

then again I said B contains a K clique, which is good for us.

Or B contains an independent set of size L-1.

And then we can add there, third [INAUDIBLE] theory, and

get an independent set of size L.

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2018 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play