Polya's Theory of Counting INEQUALITIES a new aspect of mathematical method G.POLYA G.Hordy.J.E.Limlewood G.Polya Cambridge Mathematical Library George Polya (1887-1985)
Pólya’s Theory of Counting George Pólya (1887-1985)
Counting with Symmetry Rotation Rotation Reflection: 9
Counting with Symmetry Rotation : Rotation & Reflection:
Symmetries
Symmetries
Symmetry rotation reflection 3 8 configuration x [n]>[m] X (m]inl positions colors permutation π：。回
Symmetry 0 1 2 3 4 5 rotation reflection configuration x : [n] ! [m] X = [m] [n] positions colors permutation ⇡ : [n] 1-1 ! on-to [n]
Permutation Groups group(G,·）with binary operator·:GxG→G 。closure:T,o∈G→T·o∈G 。associativity:T·(o·T)=(r·o）·T 。identity:]e∈G,Vπ∈G,e·π=π ●inverse: Vπ∈G,0∈G,π·g=0·π=e -1 0三π commutative (abelian)group: π·0=0·m symmetric group S:all permutations cyclic group Cn:rotations Dihedral group D:rotations reflections
Permutation Groups group (G, ·) with binary operator · : G ⇥ G ! G • closure: • associativity: • identity: • inverse: ⇡, 2 G ) ⇡ · 2 G ⇡ · ( · ⌧ )=(⇡ · ) · ⌧ = ⇡1 8⇡ 2 G, 9 2 G, ⇡ · = · ⇡ = e 9e 2 G, 8⇡ 2 G, e · ⇡ = ⇡ commutative (abelian) group: ⇡ · = · ⇡ symmetric group cyclic group Dihedral group Sn Cn Dn : all permutations : rotations : rotations & reflections
Permutation Groups symmetric group S.:all permutations x:网品网 cyclic group Cn:rotations π=(012.·n-1) π()=(i+1)modn (012.…n-1)》generated by (012…n-1) Dihedral group D.:rotations reflections p(i)=(n-1)-i generated by (012.…n-1)andp
Permutation Groups symmetric group cyclic group Dihedral group Sn Cn Dn : all permutations : rotations : rotations & reflections ⇡ : [n] 1-1 ! on-to [n] h(012 ··· n 1)i generated by (012 ··· n 1) ⇡ = (012 ··· n 1) ⇡(i)=(i + 1) mod n generated by (012 ··· n 1) and ⇢(i)=(n 1) i ⇢
Group Action configuration x [n][m] X (m]ln] permutation 不：回风 group G (πox)(i)=xr(π(i) group action o:GxX→X ·associativity:(π·o)ox=To(gox) ●identity:eox=r
Group Action 0 1 2 3 4 5 0 1 2 3 4 5 configuration x : [n] ! [m] permutation ⇡ : [n] 1-1 ! on-to [n] group action X = [m] [n] group G : G ⇥ X ! X • associativity: • identity: (⇡ · ) x = ⇡ ( x) e x = x (⇡ x)(i) = x(⇡(i))
Graph Isomorphism(Gl)Problem input:two undirected graphs G and H output:GH? n vertices GI is in NP,but is NOT known to be in P or NPC trivial algorithm:O(n!)time Babai-Luks'83:20(vn log) time Babai 2017:a quasi-polynomial time algorithm! mpolylog(n)=2polylog(n)
Graph Isomorphism (GI) Problem ? • GI is in NP, but is NOT known to be in P or NPC • trivial algorithm: O(n!) time • Babai-Luks ’83: time n vertices Babai 2017: a quasi-polynomial time algorithm! npolylog(n) = 2polylog(n) 2O( pn log n) ⇠ = input: two undirected graphs G and H output: G ⇠ = H ?
String Isomorphism (Sl) input:two strings a,y [n]>[m] a permutation group G Sn output:x≥cy?(3o∈Gs.t.oox=y) 芒
input: two strings a permutation group output: String Isomorphism (SI) ⇠ = ? x, y : [n] ! [m] G ✓ Sn x ⇠ =G y? (9 2 G s.t. x = y)
String Isomorphism (Sl) input:two strings x,y [n]->[m] a permutation group G Sn output:x≥cy?(3o∈Gs.t.oox= y) a graph X(V,E)is a string 1:edge 0:no edge positions←→vertex-pairs all permutations on V induces a permutation group on Johnson group:S)CS on vertex pairs two graphsXY iff their string versions )y
String Isomorphism (SI) a graph X(V,E) is a string x : ✓V 2 ◆ ! {0, 1} all permutations on V induces a permutation group on on vertex pairs two graphs X ⇠ = Y iff their string versions x ⇠ =S(2) V y positions ⟷ vertex-pairs 1: edge 0: no edge Johnson group: input: two strings a permutation group output: x, y : [n] ! [m] G ✓ Sn x ⇠ =G y? (9 2 G s.t. x = y) S(2) V ⇢ S( V 2 ) ✓V 2 ◆