Clique complexes of multigraphs
Anton Ayzenberg
ayzenberga@gmail.com
based on joint work with Alexey RukhovichHigher School of Economics and Steklov Mathematical Institute, Moscow

March 25, 2021
Toric Topology in Osaka 2021
Osaka/Zoom

Anton Ayzenberg (HSE, Steklov Institute)

Clique complexes of multigraphs

Osaka, 2021

1 / 26

Plan:

1

Iterative constructions of simplicial complexes: substitutions, vertex inflations.

2

Tournaments in digraphs, cliques in multigraphs, edge inflations of simplicialcomplexes.

3Generalizations and open questions.

Anton Ayzenberg (HSE, Steklov Institute)

Clique complexes of multigraphsOsaka, 2021

2 / 26

Iterated wedge construction

Construction of Bahri–Bendersky–Cohen–Gitler

K : a simplicial complex on vertices rms  t1, . . . , mu;
pj1 , . . . , jm q : an array of positive integers.
Define iterated wedge construction K pj1 , . . . , jm q with
Vertex set J1 \    \ Jm (with |Ji |  ji ).
A1 \    \ Am is a simplex iff ti | Ai  Ji u P K .
Construction has nice properties.

Anton Ayzenberg (HSE, Steklov Institute)

Clique complexes of multigraphsOsaka, 2021

3 / 26

Iterated wedge construction

Construction of Bahri–Bendersky–Cohen–Gitler

K : a simplicial complex on vertices rms  t1, . . . , mu;
pj1 , . . . , jm q : an array of positive integers.
Define iterated wedge construction K pj1 , . . . , jm q with
Vertex set J1 \    \ Jm (with |Ji |  ji ).
A1 \    \ Am is a simplex iff ti | Ai  Ji u P K .
Construction has nice properties.
If K is a sphere then so is K pj1 , . . . , jm q.

Anton Ayzenberg (HSE, Steklov Institute)

Clique complexes of multigraphs

Osaka, 2021

3 / 26

Iterated wedge construction

Construction of Bahri–Bendersky–Cohen–Gitler

K : a simplicial complex on vertices rms  t1, . . . , mu;
pj1 , . . . , jm q : an array of positive integers.
Define iterated wedge construction K pj1 , . . . , jm q with
Vertex set J1 \    \ Jm (with |Ji |  ji ).
A1 \    \ Am is a simplex iff ti | Ai  Ji u P K .
Construction has nice properties.
If K is a sphere then so is K pj1 , . . . , jm q.

If K is a boundary of simplicial polytope then so is K pj1 , . . . , jm q.

Anton Ayzenberg (HSE, Steklov Institute)

Clique complexes of multigraphs

Osaka, 2021

3 / 26

Iterated wedge construction

Construction of Bahri–Bendersky–Cohen–Gitler

K : a simplicial complex on vertices rms  t1, . . . , mu;
pj1 , . . . , jm q : an array of positive integers.
Define iterated wedge construction K pj1 , . . . , jm q withVertex set J1 \    \ Jm (with |Ji |  ji ).
A1 \    \ Am is a simplex iff ti | Ai  Ji u P K .
Construction has nice properties.
If K is a sphere then so is K pj1 , . . . , jm q.

If K is a boundary of simplicial polytope then so is K pj1 , . . . , jm q.

ZK pji q pD 1 , S 0 q  ZK ppD ji , S ji 1 qq, etc.

Anton Ayzenberg (HSE, Steklov Institute)

Clique complexes of multigraphs

Osaka, 2021

3 / 26

Related construction: substitutions of complexes
Construction of thick substitution

K : a simplicial complex on vertices rms  t1, . . . , mu;
pK1 , . . . , Km q : an array of simplicial complexes on vertex sets J1 , . . . , Jm
resp..
Define new complex K pK1 , . . . , Km q with
Vertex set J1 \    \ Jm .
A1 \    \ Am is a simplex iff ti | Ai R Ki u P K .
A6єK6
A1єK1

A2єK2

A7єK7

A8єK8
K(K1,...,K8)

A єK

Anton Ayzenberg (HSE, Steklov Institute)

Clique complexes of multigraphs

Osaka, 2021

4 / 26

Thick substitution

Remark: thick substitution generalizes iterated wedges:
K pj1 , . . . , jm q  K pB ∆j1 1 , . . . , B ∆jm 1 q.

