Polynomial invariant and reciprocity theorem on the Hopf monoid of hypergraphs

(1)

Polynomial invariant and reciprocity theorem on the Hopf monoid of hypergraphs

Theo Karaboghossian,

Jean-Christophe Aval, Adrian Tanasa arXiv:1806.08546v2

Bordeaux

April 16, 2019

(2)

Species

(Joyal) A species P is given by the data of:

for each finite set I, a vector space P[I], for each bijectionσ :I →J, a linear map

P[σ] :P[I]→P[J], such that

P[τ◦σ] =P[τ]◦P[σ]andP[id] = id.

Ex: G[I]= Vect({graphs over I}), G[σ]relabeling

(5)

Species

(Joyal) A species P is given by the data of:

for each finite set I, a vector space P[I], for each bijectionσ :I →J, a linear map

P[σ] :P[I]→P[J], such that

P[τ◦σ] =P[τ]◦P[σ]andP[id] = id.

Ex: G[I]= Vect({graphs over I}), G[σ]relabeling

(6)

Hopf monoid

(Aguiar-Mahajan) A Hopf monoid is a species M with, for eachI =StT, a productµS,T :M[S]⊗M[T]→M[I],

a co-product∆S,T :M[I]→M[S]⊗M[T].

Co-associativity:

P[RtStT]

P[R tS]⊗P[T] P[R]⊗P[StT]

P[R]⊗P[S]⊗P[T]

∆RtS,T ∆R,StT

∆R,S⊗id id⊗∆_S,T

(7)

Hopf monoid

Co-associativity:

P[RtStT]

P[R]⊗P[S]⊗P[T]

∆RtS,T ∆R,StT

(8)

Hopf monoid

Co-associativity:

P[RtStT]

P[R]⊗P[S]⊗P[T]

∆RtS,T ∆R,StT

∆R,S,T

(9)

Hopf monoid of graphs

µ_S,T :G[S]⊗G[T]→G[I] ∆_S,T :G[I]→G[S]⊗G[T] g₁⊗g₂ 7→g₁tg₂ g 7→g_|S ⊗g_/S, where g_|S is the sub-graph of g induced by S andg_/S =g_|T.

Ex: ForS ={1,2,3}andT ={a,b}:

1 a

2 b 3 2

3 1

⊗

a b

∆S,T

(10)

Hopf monoid of graphs

µ_S,T :G[S]⊗G[T]→G[I] ∆_S,T :G[I]→G[S]⊗G[T] g₁⊗g₂ 7→g₁tg₂ g 7→g_|S ⊗g_/S, where g_|S is the sub-graph of g induced by S andg_/S =g_|T.

Ex: ForS ={1,2,3}andT ={a,b}:

1 a

2 b 3 2

3 1

⊗

a b

∆S,T

(11)

Character

A Hopf monoid characterζ :M →k is a collection of linear forms ζ_I :M[I]→k

such that for every I =StT:

M[S]⊗M[T] M[I]

k⊗k k

ζS⊗ζ_T µS,T

ζI

∼=

Ex: Forg ∈G[I] ζ_I(g) =

1 if g is discrete (i.e has no edges) 0 if not

(12)

Character

A Hopf monoid characterζ :M →k is a collection of linear forms ζ_I :M[I]→k

such that for every I =StT:

M[S]⊗M[T] M[I]

k⊗k k

ζS⊗ζ_T µS,T

ζI

∼=

Ex: Forg ∈G[I] ζI(g) =

1 if g is discrete (i.e has no edges) 0 if not

(13)

Polynomial invariant

A decomposition ofI,(S₁, . . . ,S_n)`I is a sequence of disjoint sets of I such that F

S_i =I. We note`(S) the number of elements ofS.

Theorem (Aguiar and Ardila)

Let M be a Hopf monoid, ζ a character,n an integer andx ∈M[I]. Then χ_I(x)(n) = X

S`I,`(S)=n

