1
ECS 20 — Lecture 16 — Fall 2013 —19 Nov 2013
Phil Rogaway
Today:
Remaining topics: graphs, counting, and probability
Pigeonhole Principle
Recall:
Restated: [Pigeonhole principle]
If f : A B where A and B are finite sets, |A|>|B|, then f is NOT injective. Stronger form
[Pigeonhole principle, strong form]
Eg, if 100 pigeons roost in 30 holes, some hole has at least 4 pigeons roosting therein.
Ex: Given five points inside the square whose side is of length 2, prove that two are within \sqrt{2} of each other.
Soln: divide square into four 1 x 1 cells. Diameter of each cell = \sqrt{2}
Ex. (beautiful example) In any room of 6 people, there are 3 mutual friends or 3 mutual strangers (Ramsey theorem, and R(3,3)=6)
1
2
3 54
Quiz 3
Finish pigeonhole applications Graphs
If f : A B where A and B are finite sets, then so point bB must have at least |B|/|A|
preimages.
6
Remove person 1 5 people left.
Put into two pots: friends with 1, non-friends with 1.
One has at least three people.
If three friends: Case 1: some two know each other: DONE
Case 2: no two know each other: DONE
If three non-friends: …o
Difficult Puzzle: What is the minimum number of people that must assemble in a room such that there will be at least n friends or n non-friends: R(n,n)
R(4,4) = 18 (1955)
R(5,5) = ?? open!!! known to be between 43 (1989) and 49 (1995)
R(10,10) =?? open and not tightly determined at all: range 798 (1986)- 23,556 (2002)
Cliques and Ramsey numbers
The following definitions assume graph-theory terminology, to be introduced shortly. A clique of size n in a graph is a set of n mutually connected vertices. Denote Kn .
An independent set of size m in a graph is a set of m vertices that are mutually non-adjacent.
Clique number (G) = size of a largest clique within G (largest subgraph that’s a clique) FACT: There is no efficient algorithm known to calculate k(G).
Let R(n,m) = the minimum number of vertices such that a graph of
R(n,m) vertices either has a clique of size n or an independent set of size m.
Alternative version:
R(n,m) = the minimum number of vertices such that if you red/blue color the edges of a graph with
of R(n,m) vertices, there is either a red clique of size n or a blue clique of size m.
Theorem: The above is well-defined:
for every n,m1 there exists a smallest number R(n,m) such that every
graph on R(n,m) vertices contains either a clique of size n or an independent set of size m.
Claim: R(3,3)=6
Interpretation: In any room of 6 people, there are 3 mutual friends or
3 mutual strangers.
R(n,m): First, R(3,3)6. Draw a five pointed start surrounded by a circle. There is no triangle and no independent set of size 3.
Second, R(3,3) 6
Remove person 1 5 people left.
Put into two pots: friends with 1, non-friends with 1. One has at least three people.
2
If three friends: Case 1: some two know each other: DONE Case 2: no two know each other: DONE
If three non-friends: …o
Difficult Puzzle: What is the minimum number of people that must assemble in a room
such that there will be at least n friends or n non-friends: R(n,n)
R(4,4) = 18 (Greenwood and Gleason, 1955) R(5,5) in [43, 49] Exoo, 1989; Radziszowski 1995 R(6,6) in [102,165]
“Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of R(5, 5) or they will destroy our planet. In that case, he claims, we should marshal all our computers [not computer scientists?!] and all our mathematicians and attempt to find the value.
“But suppose, instead, that they ask for R(6, 6). In that case, he believes, we should attempt to destroy the aliens.” Quoted by
Graph theory
Graph theory
3
1. 2. 3. 4. 5. 6. 7. 8. 9. 10.
Basic definitions
Representation of graphs Isomorphic graphs
Paths and cycles
Trees
Eulerian and Hamiltonian graphs Longest and shortest paths
Cliques and Ramsey numbers
1. Basic Definitions
Def: A (finite, simple) graph G=(V, E) is an ordered pair – V is a nonempty finite set (the vertices or nodes)
– E is a set of two-elements subsets of V (the edges)
There are many other “kinds” of graphs—for example, in a directed graph (digraph), the edges (now often called arcs) are ordered pairs, instead of unordered pairs. But, for this lecture, let’s stick to simple graph, the kind that I defined.
Conventional representation: picture.
Be clear: the picture is NOT the graph, it is a representation of the graph.
B— C /\/
AD
B— D /\/
AC
are the SAME graph.
Not a graph: draw a self-loop, multiple loops, empty set. Def: Two vertices v, w of a graph G=(V, E) are adjacent if {v,w}E.
Def: The degree of a vertex deg(v) = |{v,w}: wV|
Question: what is the maximal and minimal degrees of an n-vertex graph?
I like {x,y} for an edge, emphasizing that {x,y} are unordered.
Will sometimes see xy or (x,y), but both look like the order matters, which, in a simple graph, it does not.
Usually we use n=|V| and m=|E|; alternatively, =|V| and =|E| Prop: v deg(v) = 2m
We don’t usually care about the names of points in V, only how they’re connected up.
That’s because the properties of the graphs that matter are those that are invariant under isomorphism. Two graphs G=(V, E) and G’=(V’, E’) are isomorphic if there is a permutation : V V’ such that {v,w}E iff {(v),(w)}E’. Explain.
Give examples of properties that are (and are not) preserved under isomorphism
How many different graphs are there on V={1,…,n}? 2^{n choose 2} = 2^{n(n-1)/2} 2. Representation of graphs
Two common ways: adjacency matrix and adjacency list.
Describe them. Likely this was covered in 30 in or 40, which many students have had, although certainly not everyone.
3. Isomorphic graphs
Def: Graphs G=(V,E) and G’=(V’,E’) are isomorphic if there exists a permutation such that {x,y}E iff {(x),(y)}E’.
Amazing fact: there is no efficient algorithm known to decide if two graphs are isomorphic. (Most computer scientists believe that no such algorithm exists.) One of the biggest open questions in computer science.
4
5