Anton Ayzenberg (HSE, Steklov Institute)

Clique complexes of multigraphs

Osaka, 2021

5 / 26

Thick substitution

Remark: thick substitution generalizes iterated wedges:
K pj1 , . . . , jm q  K pB ∆j1 1 , . . . , B ∆jm 1 q.

Theorem (A.’13)
Thick substitution defines an operad structure on the set of all finite
simplicial complexes.
There is a natural homotopy equivalence|K pK1 , . . . , Km q|  |K |  |K1 |      |Km |.
An operation of substitution of polytopes (by Agnarsson’13) corresponds tothick substitution of simplicial complexes.

Anton Ayzenberg (HSE, Steklov Institute)

Clique complexes of multigraphs

Osaka, 2021

5 / 26

Related construction: substitutions of complexes
Construction of thin substitution

K : a simplicial complex on vertices rms  t1, . . . , mu;
pK1 , . . . , Km q : an array of simplicial complexes on vertex sets J1 , . . . , Jm resp.
Define new complex K rK1 , . . . , Km s with
Vertex set J1 \    \ Jm .
A1 \    \ Am is a simplex iff Ai P Ki and ti | Ai  ∅u P K .

Anton Ayzenberg (HSE, Steklov Institute)

Clique complexes of multigraphs

Osaka, 2021

6 / 26

Thin substitution

Remark: thin substitution was used by Abramyan–Panov’19 to constructnontrivial iterated higher Whitehead products in moment angle complexes.
No general good homotopy properties of K rK1 , . . . , Km s are known.

Anton Ayzenberg (HSE, Steklov Institute)

Clique complexes of multigraphs

Osaka, 2021

7 / 26

Thin substitution

Remark: thin substitution was used by Abramyan–Panov’19 to constructnontrivial iterated higher Whitehead products in moment angle complexes.
No general good homotopy properties of K rK1 , . . . , Km s are known.

Vertex inflations
Let n pt be a simplicial complex of n disjoint points. A particular case of thin
substitution was studied by Björner, Wachs, and Welker. The complex
K rj1 pt, . . . , jm pts is called a vertex inflation of K .

Kx2

Anton Ayzenberg (HSE, Steklov Institute)

K[2,2,1,3]x1x2x3Clique complexes of multigraphs

Osaka, 2021

7 / 26

Vertex inflation
Kx2

K[2,2,1,3]x1x2x3Let J  pj1 , . . . , jm q denote the multiplicities.

Anton Ayzenberg (HSE, Steklov Institute)

Clique complexes of multigraphs

Osaka, 2021

8 / 26

Vertex inflation
K

K[2,2,1,3]x1x2x2x3

Let J  pj1 , . . . , jm q denote the multiplicities.

Theorem (Björner, Wachs, and Welker’05)
12If ∆k is a±simplex, then ∆k rJ s is homotopy equivalent to a wedge ofN pJ q  i pji  1q many spheres S k .
For connected K there is a wedge decomposition|K rJ s|  |K | _ª

PpΣ|I | | linkK I |q_N pJ | q .
II K
3If K is Cohen–Macaulay, then K rJ s is also Cohen–Macaulay.

Item 1
follows easily from two observations ∆k rK1 , . . . , Km s  K1      Km , andj pt  j 1 S 0 .
Anton Ayzenberg (HSE, Steklov Institute)

Clique complexes of multigraphs

Osaka, 2021

8 / 26

Poset fiber theorem
Wedge decomposition (item 2) follows from Poset Fiber Theorem.

Poset fiber theorem of Björner, Wachs, and Welker

Let f : P Ñ Q be a morphism of posets such that for all q P Q the fiber|f 1 pQ¤q q| is dim |f 1 pQ q q|-connected. If |Q | is connected, then there is ahomotopy equivalence|P |  |Q | _ªP|f 1 pQ¤q q|  |Q¡q |.

(1)

q Q

The proof is based on homotopy colimits.

Anton Ayzenberg (HSE, Steklov Institute)

Clique complexes of multigraphs

Osaka, 2021

9 / 26

Poset fiber theorem
Wedge decomposition (item 2) follows from Poset Fiber Theorem.

Poset fiber theorem of Björner, Wachs, and Welker

Let f : P Ñ Q be a morphism of posets such that for all q P Q the fiber|f 1 pQ¤q q| is dim |f 1 pQ q q|-connected. If |Q | is connected, then there is ahomotopy equivalence|P |  |Q | _ªP|f 1 pQ¤q q|  |Q¡q |.