ζ_S₁⊗ · · · ⊗ζ_S_n ◦∆_S₁_,...,S_n(x)

is a polynomial in n such that χ(xy) =χ(x)χ(y) andχI(x)(1) =ζI(x).

Ex: With the preceding character, forg a graph, χI(g) is the chromatic polynomial ofg.

(14)

Polynomial invariant

S`I,`(S)=n

ζ_S₁⊗ · · · ⊗ζ_S_n ◦∆_S₁_,...,S_n(x)

(15)

Polynomial invariant

S`I,`(S)=n

ζ_S₁⊗ · · · ⊗ζ_S_n ◦∆_S₁_,...,S_n(x)

(16)

Polynomial invariant

Ex: I = [3],G = ₁ ₂ ₃ andn=2:

∆_{123},∅(G) =G⊗ ∅ ^ζ^{123}^⊗ζ^∅ 0⊗1=0

∆_{12},{3}(G) = ₁ ₂ ⊗ ₃ ^ζ^{12}^⊗ζ^{3} 0⊗1=0

∆_{13},{2}(G) = ₁ ₃ ⊗ ₂ ^ζ^{13}^⊗ζ^{2} 1⊗1=1

∆_{23},{1}(G) = ₂ ₃ ⊗ ₁ ^ζ^{23}^⊗ζ^{1} 1⊗0=0

· · ·+1

1 2 3 1 2 3

(17)

Polynomial invariant

Ex: I = [3],G = ₁ ₂ ₃ andn=2:

∆_{123},∅(G) =G⊗ ∅ ^ζ^{123}^⊗ζ^∅ 0⊗1=0

∆{12},{3}(G) = ₁ ₂ ⊗ ₃ ^ζ^{12}^⊗ζ^{3} 0⊗1=0

∆_{13},{2}(G) = ₁ ₃ ⊗ ₂ ^ζ^{13}^⊗ζ^{2} 1⊗1=1

∆_{23},{1}(G) = ₂ ₃ ⊗ ₁ ^ζ^{23}^⊗ζ^{1} 1⊗0=0

· · ·+1

1 2 3 1 2 3

(18)

Polynomial invariant

Ex: I = [3],G = ₁ ₂ ₃ andn=2:

∆_{123},∅(G) =G⊗ ∅ ^ζ^{123}^⊗ζ^∅ 0⊗1=0

∆{12},{3}(G) = ₁ ₂ ⊗ ₃ ^ζ^{12}^⊗ζ^{3} 0⊗1=0

∆_{13},{2}(G) = ₁ ₃ ⊗ ₂ ^ζ^{13}^⊗ζ^{2} 1⊗1=1

∆_{23},{1}(G) = ₂ ₃ ⊗ ₁ ^ζ^{23}^⊗ζ^{1} 1⊗0=0

· · ·+1

1 2 3 1 2 3

(19)

Polynomial invariant

Ex: I = [3],G = ₁ ₂ ₃ andn=2:

∆_{123},∅(G) =G⊗ ∅ ^ζ^{123}^⊗ζ^∅ 0⊗1=0

∆{12},{3}(G) = ₁ ₂ ⊗ ₃ ^ζ^{12}^⊗ζ^{3} 0⊗1=0

∆_{13},{2}(G) = ₁ ₃ ⊗ ₂ ^ζ^{13}^⊗ζ^{2} 1⊗1=1

∆_{23},{1}(G) = ₂ ₃ ⊗ ₁ ^ζ^{23}^⊗ζ^{1} 1⊗0=0

· · ·+1

1 2 3 1 2 3

(20)

Hypergraphs

Hypergraph over I: collection of sub-sets ofI called edges.

HG[I]=Vect({hypergraphs overI})

Ex:

{{1,2,3},{2,3,4}} ∈HG[[5]]

1 2 3

4 5

(22)

Hypergraphs

Hopf monoid structure:

