조합 및 행렬이론 시험대비

Chapter 1 What is CMT?

*Def

walk

path(walk와의 차이는 distinct vertices)

connected graph

matching, k-matching, matching number

vertex-cover, cover number

K_n, complete graph

K_no, complete graph with all loops

K_n*, complete digraph with all loops

G(MT), called the Konig digraph

IcMT(configuration of X)

MT(nxn):reducible or irreducible

nnn irreducible중에서

primitive MT

the exponent of primitive MT?

imprimitive MT, 이경우 index of imprimitivity 정의
G1,G2:cospectral if spec(A(G))=spec(A(G'))

IcMT(G), (1,0) matrix

*Thm

Principal tools of Combinatorics

-Mathematical Induction

-Pigeonhole Principle

-Inclusion-Exclusion Principle

-The methods of recurrence relations and generating functions

-Graph Theory

-Burnside's Theorem

-Polya Enumeration Theorem

각각 내용 알기, 특히 Exponential Generating Functions관련해서 내용정리 추가 필요

Tree의 equivalent def

-connected acyclic

-for distinct u,v in V(G), te! path from u to v

-connected with n-1 edges

-connected and removing any edge makes G disconnected

G:bipartite이면 cover number = matching number

From Matrix to graph

no need square(invariant for PAQ, like rank)

MT(mxn) -> K_(m,n)의 subgraph, ker(MT), bar(ker(MT)), bar(ker(MT))의 경우 weigted로도 볼 수 있는데 그 경우 bar(ker(MT))에서 0는 no edge로 보면 됨

MT(mxn) -> G(MT), K_(m,n)의 digraph 형태, weight있는 경우

MT(nxn)의 경우 그냥 G(MT)보고 det(MT)를 wt(all 1-factors)로 묘사가능

square(invariant for PArt(P), like egv)

SMT(nxn) -> K_no의 subgraph, ket(MT), bar(ker(MT)), weighted로도 볼 수 있음, bar(ker(MT))에서 0는 no edge로 보면 됨

MT(nxn) -> K_n*의 subgraph, ker(MT), bar(ker(MT)), weighted로도 볼 수 있음, bar(ker(MT))에서 0는 no edge로 보면 됨

From (di)graph to matrix

(1,0)-A(G)

arc가 있냐 없냐로 1,0

det(A(G))=(-1)^n * wt(D_n),

where D_n:={all 1-factor of σ, σ in S_n},

wt(D_n)=sum over all σ wt(F_σ),

wt(F_σ)=sign(σ) * prod over all i=1 to i=n a_(i,σ(i))

따라서 (di)graph의 형태를 보고 det구할 수 있다. cycles

A(G)^k의 (i,j)원소의 의미는 the number of walks of length k from i to j

IcMT(G)

rt(IcMT(G))*IcMT(G) = sLap(G)

det, perm using IcMT

det(MT(nxn))=W^1 W^2 ... W^n, W^i:(n choose i-1)x(n choose i) using (i+1)th row element in MT

perm(MT(nxn))=W^1 W^2 ... W^n, W^i:(n choose i-1)x(n choose i) using (i+1)th row element in MT

Perron Theorem for positive MT

About irreducible

MT:irreducible

iff G(MT):strongly connected, (G(MT):K_n*의 subgraph, unweighted directed)

About primitive MT

the index of imprimitive = gcd(the lengths of all directed cycles in G(MT))

MT:primitive

iff lim m->inf (MT/specR(MT))^m exists, the limit = (p*rt(q))/(rt(q)*p) > 0, where p:perron for MT, q:perron for rt(MT)

iff the index of imprimitive = 1

iff gcd(the lengths of all directed cycles in G(MT)) = 1, (G(MT):K_n*의 subgraph, unweighted directed)

iff MT^m > 0 for some m, called the exponent

Perron-Frobenius Theorem for irreducible NNN MT