Understanding Graph Theory: Friendship Theorem and Freshman's Dream

Slide Note
Embed
Share

Explore the intriguing concepts of the Friendship Theorem and Freshman's Dream in graph theory along with examples and visual illustrations. Learn about common friends, relationships between vertices and edges, and what defines a graph in a concise yet comprehensive manner.


Uploaded on Jul 20, 2024 | 0 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. The Friendship Theorem Dr. John S. Caughman Portland State University

  2. Public Service Announcement Freshman s Dream (a+b)p=ap+bp mod p when a, b are integers and p is prime.

  3. Freshmans Dream Generalizes! (a1+a2+ +an)p=a1p +a2p+ +anp mod p when a, b are integers and p is prime.

  4. Freshmans Dream Generalizes * a1 A = * * 0 a2 * * 0 0 a3 * 0 0 0 a4 (a1+a2+ +an)p = a1p +a2p+ +anp tr(A) p = tr(Ap) (mod p)

  5. Freshmans Dream Generalizes! * * A = * * * * * * * * * * * * * * tr(A) p = tr(Ap) (mod p) tr(A p)= tr((L+U)p) = tr(Lp +Up) = tr(Lp)+tr(Up)=0+tr(U)p = tr(A)p Note:tr(UL)=tr(LU) so cross terms combine , and coefficients =0 mod p.

  6. The Theorem If every pair of people at a party has precisely one common friend, then there must be a person who is everybody's friend.

  7. Cheap Example Nancy John Mark

  8. Cheap Example of a Graph Nancy John Mark

  9. What a Graph IS: Nancy John Mark

  10. What a Graph IS: Nancy Vertices! John Mark

  11. What a Graph IS: Nancy Edges! John Mark

  12. What a Graph IS NOT: Nancy John Mark

  13. What a Graph IS NOT: Loops! Nancy John Mark

  14. What a Graph IS NOT: Loops! Nancy John Mark

  15. What a Graph IS NOT: Nancy Directed edges! Mark John

  16. What a Graph IS NOT: Nancy Directed edges! Mark John

  17. What a Graph IS NOT: Nancy Multi-edges! John Mark

  18. What a Graph IS NOT: Nancy Multi-edges! John Mark

  19. Simple Graphs Nancy Finite Undirected No Loops No Multiple Edges John Mark

  20. The Theorem, Restated Let G be a simple graph with n vertices. If every pair of vertices in G has precisely one common neighbor, then G has a vertex with n-1 neighbors.

  21. The Theorem, Restated Generally attributed to Erd s (1966). Easily proved using linear algebra. Combinatorial proofs more elusive.

  22. NOT A TYPICAL THRESHOLD RESULT

  23. Pigeonhole Principle If more than n pigeons are placed into n or fewer holes, then at least one hole will contain more than one pigeon.

  24. Some threshold results If a graph with n vertices has > n2/4 edges, then there must be a set of 3 mutual neighbors. If it has > n(n-2)/2 edges, then there must be a vertex with n-1 neighbors.

  25. Extremal Graph Theory If this were an extremal problem, we would expect graphs with MORE edges than ours to also satisfy the same conclusion

  26. 1

  27. 1 2

  28. 1 2 3

  29. 1 4 2 3

  30. 4

  31. 4

  32. 4

  33. 2

  34. Of the 15 pairs, 3 have four neighbors in common and 12 have two in common. So ALL pairs have at least one in common. But NO vertex has five neighbors!

  35. Related Fact losing edges

  36. Related Fact losing edges

  37. Related Fact losing edges

  38. Summary If every pair of vertices in a graph has at least one neighbor in common, it might not be possible to remove edges and produce a subgraph in which every pair has exactly one common neighbor.

  39. Accolades for Friendship The Friendship Theorem is listed among Abad's 100 Greatest Theorems The proof is immortalized in Aigner and Ziegler's Proofs from THE BOOK.

  40. Example 1

  41. Example 2

  42. Example 3

  43. How to prove it: STEP ONE: If x and y are not neighbors, they have the same # of neighbors. Why: Let Nx = set of neighbors of x Let Ny = set of neighbors of y

  44. How to prove it: y x

  45. How to prove it: y x Nx

  46. How to prove it: y x Ny

Related


More Related Content