µS,T :HG[S]⊗HG[T]→HG[I] ∆S,T :HG[I]→HG[S]⊗HG[T] H₁⊗H₂ 7→H₁tH₂ H 7→H_|S ⊗H_/S

H_|S ={e ∈H|e ⊆S}restriction of H toS

H_/S ={e∩T|e *S} ∪ {∅}contraction of S inH

Ex: ForS ={1,2,5}T ={3,4},

1 2 3

4 5

1 2

5

⊗ ³ ⁴

∆S,T

(23)

Hypergraphs

Hopf monoid structure:

µS,T :HG[S]⊗HG[T]→HG[I] ∆S,T :HG[I]→HG[S]⊗HG[T] H₁⊗H₂ 7→H₁tH₂ H 7→H_|S ⊗H_/S

H_|S ={e ∈H|e ⊆S}restriction of H toS

H_/S ={e∩T|e *S} ∪ {∅}contraction of S inH Ex: ForS ={1,2,5}T ={3,4},

1 2 3

4 5

1 2

5

⊗ ³ ⁴

∆S,T

(24)

Hypergraphs

Character:

ζ_I(H) =

1 if H doesn’t have edges with cardinality greater than one 0 else

χ =?

H ∈HG[I]

(25)

Hypergraphs

Character:

ζ_I(H) =

1 if H doesn’t have edges with cardinality greater than one 0 else

χ =?

H ∈HG[I]

(26)

Colorings

Definition (Coloring)

Acoloring of H with [n]is a function c :I →[n].

Lete ∈H. Thenv ∈e ismaximal ine (forc) ifv is of maximal color ine.

Ex: Coloring with {1,2,3,4}.

e3

e4 e2

a b

e1 c

d

e f

a maximal ine₁,c in e₂,c andd ine₃.

(28)

Colorings

Definition (Coloring)

Acoloring of H with [n]is a function c :I →[n].

Lete ∈H. Thenv ∈e ismaximal ine (forc) ifv is of maximal color ine.

Ex: Coloring with {1,2,3,4}.

e3

e4 e2

a b

e1 c

d

e f

a maximal ine₁,c in e₂,c andd ine₃.

(29)

Polynomial invariant

Theorem

Let I be a set andH ∈HG[I]a hypergraph overI.

Then χ_I(H)(n) is the number of colorings ofH with[n]such that each edge has only one maximal vertex.

Ex:

(30)

Polynomial invariant

Theorem

Then χI(H)(n) is the number of colorings ofH with[n]such that each edge has only one maximal vertex.

Ex: χI(H)(n) =n⁴−⁸₃n³+⁵₂n²−⁵₆n

1 2 3

4

(31)

Polynomial invariant

Theorem

Ex: forn=2: χI(H)(2) =2⁴−⁸₃2³+⁵₂2²−⁵₆2=3

1 2 3

4

(32)

Polynomial invariant

Theorem

Ex: forn=2: χI(H)(2) =2⁴−⁸₃2³+⁵₂2²−⁵₆2=3

1 2 3

4

(33)

Polynomial invariant

Theorem

Ex: forn=2: χI(H)(2) =2⁴−⁸₃2³+⁵₂2²−⁵₆2=3

1 2 3

4

(34)

Polynomial invariant

Theorem

Ex: forn=2: χI(H)(2) =2⁴−⁸₃2³+⁵₂2²−⁵₆2=3

1 2 3

4

(35)

Orientations

Definition (Orientation)

An orientation of H is a functionf :H →I such that f(e)∈e for all e ∈H.

Acycle in f is a sequencee₁, . . . ,e_k of edges such that f(e₁)∈e₂\f(e₂), . . . ,f(e_k)∈e₁\f(e₁).

We note A_H the set of acyclic orientations of H.

Ex:

1 2 3

4 5

e1 e3

e2

The orientationf(e₁) =5,f(e₂) =2,f(e₃) =3 is cyclic. The orientationf(e₁) =1,f(e₂) =1,f(e₃) =3 is acyclic.

