Understanding Low Threshold Rank Graphs and Their Structural Properties

Explore the intriguing world of low threshold rank graphs and their structural properties, including spectral graph theory, Cheeger's inequality, and generalizations to higher eigenvalues. Learn about the concept of threshold rank, partitioning of graphs, diameter limits, and eigenvectors approximation. Discover how these graphs can be divided into sets inducing expander graphs.

• Graph Theory
• Structural Properties
• Spectral Characterizations
• Eigenvalues
• Expander Graphs.

mcqueary_j Follow

Uploaded on Sep 12, 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. Structural Properties of Low Threshold Rank Graphs Shayan Oveis Gharan University of Washington

2. Spectral Graph Theory Combinatorial properties of a graph Spectrum of (normalized) Adjacency/Laplacian matrices 2

3. Setting Let ? be an unweighted ?-regular graph with ? = ? vertices Matrix Eigenvalues ?/? 1 ?? ?1= 1 Normlzd Adj ? ?/? 0 = 1 ?1 1 ?? 2 Normld Laplacian G is ?-expander if ?2 1 ?. Example: 4-cycle ?1= 1,?2= 0,?3= 0,?4= 1

4. Spectral Characterizations of Graphs ? is almost disconnected Cheeger s Inequality [Alon-Milman 85,Alon 86] ?2 1 Cheeger s inequality ?2 1 ? is an expander Expander Mixing Lemma ?2,?? 0 ? random ? is almost bipartite ?? 1 [Trevisan 08] 4

5. Generalizations to Higher Eigenvalues 5

6. Low Threshold Rank Graphs Think ???? ? ? 1 . The ?-threshold rank of a ?-regular graph ? is ?????? = | ??:|?? > ? | Examples: 1 Ramanujan expanders: ???? = 1 . 2 ? Dense graphs: 2 ? ? ? 1 ?2?? 2=? 2= ?2 ???? ? = ?. ?? ? ? So, ???? ? ??2. 6

7. Structure of Low Threshold Rank Graphs Thm [Tanaka 11,O-Trevisan 14]: For any graph ? and any ?, there is a 1 ??+12 ?4 partitioning of ? into ? sets each inducing an expander. So, Low threshold rank graphs are unions of ????( expander graphs 1 2) many 7

8. Diameter of Low Threshold Rank Graphs Thm [O-Trevisan 13]: For any graph ? and any ?, the diameter of ? is at most ? log ? 1 ?? . Diameter of low threshold rank graphs is at most ????(1 2)log? 8

9. Eigenvectors of Low Threshold Rank Graphs Thm [Kwok-Lau-Lee-O-Trevisan 13]: For any graph ?, any 1 ? < ?, the ?-th eigenvector ?? can be approximated by a 2k-step function ? s.t., ?? ?2 41 ?? , 1 ?? ??3 ??8 ??2 ??6 ??1 ??7 ??9 ??0 ??4 ??5 If ? is low threshold rank, each of the first few eigenvector are approx constant on each expander. 9

10. Cheegers Inequality for Low Threshold Rank Thm [Kwok-Lau-Lee-O-Trevisan 13]: For any graph ?, 1 ?2 2 1 ?2 1 ?? ? ? ? ? where ? ?, ? ? |?| ? ? = min ? ?/2?(?) = min ? ?/2 If ?? 1, then ?2 encodes expanders; Also, ?(?) does not cut an expander 10

11. Low Threshold Rank Graphs in Optimization [Kolla-Tulsiani 10, Arora-Barak-Steurer 10]: Subspace Enumeration Unique Games, Sparsest Cut and SSE admit constant factor approximations on low threshold rank graphs [Barak-Raghavendra-Steurer 11, Guruswami-Sinop 11 12]: SDP rounding 2-CSP problems, Quadratic Programming, are easy on low threshold rank graphs. 11

12. Third Approach: Weak Regularity Lemma for Low Threshold Rank Graphs 12

13. Weak Regularity Lemma [Frieze-Kannan98] For any graph ? = (?,?) and ? > 0, there are ? 1/?2 cut matrices ?1,?2, ,?? s.t. ? ?1?1+ + ????. ?? 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 ?? = ???(?? ,?? ) = ?? 13

14. Weak Regularity Lemma [Frieze-Kannan98] For any graph ? = (?,?) and ? > 0, there are ? 1/?2 cut matrices ?1,?2, ,?? s.t. for ? = ?1?1+ + ???? ? ???? ??2, i.e., = max ?,? ?| 1?, ? ? 1?| ??2 max ?,? ?? ?,? ? ?,? Gives PTAS for max-cut in dense graphs Enough to guess the intersection of |?? ???| for all ?. 14

15. Our Result Theorem (O.,Trevisan 13): For any graph ? = (?,?), ? > 0, there are ? ????(?)/?2 cut matrices ?1, ,??, s.t., ? ?1?1+ + ???? ??? ? ? . Furthermore, this can be computed in polynomial time. Gives a PTAS for max-cut, max-bisection in low threshold rank graphs 15

16. Proof Ideas 16

17. Low Rank Approximation of A Let ? ? = ? ?????? ? ? Define ? ? ?: ??>??????? Then, for ?,? ?, 1?, ? ? 1? 1? ? ? 1? 1? ? ?2 1? ? ?? ? = 2?|?| So, ? ???? 2? ? . 17

18. Main Lemma 2cut matrices ?1, ,??s.t. 1 ?2 ? (?1?1+ + ????)??? ? ? . ? ? There are ? ? This completes the proof of weak regularity lemma because ? ? ? ?: ??>? 2 2 ????(?). = ?? 18

19. 2cut matrices ?1,,??s.t. 1 ?2 ? ? Pf by Induction Lem: There are ? ? ? (?1?1+ + ????)??? ? ? . Suppose ? = ?1?1+ + ???? Suppose there is a bad cut: ?,?: |?(?,?) ?(?,?)| > ?.|?| Define ??+1= ??? ?,? and ??+1 ? ?,? ? ?,? ?2? |?| 2. ? ? We show convergence: Use potential fn ? = ? Then, ? ? ??+1??+1 ? ? ?2 2 1 ?2 ? ? ? ? 19

20. Few Remarks Proof naturally generalizes to weighted non-regular graphs To make it algorithmic, we use [Alon-Naor 05]: That for any matrix ? ? ? finds ?,? s.t. | 1?,?1?| 0.56 ???? We use LP to estimate ?? ??? ,|?? ???| for all ?. In time 2?(???? ?1.5/?3)+ ????(?,???? ? ,1 additive approximation to max-cut and max-bisection. ?) finds 8?|?| 20

21. Spectral Characterizations: Higher Eigenvalues Eigenvectors of G are 2k-step fns [Kwok-Lee-Lau-O- Trevisan 13] ?? 1 ? is union of expanders ?? 1 [O-Trevisan 14] ? ???? ? ? ? ?( ?2) cuts [O-Trevisan 13] ? has a natural ?-partitioning [Lee-O-Trevisan 12,Louis- Raghavendra-Tetali-Vempala 12] ?? 1 21

22. Conclusion and Future Directions High threshold rank graphs are natural generalization of expanders A generalization of weak regularity lemma to low threshold rank graphs Future Directions: Generalizations to hypergraphs and r-CSPs. Stronger forms of regularity Lemma for low threshold graphs 22