### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# TOPIC MATH 778S

GPA 3.51

### View Full Document

## 22

## 0

## Popular in Course

## Popular in Mathematics (M)

This 18 page Class Notes was uploaded by Cassidy Grimes on Monday October 26, 2015. The Class Notes belongs to MATH 778S at University of South Carolina - Columbia taught by L. Lu in Fall. Since its upload, it has received 22 views. For similar materials see /class/229530/math-778s-university-of-south-carolina-columbia in Mathematics (M) at University of South Carolina - Columbia.

## Reviews for TOPIC

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/26/15

Math 7788 Spectral Graph Theory Handout 1 Basic linear algebra Let A be an n X nmatrixi If there exists a nonzero column vector 1 and a number A satisfying Aa Aa we say A is an eigenvalue of A and a is an eigenvector of A corresponding to the eigenvalue A For any 5 f 0 ca is also an eigenvector of A We can normalize it so that 1 becomes a unit vector Note that a and A is NOT necessary to be real even if A is a real matrixi All eigenvalues A1 A2 i An are the root of the characteristic polynomial n detw 7 A HQ 7 My By comparing the coef cient we have H A det A i1 Z A MA i1 Here trA 221 aii is called the trace of a matrix Let be any polynomial of I It is easy to check that fAa ow In conclusion has eigenvalues f1 f2i i In particular we ave EA My i1 From now on we assume A is a symmetric real matrix ie A A Then all eigenvalues are real and all eigenvectors can be made into an orthogonal basei Two eigenvectors corresponding to the distinct eigenvalues are always or thogonal to each other Two eigenvectors corresponding to the same eigenvalue is not always orthogonal to each other A matrix 0 is orthogonal if 0 O li There exists an orthogonal matrix 0 satisfying AO OAi Here A is a diagonal matrix with diagonal entries A1 A2 i i Ani Let ai be the ith column of 0 Then ai is the eigenvector corresponding to Air liei Aai Mail Example 1 Find all eigenvalues and eigenvectors of 0 1 0 A 1 0 1 0 1 0 Solution A 71 0 detA17A det 71 A 71 0 71 A A372A AA 7 x Thus A has three distinct eigenvalues V20 7amp1 To nd an eigenvector for A1 we solve 71 0 z 0 71 71 y 0 0 71 2 0 We have y x and y This system of linear equations has in nitely many solutions of form 6 1 Up to a sign we get a unit eigenvector To nd an eigenvector for A1 0 we solve mw mw 0 71 0 z 0 71 0 71 y 0 0 71 0 2 0 We have y 0 and z 2 0 This system of linear equations has in nitely many solutions of form 1 0 71 Up to a sign we get a unit eigenvector To nd an eigenvector for A3 i we solve 7 71 0 z 0 71 7 71 y 0 0 71 7 2 0 We have y 7amp2 and y i zi This system of linear equations has in nitely many solutions of form 67 1 Up to a sign7 we have a unit eigenvector l 2 a1 1 2 The eigenvectors a1 a2 13 are orthogonal to one another Let 0 ozl7 a2 13 be the orthogonal rnatrixi We have 2 010 oo 507 101 g0 000 010 57 oo i Math 7788 Spectral Graph Theory Handout 3 Eigenvalues of Adjacency Matrix The Cartesian product denoted by G D H of two simple graphs G and H has the vertexset VG gtlt For any u7 v E VG and xy E VH7 u7x is adjacent to v7 y if either u v and xy 6 EH77 or uv E EG and x y77i Lemma 1 Suppose AlpiWAn are eigenvalues of the adjacency matrix of a graph G and 1 i i i um are eigenvalues of the adjacency matrix of a graph H Then the eigenvalues of the adjacency matrix of the Cartesian product G D H areAiujf0rl i n andlSjSm Proof Let A or B be the adjacency matrix of G or H respectively For any eigenvalue A of A and any eigenvalue u of B7 we would like to show A u is an eigenvalue of G D Hi Let a be the eigenvector of A corresponding to A and B be the eigenvector of B corresponding to a We have Aa Aa 1 BB w 2 Equivalently7 for any u E lG7 Zav Aau for any x E VH7 25y 5 gm Let 1 6 be the n X m column vector de ned by entries 1 may au x Let C be the adjacency matrix of G D Hi We would like to show 1 5 is an eigenvector of C We have7 for any u7x E VG D H7 Z a vy Z av y vgtyNugtr vgtyNu c Z au y Z av x UgtyNu vgt Nugtr Z au y Z av x W Mu H E M E Jr a M E auM x anu A We BUT This is equivalent to 0lta x B 7 M ma x 5 Thus A M is an eigenvalue of G D Hi Forlgignandlgjgmiuj G D H has nm vertices these 39 w of G D H i D Remark The adjacency matrix of G D H can be written as A Imln Bi Here is tensor product of matrices are eigenvalues of G D Hi Since 1th are all Hypercube Qn The vertices of Qn are points in ndirnensional space over the eld of two elements F2 01 Two points are adjacent in Q7 if and only if they differ by exactly one coordinate We have Q1 2 2 C4 and Q3 is the cube in 3dirnensional space We have Qn1 Q1 D The eigenvalues of Qn can be determined from the eigenvalues of Q1 and the above lemma Q1 P2 has eigenvalues ill Qn has eigenvalues n7 2239 with multiplicity for 0 S i S n Regular graphs The degree of a vertex v in G is the number of edges incident to vi If all degrees are equal to d then G is called a d regular graphi Let 1 be the column vector of all entries equal to 1 If G is a regular graph then A1 dli Hence 1 is an eigenvector for the eigenvalue di Eigenvalues of Kn Let J 1 1 be the n X nrnatrix with all entries 1 Since J is a rank 1 matrix J has eigenvalues 0 with multiplicity n 7 1 It is easy to see that the nonzero eigenvalue of J is n The complete graph Kn has the adjacency matrix J 7 I T us Kn has an eigenvalue n 7 l of multiplicity l and 7l of multiplicity n 7 ll 0 l 0 0 i i i 0 0 0 l 0 i i i 0 Eigenvalues of On Let Q 0 0 0 1 0 l 0 0 0 Q can be viewed as the adjacency matrix of the directed cycle We have A Q Qi Note that Q I Let A be the eigenvalue of We have A i The eigenvalues of Q are precisely n th root of 1 pk cos 7ilsin forOS kg n7li Note Q Qn li Thus A Q Q has eigenvalues pk WM 7 2mm 7 20042 fork0l2iun7li Let 1 2 M2 2 mun be the eigenvalues of the adjacency matrix of a graph G We refer M1 Mmax and Mn Mmini We have Mm sup z Az llTll1 Mmin inf z Az HTH1 Suppose I Az reaches the maximum at a on the unit sphere Then all coordinates of a are nonnegativei Lemma 2 IfH is a subgmph of G then we have MmaxG 2 MmaxH Proof Without loss of generality we assume VH VGi Otherwise we add some isolated vertices to Hi It doesn7t change the maximum eigenvalue of Let a be the eigenvector AH corresponding to MmaxHi We have maxH OAHOt 2 Z 01in ijEEH S 2 Z 04in ijeEG oAga S sup zAgz llTll1 maXG Let 6 be the minimum degree and A be the maximum degree of Cl We have the following bound on Mmaxi Lemma 3 For every graph G we have 59 S MmaxG S NC Proof Let a be an eigenvector for eigenvalue M MmaxGi Since a f 0 we can assume a has at least one positive coordinatei If all coordinates are nonepositive we consider 7a insteadi Let 04k maxi ai be the largest coordinate of 1 Since Aa Ma we have ak Aak Zai S Aaki iwk Thus M S A Now we show MmaXG Z 66 MW sup z Aaz HOEHI 1 1 7114 71 7 CW 1 22 W 21EGl 667 1 V D A kcoloring of a graph G is a map 0 VG A k 1727111716 A k coloring is said to be proper if the end vertices of any edge in G receive different colors e7 Cu Cv for any u N vi In this case7 we say G is kcolorablei The chromatic number denoted by xG is the minimum integer k such that G is kcolorablei For example7 xKn ni xG 2 if and only if G is a nonempty bipartite graph There is a simple bound on xGi Theorem 1 For every G7 MG g 1 AG Proof Given any order v17 v27 1 i i 7 1177 we color vertices one by one using A 1 colors At time i7 we assume U171 i i 7 151 has been colored properlyi Note that v7 has at most A neighbors in v17 1 i i 7 117711 We can pickup a distinct color for v7 other than those neighbors received The resulted coloring is a proper coloringi Theorem 2 Wilf 1967 For every G7 MG g 1 AmaxG Proof In the proof of the previous lemma7 the graph G is kcolorable if vi has at most k 7 1 neighbors in the induced subgraph on 11171127111715 or all i1727iu7ni Since the order of the vertices can be arbitrary7 we choose vn to be the vertex having the minimum degree or i n7 n 7 17 i i i 7 17 let vi be the vertex having minimum degree in the induced subgraph Gl on v17 v27 1 i i 7 vii Note 6Gi S MmaxGi S Mmax 01 Thus7 under this order7 the previous greedy algorithm results a proper kcoloring for any k S 1 MmaxGi D Remark Brook s theorem states that if G is a simple connected graph other than the complete graph and odd cycles then MG S NC It is unknown Whether similar result can be proved using nmax G insteadi Assume 1 gt 2 gt gt muk are distinct eigenvalues of Al The 1111 7 Mk is called the minimal polynomial of A We have MA 0 Any polynomial With 0 is divisible by or any pair of vertices u7 v the distance du7 v is the shortest length of any uvpathi The diameter of graph G is the maximum distance among all pairs of vertices Which belongs to the same connected component Theorem 3 The diameter of a graph is less than its number of distinct eigen va ues Proof Without loss of generality7 we can assume G is connected Let k be the number of distinct eigenvalues The minimum polynomial has degree k Since 07 Ak can be expressed as a linear combination of 1 A7 i i i 7 A Suppose the diameter of G is greater than or equal to h There exists a pair of vertices u and v satisfying duv h We have Akw 2 1 and Aiw 0 for i 0127Hi7A 1 This is a contradiction to the fact Ak is a linear combination of I 147m7 Ak li D This result is tight for the hypercube Math 7788 Spectral Graph Theory Handout 4 Laplacian Eigenvalues and Graph Projection A weighted graph G has a weight function wEG A 07ooi It can be extended to w VG gtlt VG A R so that for any uv g EG7 then uu7 v 0 The adjacency matrix of a weighted graph is simply the weight matrix liei A W The degree du of a vertex u is du Ev wwi Let T be the diagonal matrix of degrees The Laplacian matrix is de ned as r If T AT i Let g be an eigenvector of L for an eigenvalue A Then TlQg is an eigenvector of T lA for the eigenvalue 1 7 Al liei7 for any u E lCv397 Zgwunaiah U du Suppose G and H are two weighted graphsi A projection is an onto map 7r VG A VH satisfying 2 wfy 1051 for any uv E zewlm y ir l i A projection 7r G A H is called regular7 if for any 1112 6 VG and any 1 E VH the sum 2 way Z Wang if 11 I2l y7ryv y7ryv Lemma 1 If the graph projection 7TZG A H is regular then any Laplacian eigenvalue of H is a Laplacian eigenvalue of G Proof Suppose A is an eigenvalue of Hi There exists a harmonic function f VH A R satisfying for any u E 1 gw nath v6VH Now we extend f to f VG A R fr fmcy We would like to show f is the harmonic function Lg We have for any I E VG letting u 7rz we have 1 G 1 G diwxyfy Z Z i707ny y6VG 7 v6VHy7ryv 7 G Z Ey7ryv wxyf dag v v6VH H w 7 Z W fv v6VH 1 Afu 1 Mfgp D Example 1 Let G Kgi Identifying two vertices together we get a projection fromGto Hi Here A 7 0 2 H 2 2 H has degree 2 and 4 We have the Laplacian matrix 1 LH g 1 i 2 2 detI7 EH A 71 7 7 g MA 7 H has Laplacian eigenvalues 0 and Note C has Laplacian eigenvalues 0 g The set of all Laplacian eigenvalues of H is a subset of all Laplacian eigenvalues of Cl Example 2 Let Pk12 be the weighed graph by assigning each edge of Pk1 a weight 2 Pk12 and Pk1 have the same set of Laplacian eigenvaluesi There is a regular projection from 02k 7 Pk1 We conclude that Lapla cian eigenvalues of Pk1 are Laplacian eigenvalues of C219 Example 3 If the projection is not regular then the lemma may not hold For example there is a projection from 2P2 7 P3 by identifying two vertices into one vertex The Laplacian eigenvalues of P3 is 01 2 while the Laplacian eigenvalues of 2P2 is 0 0 2 2 Note Lemma 2 IfTr G 7gt H is a projection then AG S AHi Proof Let f be the harmonic function for AHi For any u E VH we have 1 Euevm dfffu 0i 7 2 H 2 AH Eu fduf wwr Now we extend f to f VG A R f1 fmcy In general fis not a harmonic function of Cr However7 we have 2 dffx Z dffu0r 6VG u6VH We have 2 G AG S 2M9 if wmy Ex dgfx 7 mm 7 fv Zw Eu dfffu AHr oh thdt dssoeddtes wtth edeh edge two u rttc s edlled dts ehdpodhts Example 1 For the yrobl m of the Konzgsb ry Bmdges ohe edh de he the graph ds follows V rttc s am ldhdmdsses whdle edges me lmdges We hdoe we mew EG 5152535455Ee57 e1 lt w e2 e w e Es lt t w z 54 lt t w z 5 lt w 11 Ea lt t I y 57 H 9 3 De nition 2 A loop ts dh edge whose ehdpodhts am the some Multlple edges me edges thdthdoe the mm ymr ofehdpodhts Aslnnple graph ts d gmph wdthodt loops or multdple ges For a simple graph7 an edge e is uniquely represented by its endpoints u and vi In this case7 we Write e uv or e vu 7 and we say u and v are adjacent u is a neighbor of v7 and Vice versai An edge e is incident to u and v A simple graph G on n vertices can have at most edges The simple graph With n vertices and edges is called the complete graph7 denoted by Kni The simple graph G on n vertices With 0 edge is called the empty graph The graph With 0 vertices and 0 edges is called the null graphi A 5 6 Figure 3 Complete graphs K3 K4 K57 and K5 A cycle on n vertices7 Written On7 is a graph With vertex set VG 1237 i i i 7n and edge set EG 12237 347Hi7n7 ln7 n1 900 5 6 Figure 4 Cycles C3 C47 C57 and C5 A path on n vertices7 Written Pn7 is a graph With vertex set VG 1237 i i i 7n and edge set EG 12237 347 i i in 7 De nition 3 The complement G of a simple graph G is the simple graph with vertex set VG VG and edge set EG de ned by uv E EG and only if uv g A clique in a graph is a set of pairwise adjacent vertices An independent set in a graph is a set of pairwise nonadjacent vertices De nition 4 A graph G is bipartite if VG is the union of two disjoint inde pendent sets called par tite sets of G De nition 5 A graph is kpartite VG can be expressed as the union of k independent sets De nition 6 The chromatic number of a graph G written xG is the mini mum number k such that G is kpartite A subgraph of a graph G is a graph H such that VH C VG and C We says G contains H A induced subgraph of a graph G is a subgraph H satisfying uv uv E VHuv E Example 2 Let G1 be the simple graph de ned by see Figure 5 VGl 172737475 EGl 122313243445 2 1 4 5 3 Figure 5 A simple graph G1 12 3 is a clique 1 4 is an independent set G1 is not a bipartite graph The chromatic number is xG1 3 2 2 1 4 1 4 3 3 Figure 6 A subgraph of G1 Figure 7 A induced subgraph of G1 An isomorphism from a simple graph G to a simple graph H is a bijection f VG A VH satisfying uv E EG iff E We say G is isomorphic to H7 denoted G E H The isomorphism relation is an equivalence relation Le7 it is l re exive A E A 2 symmetric if A 2 B7 then B E A 3 transitive if A E B and B 2 C7 then A E C An isomorphism class of graphs is an equivalence class of graphs under the isomorphism relation It is also known as an unlabeled graph De nition 7 The adjacency matrix of a graph G written AG is the nbyn matrix in which entry aij is the number of edges with endpoints vi7 vj in G Here VG v17v27 7 vn is the vertex set of G For a simple graph G we have 146 1 1f vivj 1s an edge 0 otherwise AG is a symmetric 01 matrix with Us on the diagonal For a vertex v of the graph G the degree do is the number of edges which are incident to v If v vi then dvl is the ith rowcolumn sum of AG Example 3 For graph G1 Figure 5 the adjacency matrix is given by 0 l l 0 0 l 0 l l 0 A l l 0 l 0 0 l l 0 l 0 0 0 l 0 De nition 8 A walk on a graph G is a list v07e17v17e17 ek vk satisfying ei vi71vi is an edge for all i 12 7k k is called the length of the walk A u7vwalk is a walk with v0 u and vk v A trail is a walk with no repeated edge A path is a walk with no repeated vertices A closed walk is a walk with the same endpoints ie v0 vk A cycle is a closed walk with no repeated vertices except for the endpoints Lemma 1 Every u7 vwalk contains a u7vpath Proof We prove it by induction on the length k of the walk When l a uvwalk is a uvpat i We assume that every uvwalk with length at most k contains a uvpathi Now let us consider a uvwalk u v0e1v1e1i i iek1vk1 v of length k 1 If the walk has no repeated vertices it is a uvpath by de nition Otherwise say vi vj for 0 S i lt j S k 1 By deleting all vertices and edges between vi and v we get a new walk vow 11139 v1 vkarli This walk has length at most kl By the inductive hypothesis it contains a u vpathi Di De nition 9 A graph G is connected it has a u vpath for any uv E VG For any u v we de ne a connected relation u N 1 over VG if there is a u v path in G The connected relation is an equivalence relation The equivalence classes for this relation are called connected components of Cl component is trivial if it contains only one vertex A trivial component is also called an isolated vertexi Lemma 2 Every closed odd walk contains an odd cycle Proof We prove it by induction on the length k of the closed walk When Is l the walk of length 1 is a loop Thus it is an odd cycle We assume that every odd walk with length at most k 2r71 contains a u v pathi Now let us consider a closed walk u v0 e1v1e1 i i i e2T1 v2T1 v of length 2r 1 If the walk has no repeated vertices it is an odd cycle by de nition Otherwise say vi vj for 0 S i lt j S 2r 1 The walk can be split into two closed walks v07m7vz vjwka vii ei1iuvji One of them must have odd length of at most 2r71i By the inductive hypothesis it contains an odd cyc e The proof is nished Di Theorem 1 Konig 1936 A graph is bipartite if and only if it has no odd cycle Proof It is suf cient to prove this for any connected graph Necessity Let G be bipartite graph Every walk of G alternates between the two sets of a bipartitioni The lengths of any closed walks are even Therefore it has no odd cyclei Su ciency Let G be a graph with no odd cycle We will construct a bipartition as follows Choose any vertex a We de ne a partition VG XUY as follows X v E VGl there is a u vpath of odd lengthi Y v E VGl there is a uvpath of even lengthi Since G is connected we have X U Y VGi We will show X N Y 0 Otherwise let u E X N Yr There are two uvpathsi One path has even length while the other one has odd length Put them together We have an odd closed walki By lemma G has an odd cycle Contradiction Therefore VG X UY is a partition Next we will show there are no edges with both ends in X or Yr Otherwise suppose that vw is such an edge The u vpath the edge vw and the w upath together form an odd closed walki By previous lemma G contains an odd cyclei Contradiction Hence G is a bipartite graph D A complete bipartite graph K5 has a vertex set partition V X U Y with le s and lYl t and an edge set EG zy l I E Xy 6 Yr Theorem 2 Let A1 2 A2 2 n be the eigenvalues of the adjacency matiix of a simple graph G The the following statements are equivalent 1 G is a bipartite graph 2 For all 1 S i S n An17i 7 Proof Suppose G is a bipartite graph Then there exists a vertex set partition V X U Yr Reorder vertices so that the vertices in X are before the vertices in Yr The adjacency matrix A has the following shape 0 B A7ltB 0 gt be an eigenvector corresponding to an eigenvalue A Since 6 Leta Aa Aa we have B7 AB B Aai Let i lt 737 gt Then we have lt3 5M 2 lt3 This shows 7A is also an eigenvalue of Al The eigenvalues are symmetric about Suppose Ai 7An14 for all 2quot We have trA2k1 EA 0A i1 The number of odd Closed walks is 0 G has no odd cyclel Thus G is bipartite by Konig s theoreml

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I made $350 in just two days after posting my first study guide."

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.