(37)

Orientations

Definition (Orientation)

An orientation of H is a functionf :H →I such that f(e)∈e for all e ∈H.

Acycle in f is a sequencee₁, . . . ,e_k of edges such that f(e₁)∈e₂\f(e₂), . . . ,f(e_k)∈e₁\f(e₁).

We note A_H the set of acyclic orientations of H.

Ex:

1 2 3

4 5

e1 e3

e2

The orientationf(e₁) =5,f(e₂) =2,f(e₃) =3 is cyclic.

(38)

Reciprocity theorem

Theorem

Let I be a set andH ∈HG[I]be a hypergraph over I.

Then (−1)^|I|χ_I(H)(−1) =|A_H|is the number of acyclic orientations of H.

Ex:

1 2 3

4

e1 e2

(39)

Reciprocity theorem

Theorem

Ex: χ_I(H)(n) =n⁴−⁸₃n³+⁵₂n²−⁵₆n

1 2 3

4

e1 e2

(40)

Reciprocity theorem

Theorem

Then (−1)^|I|χI(H)(−1) =|A_H|is the number of acyclic orientations of H.

Ex: χI(H)(−1) =1+⁸₃ +⁵₂ +⁵₆ =7

1 2 3

4

e1 e2

3·3=9 orientations minus 2 cyclic orientations.

(41)

Reciprocity theorem

Theorem

Ex: χ_I(H)(−1) =1+⁸₃ +⁵₂ +⁵₆ =7

1 2 3

4

e1 e2

3·3=9 orientations minus 2 cyclic orientations.

Remark: There is a combinatorial interpretation of(−1)^|I|χ_I(H)(−n).

(42)

Graphs

Reminder:

µS,T :G[S]⊗G[T]→G[I] ∆S,T :G[I]→G[S]⊗G[T] g₁⊗g₂ 7→g₁tg₂ g 7→g_|S ⊗g_|T,

Theorem

Let g ∈G[I]. Then χ^G_I (g) is the chromatic polynomial ofg. Furthermore (−1)^|I^|χ^G_I (g)(−1)is the number of acyclic orientations ofg.

proof:

Only one maximal vertex ⇐⇒ neighbour vertex of different colors.

(44)

Graphs

Reminder:

Theorem

Let g ∈G[I]. Then χ^G_I (g) is the chromatic polynomial ofg. Furthermore (−1)^|I|χ^G_I (g)(−1) is the number of acyclic orientations ofg.

proof:

(45)

Graphs

Reminder:

Theorem

Let g ∈G[I]. Then χ^G_I (g) is the chromatic polynomial ofg. Furthermore (−1)^|I|χ^G_I (g)(−1) is the number of acyclic orientations ofg.

proof:

(46)

Simplicial complexes (Benedetti, Hallam, Machacek)

A simplicial complex over I is a set of parts S ofI such that

K ⊂J ∈S ⇒K ∈S. We noteSC the species of simplicial complexes.

The 1-skeleton of simplicial complex is the graph formed by its parts of cardinality 2.

Theorem

SC is a Hopf sub-monoid ofHG. Let be C ∈SC[I]andg be its 1-skeleton. Thenχ^SC_I (C) =χ^G_I (g).

(47)

Simplicial complexes (Benedetti, Hallam, Machacek)

A simplicial complex over I is a set of parts S ofI such that

K ⊂J ∈S ⇒K ∈S. We noteSC the species of simplicial complexes.

The 1-skeleton of simplicial complex is the graph formed by its parts of cardinality 2.

Theorem

SC is a Hopf sub-monoid ofHG. Let be C ∈SC[I]andg be its 1-skeleton. Thenχ^SC_I (C) =χ^G_I (g).

(48)

Set of paths (Aguiar and Ardila)

A path over I is a word overI quotiented by the relation

