Insights into Cliques and Independent Sets in Graph Theory

Exploring the concepts of cliques, independent sets, and theorems in graph theory regarding enemy relationships, maximum number of edges in 3-free graphs, and properties of multipartite graphs. The propositions and theorems discussed shed light on graph structures and their properties, providing valuable insights into the world of graph theory.

• Graph Theory
• Cliques
• Independent Sets
• Theorems
• Relationships

scode Follow

Uploaded on Nov 19, 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.

Presentation Transcript

1. Cliques and Independent Sets prepared and instructed by Shmuel Wimer Eng. Faculty, Bar-Ilan University March 2020 Cliques and Independent Sets 1

2. Turns Theorem Seldom two enemies have another common enemy. Soon two will ally to beat the third. Given ? entities, what is the maximum number of pairs of enemies sharing no common enemy? Let ? ?,? be s.t. ?? ? iff its ? and ? are enemies. The problem turns to finding the maximum number of edges in ? s.t.it is ?3-free (triangle free). March 2020 Cliques and Independent Sets 2

3. Proposition: (Mantel 1907) The maximum number of edges in an ?-vertex ?3-free graph is ?24 . Proof: Let ? ?,? be ?3-free, and ? ?, ? ? = ? = ? (max degree). ? has no triangles no edges in ? ? (neighborhood). Sum of the ? ? and all ? ? , ? ?\ ? ? ? counts every ? ? at least once. ?24. ? ? + ? ? 1 ? = ? ? ? March 2020 Cliques and Independent Sets 3

4. The complete bipartite graph ? has ?24 edges, thus achieving the bound. ? 2 is ?3-free and ? 2 , Definition: A complete multipartite graph ? is a graph whose vertices can be partitioned into sets s.t. ?? ? iff ? and ? belong to different sets. ? s (complementary) components are Equivalently, complete graphs. March 2020 Cliques and Independent Sets 4

5. We write ??1,,??where ?1,,?? are the partite sizes and ? s components are ??1, ,???. ?1 ?2 ?1 ?2 ?1 ?3 ?2 ?3 ?3 ???,??,?? Let ?1+ + ??= ?. When ?1, ,?? are s.t. ?? ?? 1, 1 ?,? ?, ? called Tur n graph ??,?. ??,?is ??+1 free. March 2020 Cliques and Independent Sets 5

6. Theorem: (Turn 1941) Let ? be an ?-vertex simple ??+1-free graph. Then ? ? ? ??,? with equality iff ? ??,? (isomorphic). Proof: (Zykov 1949) By induction on ?. ? = 1 ? ? = 0 ?2-free. Let ? > 1 and ? be ?-vertex and ??+1-free. Choose ? ? ? s.t. ? ? = ? = ?. Set ? = ? ? and ? = ? ? \?. March 2020 Cliques and Independent Sets 6

7. ? ? ? ? ? There is ? ? = ? ? + ? ?,? + ? ? . ? be ??+1-free ? ? (induced subgraph) is ??-free, otherwise ? ? ? ??+1. by induction ? ? ? ?? 1,? with equality iff ? ? ?? 1,?. March 2020 Cliques and Independent Sets 7

8. ? s incident edge belongs either to ? ? ? ?,? (linking edges) or ? ? + ? ?,? ? ? ? . ? = ? ? = ? Equality iff ? is independent and ? ? = ? ? ?. (? s internal edge cancels two of ? ?,? ). Define ? by connecting all ?? 1,? vertices to all ? ? vertices of independent set. March 2020 Cliques and Independent Sets 8

9. replace ? independent ?? 1,? ? ? ? ? ? ? ?? 1,? ??-free ??-vertex complete ?-partite ??+1- free. ? ? ? ?? 1,? ? ? ? ? . We show that among all ?-vertex complete ?-partite graphs ??,?has maximum number of edges. March 2020 Cliques and Independent Sets 9

10. Otherwise ??1,,??, ?1+ + ??= ?, and some 1 ? ? ? s.t. ?? ??> 1. Move a vertex ? from ??? to ???. The number of edges in ??1, ,??is increased by ?? 1 ??+ 1 ?? ??= ?? ?? 1 1. ? ? ? ??,? with equality iff ? ??,?. March 2020 Cliques and Independent Sets 10