(1)q Q

The proof is based on homotopy colimits.
The application idea: notice that there is a “blow down” map which satisfies
assumptions of PFT:

K[2,2,1,3]

Anton Ayzenberg (HSE, Steklov Institute)K

Clique complexes of multigraphs

Osaka, 2021

9 / 26

Clique (or flag) complex of a graph

G

Anton Ayzenberg (HSE, Steklov Institute)

F.G

Clique complexes of multigraphs

Osaka, 2021

10 / 26

Tournaplex of a digraph

Both dF .Γ and tF .Γ are simplicial posets.

Anton Ayzenberg (HSE, Steklov Institute)

Clique complexes of multigraphs

Osaka, 2021

11 / 26

Tournaplex of a digraph

Both dF .Γ and tF .Γ are simplicial posets.
Introduced and studied in BlueBrain project (Kathryn Hess, Ran Levi, and others).
Used to construct numerical characteristics of brain functional networks.

Anton Ayzenberg (HSE, Steklov Institute)

Clique complexes of multigraphs

Osaka, 2021

11 / 26

Clique complex of a multigraphMultigraph : multiple edges, no loops.
A clique : a sub(multi)graph isomorphic to Kn .
F .Γ : the simplicial poset of all cliques in Γ.
We want to study topology of F .Γ.

Anton Ayzenberg (HSE, Steklov Institute)

Clique complexes of multigraphs

Osaka, 2021

12 / 26

A generalization: edge inflation
K : a simplicial complex (or simplicial poset).
E pK q : the edge set of K .

µ : E pK q Ñ Z : multiplicity function.
I P K : a simplex, E pI q : its edges.

Anton Ayzenberg (HSE, Steklov Institute)

Clique complexes of multigraphs

Osaka, 2021

13 / 26

A generalization: edge inflation
K : a simplicial complex (or simplicial poset).
E pK q : the edge set of K .

µ : E pK q Ñ Z : multiplicity function.
I P K : a simplex, E pI q : its edges.

Construction±For each simplex I P K we take e PE pI q µpe q many copies of it. Formally, let Kµ
be a poset, whose elements have the form pI , cI q, where I P K and cI : E pI q Ñ Zmaps each edge e P E pI q to one of the labels t1, . . . , µpe qu. The order is given by

pI , cI q ¤ pJ, cJ q iff I  J and cJ |E pI q  cI .
Kµ is a simplicial poset. We call it the edge inflation of K .

Anton Ayzenberg (HSE, Steklov Institute)

Clique complexes of multigraphs

Osaka, 2021

13 / 26

A generalization: edge inflation

Anton Ayzenberg (HSE, Steklov Institute)

Clique complexes of multigraphs

Osaka, 2021

14 / 26

A generalization: edge inflation

RemarkIf Γ is a multigraph, and G is its underlying simple graph (i.e. Γ  Gµ ), thenF .Γ  pF .G qµEdge inflations generalize clique complexes of multigraphs.

Anton Ayzenberg (HSE, Steklov Institute)

Clique complexes of multigraphs

Osaka, 2021

14 / 26

Homotopy type of edge inflations
Let ∆V be a simplex on a vertex set V .

Anton Ayzenberg (HSE, Steklov Institute)

Clique complexes of multigraphs

Osaka, 2021

15 / 26

Homotopy type of edge inflations
Let ∆V be a simplex on a vertex set V .

Theorem (A.–Rukhovich’20)
For each multiplicity function the following hold for edge inflated complexes:
1p∆V qµ is homotopy equivalent to a wedge of npµ, V q many S |V |1 .
2
If K is connected then|Kµ |  |K | _ªP

I K ,dim I
3pΣ|I | | linkK I |q_npµ| ,I q .
I¥1

If K is Cohen–Macaulay, then so is Kµ .

Anton Ayzenberg (HSE, Steklov Institute)

Clique complexes of multigraphsOsaka, 2021

15 / 26

Homotopy type of edge inflations
Let ∆V be a simplex on a vertex set V .

Theorem (A.–Rukhovich’20)
For each multiplicity function the following hold for edge inflated complexes:
1p∆V qµ is homotopy equivalent to a wedge of npµ, V q many S |V |1 .
2
If K is connected then|Kµ |  |K | _ªP