w1. . .w_|I|∼w_|I|. . .w1. A set of pathss1|. . .|s_` overI is a partition of I in paths.

The species F of sets of paths is a Hopf monoid: µS,T :F[S]⊗F[T]→F[I]

s₁|. . .|s_`⊗t₁|. . .|t_`⁰ 7→s₁|. . .|s_`|t₁|. . .|t_`⁰

∆_S,T :F[I]→F[S]⊗F[T]

s₁|. . .|s_` 7→s₁∩S|. . .|s_`∩S⊗s₁_S←||. . .|s_`S_←|

Ex: ForI ={a,b,c,d,e,f,g}andS ={b,c,e} andT ={a,d,f,g} we have :

∆_S,T(bfc|g|aed) =bc|e⊗f|g|a|d

(49)

Set of paths (Aguiar and Ardila)

The species F of sets of paths is a Hopf monoid:

µS,T :F[S]⊗F[T]→F[I]

s₁|. . .|s_`⊗t₁|. . .|t_`⁰ 7→s₁|. . .|s_`|t₁|. . .|t_`⁰

∆_S,T :F[I]→F[S]⊗F[T]

s₁|. . .|s_` 7→s₁∩S|. . .|s_`∩S⊗s₁_S←||. . .|s_`S_←|

(50)

Set of paths (Aguiar and Ardila)

The species F of sets of paths is a Hopf monoid:

µS,T :F[S]⊗F[T]→F[I]

s₁|. . .|s_`⊗t₁|. . .|t_`⁰ 7→s₁|. . .|s_`|t₁|. . .|t_`⁰

∆_S,T :F[I]→F[S]⊗F[T]

s₁|. . .|s_` 7→s₁∩S|. . .|s_`∩S⊗s₁_S←||. . .|s_`S_←|

(51)

Set of paths (Aguiar and Ardila)

Theorem

Letα be a path overI. χ^F_I(α)(n)is the number of rooted binary trees with

|I|vertices and colored with [n]such that the color of a vertex is strictly greater than the color of its children.

Furthermore (−1)^|I|χ^F_I (α)(−1) =C_|I|with (C_k)k∈Nthe Catalan number sequence.

(52)

Perspectives

Generalisation to all characters on HG.

Antipode S :M →M such that:

χI(x)(−n) =χI(S(x))(n)

Open question: find a (nice) proof of reciprocity theorems using the antipode.

(53)

Perspectives

Generalisation to all characters on HG.

AntipodeS :M →M such that:

χI(x)(−n) =χI(S(x))(n)

Open question: find a (nice) proof of reciprocity theorems using the antipode.

(54)

Thank you for your attention.

arXiv:1806.08546v2

Polynomial invariant and reciprocity theorem on the Hopf monoid of hypergraphs

Polynomial invariant and reciprocity theorem on the Hopf monoid of hypergraphs

Table of contents

Table of contents

Species

Species

Hopf monoid

Hopf monoid

Hopf monoid

Hopf monoid of graphs

Hopf monoid of graphs

Character

Character

Polynomial invariant

Polynomial invariant

Polynomial invariant

Polynomial invariant

Polynomial invariant

Polynomial invariant

Polynomial invariant

Table of contents

Hypergraphs

Hypergraphs

Hypergraphs

Hypergraphs

χ =?

Hypergraphs

χ =?

Table of contents

Colorings

Colorings

Polynomial invariant

Polynomial invariant

Polynomial invariant

Polynomial invariant

Polynomial invariant

Polynomial invariant

Table of contents

Orientations

Orientations

Reciprocity theorem

Reciprocity theorem

Reciprocity theorem

Reciprocity theorem

Table of contents

Graphs

Graphs

Graphs

Simplicial complexes (Benedetti, Hallam, Machacek)

Simplicial complexes (Benedetti, Hallam, Machacek)

Set of paths (Aguiar and Ardila)

Set of paths (Aguiar and Ardila)

Set of paths (Aguiar and Ardila)

Set of paths (Aguiar and Ardila)

Perspectives

Perspectives

Thank you for your attention.