11. Application to Combinatorial Geometry Place 6 police cars in town of diameter 1, maximizing car pairs ?,? s.t. ? ?,? > 1 2. 9 good pair, 6 bad pairs. 12 good pair, 3 bad pairs. ?3,6 March 2020 Cliques and Independent Sets 11

12. Theorem: Let ? points placed in 1-diameter circle. Max number of ?? pairs s.t. ? ?,? > ?23 . 1 2 is Proof: Create ?-vertex graph ? ?,? in 1-diameter circle s.t. ?? ? iff ? ?,? > 1 2. (Tur n s theorem ?3,6 largest 6-vertex excluding ?4.) Show that the desired ? is ?4-free. Let ? contain ?4 comprising quadrilateral ?,?,?,?. March 2020 Cliques and Independent Sets 12

13. Convex quadrilateral angle 90 , say ???. ? ?,? > 2 and ? ?,? > 1 1 2 ? ?,? > 1, impossible. Otherwise, let ??? >180 . ? ? ?4 ?4 ? ? ? ? ? ? March 2020 Cliques and Independent Sets 13

14. Edge length > opposite edge length > 1, impossible. 2 and one angles around ? 120 , 1 Theorem ?-vertex ? maximizing 1 2 excludes ?4. ? 3 2? 3 1 2= ?23 . Number of edges in ?3,? is 3 All edges of equilateraltriangle embedding of ?3,? in the 1-diameter circle ( ? 3 vertices at apex), exceed 1 2 length. March 2020 Cliques and Independent Sets 14

15. Ramsey's Theorem Clique in ? independent set in ?. If ? has no large cliques, reasonable that ? has. Example: Among 6 persons there are always 3 mutual acquaintances or 3 mutual non-acquaintances. Proof: ? ???? + ? ?? = 5. either ??? 3 or ? ?? 3. W.l.o.g let ??? 3. Let ?,?,? ??? . March 2020 Cliques and Independent Sets 15

16. Any of ??,??,?? ? ? triangle in ?. Else triangle in ?. Ramsey (1930): ? > 0 and ? > 0 smallest number ? ?,? s.t. ? ?,? -vertex ? either ?? ? or ?? ?. ? ?,? are called Ramsey numbers. Ramsey numbers are very difficult to determine. ? 1,? = ? ?,1 = 1, ? 2,? = ? and ? ?,2 = ?. By example ? 3,3 6. March 2020 Cliques and Independent Sets 16

17. Since in ?5 (cycle graph) ?3 ?5 and ?3 ?5 ? 3,3 6, ? 3,3 = 6. Theorem: ? 2 and ? 2 ? ?,? ? ?,? 1 + ? ? 1,? , and < if ? ?,? 1 and ? ? 1,? are even (HW). Proof: Let ? ?,? be ? ?,? 1 + ? ? 1,? -vertex and ? ?. Let ? = ? ? and ? = ?\ ? ? (nonadjacent to ?) . March 2020 Cliques and Independent Sets 17

18. Since ? + ? =? ?,? 1 + ? ? 1,? 1, one and only one of the following holds: 1. ? ? ?,? 1 2. ? ? ? 1,? . ? ? ?,? 1 : ? ? contains either ?? or ?? 1. 1. ? ? ? contains either ?? or ??. 2. ? ? ? 1,? : ? ? contains either ?? 1 or ??. ? ? ? contains either ?? or ??. March 2020 Cliques and Independent Sets 18

19. 1 or 2 holds ? contains either ?? or ??, ? ?,? ? ?,? 1 + ? ? 1,? . The determination of Ramsey number in general is a very difficult unsolved problem. Example: Determination of ? 3,3 revisited. ? 2,3 = ? 3,2 ? 3,1 + ? 2,2 = 1 + 2 = 3. ? 3,3 ? 3,2 + ? 2,3 = 3 + 3 = 6. ?3 ?5, ?3 ?5 ? 3,3 6 ? 3,3 = 6. March 2020 Cliques and Independent Sets 19

20. Example: Showing ? 3,4 = 9. ? = 8 ?3 ?, ?4 ? ? 3,4 9. ? 3,3 and ? 2,4 even, by theorem ? 3,4 ? 3,3 + ? 2,4 1 = 6 + 4 1 = 9. March 2020 Cliques and Independent Sets 20