I K ,dim I
3pΣ|I | | linkK I |q_npµ| ,I q .
I¥1If K is Cohen–Macaulay, then so is Kµ .

Item 2 follows from Poset Fiber Theorem, since there is the blow-down map:

Anton Ayzenberg (HSE, Steklov Institute)

Clique complexes of multigraphs

Osaka, 2021

15 / 26

How many spheres in a wedge?

Theorem, essential partFor each multiplicity function the following hold for edge inflated complexes:
1p∆V qµ is homotopy equivalent to a wedge of npµ, V q many S |V |1 .
The number npµ, V q can be computed from Euler characteristic (n  |V |):npµ, V q ¸p1qn|J | | |¥2

J V, J

Anton Ayzenberg (HSE, Steklov Institute)¹ePpJ2qµpe q

Clique complexes of multigraphsp1qn1 pn  1q.

Osaka, 2021

16 / 26

How many spheres in a wedge?
Theorem, essential partFor each multiplicity function the following hold for edge inflated complexes:
1p∆V qµ is homotopy equivalent to a wedge of npµ, V q many S |V |1 .
Item 1 is a bit more complicated than for vertex inflations studied by Björner,Wachs, and Welker.

Anton Ayzenberg (HSE, Steklov Institute)

Clique complexes of multigraphs

Osaka, 2021

17 / 26

How many spheres in a wedge?
Theorem, essential partFor each multiplicity function the following hold for edge inflated complexes:
1p∆V qµ is homotopy equivalent to a wedge of npµ, V q many S |V |1 .
Item 1 is a bit more complicated than for vertex inflations studied by Björner,Wachs, and Welker. It can be derived fromLemma

Let Y  X1 YA X2 . Assume that X1 , X2 are (homotopy equivalent to) wedges ofn-dimensional spheres, and A is a wedge of pn  1q-dimensional spheres. Then Y
is a wedge of n-dimensional spheres.

Anton Ayzenberg (HSE, Steklov Institute)

Clique complexes of multigraphsOsaka, 2021

17 / 26

How many spheres in a wedge?
Theorem, essential partFor each multiplicity function the following hold for edge inflated complexes:
1p∆V qµ is homotopy equivalent to a wedge of npµ, V q many S |V |1 .
Item 1 is a bit more complicated than for vertex inflations studied by Björner,Wachs, and Welker. It can be derived fromLemma

Let Y  X1 YA X2 . Assume that X1 , X2 are (homotopy equivalent to) wedges ofn-dimensional spheres, and A is a wedge of pn  1q-dimensional spheres. Then Yis a wedge of n-dimensional spheres.
If w pZ q denotes the number of spheres in a wedge Z , then we havew pY q  w pX1 q w pX2 q w pAq.

Anton Ayzenberg (HSE, Steklov Institute)

Clique complexes of multigraphs

Osaka, 2021

17 / 26

Calculation examplesw= w+w+w= 0+0+0=0w= w+w+w= 0+0+1=1w= w+w+w= 1+1+2=4

Anton Ayzenberg (HSE, Steklov Institute)

Clique complexes of multigraphs

Osaka, 2021

18 / 26

How many spheres in a wedge?

Since p∆V qµ is always a wedge of spheres, we can ask

natural questions

For which µ the complex p∆V qµ is contractible (= the wedge of zero manyspheres)?
For which µ the complex p∆V qµ is a single sphere?
Etc.

Anton Ayzenberg (HSE, Steklov Institute)

Clique complexes of multigraphs

Osaka, 2021

19 / 26

Characterizations

Let µ : E p∆V q  V2 Ñ Z be a multiplicity function. Consider the simple graphG pµq on V which has an edge ti, j u iff µpti, j uq ¥ 2.

Proposition 0p∆V qµ is contractible iff G pµq has an isolated vertex.

Anton Ayzenberg (HSE, Steklov Institute)

Clique complexes of multigraphs

Osaka, 2021

20 / 26

Characterizations
We say that µ is a starry sky function if
12µpe q P t1, 2u for each e P E p∆V q.

All connected components of G pµq are star graphs with at least 2 vertices.

Proposition 1p∆V qµ is homotopy equiv. to a single sphere iff µ is a starry sky function.
Anton Ayzenberg (HSE, Steklov Institute)

Clique complexes of multigraphs

Osaka, 2021

21 / 26

More infations!
So far we have
Vertex inflations by Björner, Wachs, Welker.
Edge inflations, which allow to describe clique complexes of multigraphs.