21. Bounds on Ramsey Numbers ? + ? 2 ? 1 Theorem: ?,? ? ?,? . Proof: By induction on ? + ?. Holds for ? + ? 5. 4 1. ? 3,2 = 3 =5 2 ? 4,1 = 1 =5 2 3 1. Assume by induction it holds 5 ? + ? < ? + ?. ? + ? 3 ? 1 ? ?,? ? ?,? 1 + ? ? 1,? + ? + ? 3 ? 2 ? + ? 2 ? 1 = . March 2020 Cliques and Independent Sets 21

22. Corollary: ?,? ? ?,? 2?+?2, with equality iff ? = ? = 1. ? + ? 2 ? 1 Proof: ? ?,? is the number of ? 1 - subsets of a ? + ? 2 -set, whereas 2?+? 2 is the total number of subsets. ? ?,? is called diagonal Ramsey number. The above shows that it grows at most exponentially. It is also bounded below exponentially. March 2020 Cliques and Independent Sets 22

23. Theorem: (Erds 1947) ? , ? ?,? 2 ? 2. Proof: Because ? 1,1 = 1 and ? 2,2 = 2, we may assume that ? 3. Let G G? be all simple graphs with ? = ?1,?2, ,??. ? 2 total ???? pairs G G? = 2 Let G G?,? G G? having ?? subgraph. ? 2 . ? 2 edges ? 2 ? Fixing particular ??subgraph excludes number of graphs in G G? having particular ?? is 2 2 . March 2020 Cliques and Independent Sets 23

24. ? 2 ? ? ? distinct ?? G G?,? ? ?2 2 . because ? G G?,? with some ?? counted few times. 2 <??2 ? ? ?2 ? G G?,? G G? 2 . ?! Suppose ? < 2 ? 2. ?222 ? ?! ThenG G?,? =2 ? 2 ?!<1 <2 2 2. G G? March 2020 Cliques and Independent Sets 24

25. i.e., ? < 2 ? 2 less than1 2 of G G? contain ??. Complementarity less than1 2 of G G? contain ??. G G?has graphs containing neither ?? nor ??. Holds for any ? < 2 ? 2 ? ?,? 2 ? 2. March 2020 Cliques and Independent Sets 25

26. Shannon Capacity Study the relation between maximum independent set and maximum number of distinct words that can be safely used in a message over a noisy channel . A message (sequence of words of ?chars) consisting of signals belonging to a certain finite alphabet ? is transmitted over a noisy channel. Some pairs of chars are so similar that they can be confounded by the receiver due to noise March 2020 Cliques and Independent Sets 26

27. What is the largest number of distinct words that can be used in messages w/o confusion at the receiver due to noise? Example: ? = {0,1,2,3,4} and ? = 2. Noise results errors of type ? + 1 and ? 1 (mod 5). 5-word message 00, 12, 24, 31, 43, is safe. Because distinct words are guaranteed under all errors, and erroneous words are distinctive. March 2020 Cliques and Independent Sets 27

28. Definition. The strong product ? ?of two graphs ? and ?is defined by ? ? ? ?(?) ?(?). Let ?,? ? ? and ?,? ? ? . Two vertices ?? ? ? ? and ?? ? ? ? define an edge in ? ? ? if: ?? ? ? and ? = ?, or ?? ? ? and ? = ?, or ?? ? ? and ?? ? ? . March 2020 Cliques and Independent Sets 28

29. 0 ?5 ?5 4 0 0 ?? 3 4 1 4 1 = ?? ?? 2 ?? 3 2 3 2 1 0 0 1 2 3 4 0 0 vertices are unique point on torus. March 2020 Cliques and Independent Sets 29

30. ? vertex set is alphabet ?. Edge ?? is defined if ? and ? represent signals (characters) that might be confused with each other. ??= ? ? ?, strong product of ? copies of ?, representing words of length ? over ?. What are the edges of ??? (HW) ?? edges correspond to words that might be confused with each other. March 2020 Cliques and Independent Sets 30

31. Largest number of distinct words equals ? ??. 0 4 3 In this example ? = 2 and ?(?52) = 5. 2 1 0 0 1 2 3 4 0 March 2020 Cliques and Independent Sets 31

32. Shannon proposed in information theory (1956) the parameter ?? ??, ? ? = lim ? known as Shannon capacity of ?, as a measure of the capacity for error-free transmission over a noise channel whose associated graph is ?. March 2020 Cliques and Independent Sets 32