Anton Ayzenberg (HSE, Steklov Institute)

Clique complexes of multigraphs

Osaka, 2021

22 / 26

More infations!
So far we have
Vertex inflations by Björner, Wachs, Welker.
Edge inflations, which allow to describe clique complexes of multigraphs.
Why not go further and inflate anything?

Anton Ayzenberg (HSE, Steklov Institute)

Clique complexes of multigraphs

Osaka, 2021

22 / 26

More infations!
So far we have
Vertex inflations by Björner, Wachs, Welker.
Edge inflations, which allow to describe clique complexes of multigraphs.
Why not go further and inflate anything?

Construction

Let K be a simplicial complex (or simplicial poset), and M : K Ñ Z be amultiplicity function. Then we define generalized simplex inflation byFirst, inflate all maximal simplices I , by making M pI q copies of them.
Next, inflate all simplices below maximal (this produces lots of additional
copies of maximal simplices as well).
Proceed below until you reach vertices.

Anton Ayzenberg (HSE, Steklov Institute)

Clique complexes of multigraphs

Osaka, 2021

22 / 26

More infations!
So far we have
Vertex inflations by Björner, Wachs, Welker.
Edge inflations, which allow to describe clique complexes of multigraphs.
Why not go further and inflate anything?

Construction

Let K be a simplicial complex (or simplicial poset), and M : K Ñ Z be amultiplicity function. Then we define generalized simplex inflation byFirst, inflate all maximal simplices I , by making M pI q copies of them.
Next, inflate all simplices below maximal (this produces lots of additional
copies of maximal simplices as well).
Proceed below until you reach vertices.
We get the same results: (1) Inflation of a simplex produces a wedge of spheres;(2) Homotopy wedge decomposition in general; (3) Cohen–Macaulayness isinherited by inflations.
Anton Ayzenberg (HSE, Steklov Institute)

Clique complexes of multigraphs

Osaka, 2021

22 / 26

A very abstract approach and a question
Let K be a simplicial complex. As a poset, it defines a category catpK q, whereI Ñ J iff IJ.

Consider a functor M : catpK q Ñ FSet to finite sets. We inflate K using M.

Anton Ayzenberg (HSE, Steklov Institute)

Clique complexes of multigraphs

Osaka, 2021

23 / 26

A very abstract approach and a question
Let K be a simplicial complex. As a poset, it defines a category catpK q, whereI Ñ J iff IJ.

Consider a functor M : catpK q Ñ FSet to finite sets. We inflate K using M.

Construction

For each simplex I P K initialize |MpI q| its copies. Glue them all together
according to the maps MpI J q. The resulting spacehocolim M
is called the inflation of K by the functor M.
All previous inflations are particular cases of this construction.

Anton Ayzenberg (HSE, Steklov Institute)

Clique complexes of multigraphs

Osaka, 2021

23 / 26

A very abstract approach and a question

Consider K as a finite topological space, open sets are simplicial
subcomplexes.
M can be treated as a sheaf on K .

Anton Ayzenberg (HSE, Steklov Institute)

Clique complexes of multigraphs

Osaka, 2021

24 / 26

A very abstract approach and a question

Consider K as a finite topological space, open sets are simplicial
subcomplexes.
M can be treated as a sheaf on K .

Conjecture
If M is a flasque sheaf on K , then
1For K  ∆V , hocolim M is a wedge of p|V |  1q-dimensional spheres;
2In general, there is a homotopy wedge decomposition for hocolim M.

Anton Ayzenberg (HSE, Steklov Institute)

Clique complexes of multigraphs

Osaka, 2021

24 / 26

Thank you for listening!

Anton Ayzenberg (HSE, Steklov Institute)

Clique complexes of multigraphs

Osaka, 2021

25 / 26

References

A. Ayzenberg, A. Rukhovich, Clique complexes of multigraphs, edge inflations,and tournaplexes, preprint arXiv:2012.07600
A. Björner, M. L. Wachs, V. Welker, Poset fiber theorems, Trans. Amer. Math.
Soc. 357:5 (2005), 1877–1899.
D. Govc, R. Levi, J. P. Smith, Complexes of tournaments, directionality
filtrations and persistent homology, preprint arXiv:2003.00324

Anton Ayzenberg (HSE, Steklov Institute)

Clique complexes of multigraphs

Osaka, 2021

26 / 26