Extremal Betti Numbers and Persistence in Flag Complexes

Beers, Lies; Bakke Botnan, Magnus

doi:10.4230/LIPIcs.SoCG.2025.14

Extremal Betti Numbers and Persistence in Flag Complexes

Lies Beers

Vrije Universiteit Amsterdam, The Netherlands Magnus Bakke Botnan

Vrije Universiteit Amsterdam, The Netherlands

Abstract

We investigate several problems concerning extremal Betti numbers and persistence in filtrations of flag complexes. For graphs on $n$ vertices, we show that $\beta_{k}(X(G))$ is maximal when $G=\mathcal{T}_{n,k+1}$ , the Turán graph on $k+1$ partition classes, where $X(G)$ denotes the flag complex of $G$ . Building on this, we construct an edgewise (one edge at a time) filtration $\mathcal{G}=G_{1}\subseteq\cdots\subseteq\mathcal{T}_{n,k+1}$ for which $\beta_{k}(X(G_{i}))$ is maximal for all graphs on $n$ vertices and $i$ edges. Moreover, the persistence barcode $\mathcal{B}_{k}(X(G))$ achieves a maximal number of intervals, and total persistence, among all edgewise filtrations with $|E(\mathcal{T}_{n,k+1})|$ edges.

For $k=1$ , we consider edgewise filtrations of the complete graph $K_{n}$ . We show that the maximal number of intervals in the persistence barcode is obtained precisely when $G_{\lceil n/2\rceil\cdot\lfloor n/2\rfloor}=\mathcal{T}_{n,2}$ . Among such filtrations, we characterize those achieving maximal total persistence. We further show that no filtration can optimize $\beta_{1}(X(G_{i}))$ for all $i$ , and conjecture that our filtrations maximize the total persistence over all edgewise filtrations of $K_{n}$ .

Keywords and phrases:

Topological data analysis, Extremal graph theory

Copyright and License:

2012 ACM Subject Classification:

Mathematics of computing

\rightarrow

Algebraic topology

Related Version:

Full Version: https://arxiv.org/abs/2502.21294 [3]

Acknowledgements:

We thank Ulrich Bauer for suggesting the problem of maximizing the number of intervals in the barcode of a Vietoris–Rips filtration.

DOI:

10.4230/LIPIcs.SoCG.2025.14

Event:

41st International Symposium on Computational Geometry (SoCG 2025)

Editors:

Oswin Aichholzer and Haitao Wang

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

A central theme in topological data analysis (TDA) is the computation of homological invariants from simplicial complexes. These complexes are often constructed from point cloud data, with the Vietoris–Rips complex being one of the most widely used constructions. For a finite set $P$ in a metric space $(M,d)$ , the Vietoris–Rips complex at scale $r$ , denoted $\mathrm{VR}_{r}(P)$ , includes all simplices $\sigma=\{p_{0},\ldots,p_{n}\}$ such that $d(p_{i},p_{j})\leq 2r$ for all $0\leq i,j\leq n$ . This complex is a flag complex, meaning it is the largest simplicial complex with a given underlying graph (the 1-skeleton). In particular, the edges in the connectivity graph of $P$ at scale $r$ fully determine the higher-dimensional simplices in ${\rm VR}_{r}(P)$ . Varying the scale parameter $r$ induces a filtration of simplicial complexes:

\mathrm{VR}(P)_{r_{0}}\hookrightarrow\mathrm{VR}(P)_{r_{1}}\hookrightarrow% \cdots\hookrightarrow\mathrm{VR}(P)_{r_{m}},

where $r_{0}<r_{1}<\cdots<r_{m}$ . Applying $k$ -dimensional homology over a field $\mathbf{k}$ to this filtration yields a persistence barcode in degree $k$ , denoted $\mathcal{B}_{k}(\mathrm{VR}(P))$ . This barcode, consisting of intervals $[a,b)$ , encodes the birth and death of topological features across scales and serves as a powerful tool for extracting topological information from $P$ . When $P$ is a sufficiently dense sampling of an underlying space $X$ , the number of “long bars” in $\mathcal{B}_{k}(\mathrm{VR}(P))$ determines the $k$ -th Betti number $\beta_{k}(X)$ , which describes the $k$ -dimensional topological features of $X$ [7]. For a comprehensive introduction to topological data analysis, we refer the reader to [8].

Given the central role of such filtrations in TDA, this paper addresses a fundamental question: how many topological features can arise in a data set of $n$ points? Specifically, we investigate bounds on quantities such as the maximal value of $\beta_{k}(\mathrm{VR}_{r}(P))$ , the maximal number of intervals in $\mathcal{B}_{k}(\mathrm{VR}(P))$ , the length of the longest interval, and the sum of the lengths of the intervals (the total persistence).

$\blacktriangleright$ Remark 1.

In this paper, we focus on edgewise filtrations of graphs, i.e., sequences of graphs $\mathcal{G}=G_{1}\subseteq G_{2}\subseteq\cdots\subseteq G_{m}=\bigl{\{}G_{i}% \bigr{\}}_{i=1}^{m},$ on $n$ vertices, where $G_{i+1}$ and $G_{i}$ differ by precisely one edge. Notably, every filtration of flag complexes can be realized as the Vietoris–Rips filtration of an appropriate metric on the vertices of $G_{m}$ ; see the full version of this paper [3, A]. Thus, our results are directly applicable to data analysis using persistent homology.

1.1 Overview and contributions

In Section 2, we introduce the relevant background material and compute the Betti numbers of flag complexes on Turán graphs.

In Section 3, we examine extremal Betti numbers and establish tight upper bounds on $\beta_{k}(F)$ , where $F$ is a flag complex on $n$ vertices (Theorem 10). This upper bound is achieved by the Turán graph $\mathcal{T}_{n,k+1}$ .

In Section 4, we study filtrations of flag complexes on $n$ vertices with at most $e$ edges, where $e$ is the number of edges in $\mathcal{T}_{n,k+1}$ . We prove that our filtration maximizes $\beta_{k}$ at all filtration steps (Theorem 16).

In Section 5, we analyze the longest possible interval in the barcode of a filtration of flag complexes on $n$ vertices (Corollary 21).

Additionally, in Section 6, we focus on degree $1$ homology and show that any filtration of flag complexes on $n$ vertices will achieve the maximal number of intervals in its degree $1$ barcode if and only if the filtration contains $\mathcal{T}_{n,2}$ (Corollary 25).

In Section 7, we explore flag filtrations in homology degree $1$ that achieve both a maximal number of intervals and maximal total persistence. Equivalently, we maximize the total persistence of all filtrations of graphs containing $G_{\lceil n/2\rceil\cdot\lfloor n/2\rfloor}=\mathcal{T}_{n,2}$ . Given the importance of Turán graphs in extremal graph theory, we believe that identifying extremal filtrations of Turán graphs is interesting in its own right. Our result relies on an elaborate combinatorial analysis that precisely classifies the extremal filtrations (Theorem 31).

Finally, the paper concludes with a discussion in which we outline several important conjectures for future work.

1.2 Related work

The study of extremal values of $\mathbb{Z}$ -linear functions on the $f$ - and $\beta$ -vectors of simplicial complexes with $n$ vertices has a rich history. Classical questions include determining the extremal Euler characteristic and the maximal sum of Betti numbers. These problems were addressed for general simplicial complexes in [4] and later extended to arbitrary $\mathbb{Z}$ -linear functions in [11]. Specifically, [11, Theorem 3.4] shows that for flag complexes, extremal values are always realized by $\mathcal{T}_{n,k}$ for some $k$ . Consequently, Theorem 10 follows directly from [11, Theorem 3.4].

Our proof of Theorem 10 adapts the approach of [1, Theorem 1.1], which gives an alternative proof for the extremal total Betti number of flag complexes. The key observation in our proof of Theorem 10 plays a central role in our results on extremal interval lengths (Section 5).

Another related work is [10], which examines asymptotic bounds for $\beta_{k}$ in Vietoris–Rips complexes of point samples in $\mathbb{R}^{d}$ . Similar questions have been explored for Čech complexes; see, e.g., [9].

Our work diverges from earlier work by considering filtered flag complexes. This approach is closely tied to the problem of finding extremal values for complexes with precisely $n$ vertices and $e$ edges; we return to this in Section 8. Importantly, and in contrast to classical work, graphs achieving extremal values need not have $\mathcal{T}_{n,k}$ as a subgraph.

2 Background

Graphs and Simplicial Complexes.

Let $G=(V,E)$ be a graph. We write $\{v,w\}$ for the edge connecting the vertices $v$ and $w$ . For a vertex $v\in V$ , the neighborhood is $N_{G}(v)\coloneqq\bigl{\{}w\colon\{v,w\}\in E\bigr{\}}$ , and the closed neighborhood is $N_{G}[v]\coloneqq N_{G}(v)\cup\{v\}$ . The degree of $v$ is $\deg(v)\coloneqq\deg_{G}(v)\coloneqq|N_{G}(v)|$ . The complete graph on $n$ vertices is denoted $K_{n}$ .

The complement of $G$ , denoted $\overline{G}$ , is the graph on the same vertex set as $G$ , where two distinct vertices of $\overline{G}$ are adjacent if and only if they are non-adjacent in $G$ . The join of disjoint graphs $G_{1}$ and $G_{2}$ is the graph $G_{1}\vee G_{2}$ with vertex set $V(G_{1})\sqcup V(G_{2})$ and edge set $E(G_{1})\cup E(G_{2})\cup\bigl{\{}\{v_{1},v_{2}\}\colon v_{1}\in V(G_{1}),v_{2% }\in V(G_{2})\bigr{\}}$ . The complete bipartite graph $K_{n_{1},n_{2}}$ is defined as the join $G_{1}\vee G_{2}$ , where each $G_{i}$ is an empty graph on $n_{i}$ vertices. The sets $V(G_{1})$ and $V(G_{2})$ are called the partition classes of $K_{n_{1},n_{2}}$ .

For a vertex $v$ in a simplicial complex $K$ , the link and (closed) star of $v$ are the simplicial complexes given respectively by

{\rm lk}_{K}(v)=\{\tau\in K:v\not\in\tau,\{v\}\cup\tau\in K\}\qquad\qquad{\rm st% }_{K}(v)=\{\tau\in K:\{v\}\cup\tau\in K\}.

We write $K-v$ for the simplicial complex with simplices $\tau\in K$ for which $v\not\in K$ .

For a graph $G$ , we let $X(G)$ denote the simplicial complex with $m$ -simplices given by the $(m+1)$ -cliques in $G$ . A simplicial complex $K$ is called a flag complex if $K=X(G)$ for some graph $G$ . The independence complex of $G$ is the simplicial complex ${\rm Ind}(G)=X(\overline{G})$ . Examples of flag and independence complexes are given in Figure 1.

Figure 1: A graph (left), its flag complex (middle) and independence complex (right).

Homology.

For a simplicial complex $K$ , we let $\beta_{k}(K)$ denote the dimension of the reduced homology group $\tilde{H}_{k}(K;\mathbf{k})$ , and let $C_{k}(K)$ denote the vector space of $k$ -chains. We use coefficients in a fixed, but arbitrary, field $\mathbf{k}$ ; our optimal constructions are torsion-free and thus our results do not depend on the choice of coefficient field. For that reason, we simply write $\tilde{H}_{k}(K)$ . We also employ the notation $\beta^{{\rm FL}}_{k}(G)=\beta_{k}(X(G))$ for a graph $G$ .

Persistent Homology.

A filtration $\mathscr{K}$ of simplicial complexes is a collection of simplicial complexes $\{K_{i}\}_{i=1}^{m}$ such that $K_{i}\subseteq K_{j}$ for $i\leq j$ . Applying $\tilde{H}_{k}(-;\mathbf{k})$ to a filtration yields a sequence of vector spaces and linear maps $\tilde{H}_{k}(\mathscr{K}):\tilde{H}_{k}(K_{1})\to\cdots\to\tilde{H}_{k}(K_{m})$ called a persistence module. Provided all the vector spaces are finite-dimensional, $\tilde{H}_{k}(\mathscr{K})$ is uniquely described by a collection of intervals in $\{1,\ldots,m\}$ , called the degree $k$ barcode of $\mathscr{K}$ . We shall denote this barcode by $\mathcal{B}_{k}(\mathscr{K})$ . The total persistence of $\mathcal{K}$ is given by

T\beta_{k}(\mathcal{K})=\sum_{[a,b)\in\mathcal{B}_{k}(\mathcal{K})}\bigl{(}b-a% \bigr{)}=\sum_{i=1}^{m}\beta_{k}(K_{i}).

For a more thorough introduction to persistent homology, (generalized) persistence modules, and examples, see, e.g., [8, Chapter 3] or [5].

For a filtration $\mathcal{G}$ of graphs (1-dimensional simplicial complexes), we get a filtration $X(\mathcal{G})$ of simplicial complexes by taking the flag complex at every index. If $G_{i+1}-G_{i}$ is a single edge for all $i$ , then we say that the filtration $\mathcal{G}$ is edgewise. We shall employ the notation $\mathcal{B}^{{\rm FL}}_{k}(G)=\mathcal{B}_{k}(X(\mathcal{G}))$ .

Example 2.

An edgewise filtration of $K_{5}$ can be found in Figure 2.

Figure 2: An edgewise filtration of

K_{5}

.

2.1 Elementary homological properties

The following two lemmas are well-known and important in combinatorial topology. For completeness, their proofs can be found in the full version [3, B.1].

Lemma 3.

Let $K$ be a simplicial complex and $v\in V(K)$ a vertex. Then, for all $k\geq 1$ ,

\beta_{k}(K)\leq\beta_{k}(K-v)+\beta_{k-1}({\rm lk}_{K}(v)).

Lemma 4.

For any two graphs $G$ and $H$ , and $k\geq-1$ ,

\beta_{k}({\rm Ind}(G\sqcup H))=\sum_{i,j\geq-1;i+j=k-1}\beta_{i}({\rm Ind}(G)% )\beta_{j}({\rm Ind}(H)).

The following observation is essential for our work in Section 7.

Proposition 5.

Let $V(G)=V_{1}\sqcup V_{2}$ be the vertex set of a graph $G$ containing all edges of the form $\{v,w\}$ where $v\in V_{1}$ and $w\in V_{2}$ . Let $d_{i}\geq 1$ denote the number of connected components of $G$ restricted to $V_{i}$ . Then, $\beta^{{\rm FL}}_{1}(G)=\beta^{{\rm FL}}_{0}(G_{1})\beta^{{\rm FL}}_{0}(G_{2})% =(d_{1}-1)(d_{2}-1).$

Proof.

Let $\overline{G}$ denote the complement graph of $G$ and observe that $\overline{G}=\overline{G}_{1}\sqcup\overline{G}_{2}$ where $G_{1}$ and $G_{2}$ are the full subgraphs of $G$ with vertices $V_{1}$ and $V_{2}$ , respectively. From Lemma 4,

\beta^{{\rm FL}}_{1}(G)=\beta_{1}({\rm Ind}(\overline{G}))=\beta_{0}({\rm Ind}% (\overline{G}_{1}))\beta_{0}({\rm Ind}(\overline{G}_{2}))=\beta_{0}(X(G_{1}))% \beta_{0}(X(G_{2})).\

$\hfill\blacktriangleleft$

2.2 Turán graphs

Definition 6.

Let $n\geq 0$ and $k\geq 1$ , and let $n^{\prime}$ be the smallest positive integer such that $n^{\prime}\equiv n\bmod k$ . Then, the $(n,k)$ graph $\mathcal{T}_{n,k}$ is the complement graph of the graph

\overline{\mathcal{T}_{n,k}}=\bigsqcup_{i=1}^{k}K_{n_{i}},\qquad n_{i}=\begin{% cases}\lceil n/k\rceil&\text{ if }1\leq i\leq n^{\prime},\\ \lfloor n/k\rfloor&\text{otherwise.}\end{cases}

Example 7.

See Figure 3 for some examples of Turán graphs.

Figure 3: From left to right: the Turán graphs

\mathcal{T}_{5,2}

,

\mathcal{T}_{8,2}

and

\mathcal{T}_{8,3}

.

The proof of the following can be found in the full version [3, B.1].

Proposition 8.

For all integers $n\geq 1$ and $k\geq 1$ , we let $n^{\prime}$ be the smallest positive integer such that $n^{\prime}\equiv n\bmod k$ . We have

\beta^{{\rm FL}}_{i}(\mathcal{T}_{n,k})=\begin{cases}(\lceil n/k\rceil-1)^{n^{% \prime}}\cdot(\lfloor n/k\rfloor-1)^{k-n^{\prime}}&\text{if $i=k-1$},\\ 0&\text{otherwise.}\end{cases}

In particular, if $n$ is a multiple of $k$ , then $\beta_{k-1}=(n/k-1)^{k}.$

3 The maximum value of $\beta_{k}(X(G))$

The following is well-known; see the full version [3, B.2] for a proof.

Lemma 9.

Let $S$ be a positive integer, and $x_{i}\geq 1$ be integers satisfying $\sum_{i=1}^{n}x_{i}=S$ . Then, $\prod_{i=1}^{n}(x_{i}-1)\leq\prod_{i=1}^{n}(y_{i}-1)$ where

y_{i}=\begin{cases}\lceil S/n\rceil&\text{ if }1\leq i\leq S\bmod n\\ \lfloor S/n\rfloor&\text{otherwise.}\end{cases}

(1)

As said in Section 1.2, the following proof is a modification of the proof of [1, Theorem 1.1].

Theorem 10.

Let $G$ be a graph on $n$ vertices. Then, for all $k\geq 0$ ,

\beta^{{\rm FL}}_{k}(G)\leq(\lceil n/(k+1)\rceil-1)^{(n\bmod k+1)}\cdot(% \lfloor n/(k+1)\rfloor-1)^{(k+1)-(n\bmod k+1)}.

Proof.

We shall work inductively on $n$ . The result is trivially true for $n=1$ , so assume that it holds for all $n^{\prime}<n$ .

Note that $X(G)={\rm Ind}(\overline{G})$ . Let $d$ denote the minimal degree over all $v\in V(\overline{G})$ . Assume that $v$ is a vertex with $\deg(v)=d$ , and let $\{v_{1},\ldots,v_{d}\}$ denote the neighbours of $v$ in $\overline{G}$ . Moreover, let $\overline{G}_{i}=\overline{G}-\{v_{1},\ldots,v_{i}\}$ for $i=1,\ldots,d$ and $\overline{G}_{0}=\overline{G}$ . Applying Lemma 3,

	$\displaystyle\beta_{k}({\rm Ind}(\overline{G}))$	$\displaystyle\leq\beta_{k}({\rm Ind}(\overline{G}_{1}))+\beta_{k-1}({\rm Ind}(% \overline{G}-N_{\overline{G}}[v_{1}])$
		$\displaystyle\leq\beta_{k}({\rm Ind}(\overline{G}_{2}))+\beta_{k-1}({\rm Ind}(% \overline{G}_{1}-N_{\overline{G}_{1}}[v_{2}]))+\beta_{k-1}({\rm Ind}(\overline% {G}-N_{\overline{G}}[v_{1}])))$
		$\displaystyle\vdots$
		$\displaystyle\leq\beta_{k}({\rm Ind}(\overline{G}_{d}))+\sum_{i=0}^{d-1}\beta_% {k-1}({\rm Ind}(\overline{G}_{i}-N_{\overline{G}_{i}}[v_{i+1}]))$

Here $\overline{G}_{d}$ has an isolated vertex and thus ${\rm Ind}(\overline{G}_{d})$ is a cone, and therefore $\beta_{k}({\rm Ind}(\overline{G}_{d}))=0$ . Since every vertex of $\overline{G}$ has degree at least $d$ , it follows that $\overline{G}_{i}-N_{\overline{G}_{i}}(v_{i+1})$ contains at most $n-(d+1)=n-d-1$ vertices. By the induction hypothesis it follows that

\beta_{k}({\rm Ind}(\overline{G}))\leq d\cdot(x_{1}-1)\cdots(x_{k}-1)=((d+1)-1% )\cdot(x_{1}-1)\cdots(x_{k}-1)

for integers $x_{i}\geq 1$ for which $(d+1)+\sum_{i=1}^{k}x_{i}=d+1+n-d-1=n$ . Hence, by Lemma 9,

\beta_{k}({\rm Ind}(\overline{G}))\leq(\lceil n/(k+1)\rceil-1)^{(n\bmod k+1)}% \cdot(\lfloor n/(k+1)\rfloor-1)^{(k+1)-(n\bmod k+1)}.\

$\hfill\blacktriangleleft$ Let $\mathbf{G}(n)=\bigl{\{}G\colon\text{ graph on $n$ vertices}\bigr{\}}$ . Combining Theorem 10 and Proposition 8, we have

Corollary 11.

Of all graphs on $n$ vertices, $\mathcal{T}_{n,k+1}$ maximizes the $k$ -th Betti number. I.e.,

\max_{G\in\mathbf{G}(n)}\beta^{{\rm FL}}_{k}(G)=\beta^{{\rm FL}}_{k}(\mathcal{% T}_{n,k+1}).

In particular, if $n$ is a multiple of $k$ , then $\max_{G\in\mathbf{G}(n)}\beta^{{\rm FL}}_{k}(G)=(n/k-1)^{k}.$

4 The maximum value of $\beta_{k}(X(G))$ for $|E(G)|\leq|E(\mathcal{T}_{n,k+1})|$

In this section, we fix $n,k\geq 1$ , and the notation

e_{n,k+1}\coloneqq|E(\mathcal{T}_{n,k+1})|\text{ and }\Delta_{m-1,m}^{k+1}% \coloneqq e_{m}^{k+1}-e_{m-1}^{k+1}.

(2)

The following result follows from combining Lemma 3 and Corollary 11, and will be integral in proving the main result of this section.

Corollary 12.

Let $v$ be a vertex of degree $d\geq 1$ in a graph $G$ . Then,

\beta^{{\rm FL}}_{k}(G)\leq\beta^{{\rm FL}}_{k}(G-v)+\beta^{{\rm FL}}_{k-1}(% \mathcal{T}_{d,k}).

Proof.

If $K=X(G)$ , then $K-v=X(G-v)$ , and Lemma 3 implies that

\beta^{{\rm FL}}_{k}(G)\leq\beta^{{\rm FL}}_{k}(G-v)+\beta_{k-1}({\rm lk}_{X(G% )}(v)).

Now observe that ${\rm lk}_{X(G)}(v)=X(N_{G}[v])$ , and since ${\rm lk}_{X(G)}(v)$ has $d$ vertices, it follows from Corollary 11 that $\beta_{k-1}({\rm lk}_{K}(v))\leq\beta^{{\rm FL}}_{k-1}(\mathcal{T}_{d,k})$ . $\hfill\blacktriangleleft$ We now define an edgewise filtration $\mathcal{H}^{n,k+1}=\mathcal{H}=\bigl{\{}H_{i}\bigr{\}}_{i=1}^{e_{n,k+1}}=% \bigl{\{}H_{i}^{n,k+1}\bigr{\}}_{i=1}^{e_{n,k+1}}$ of the Turán graph $\mathcal{T}_{n,k+1}$ . In this section, we shall show, for $m=1,\ldots,|\mathcal{T}_{n,k+1}|$ , that $\beta^{{\rm FL}}_{k}(H_{m})$ is maximal over all graphs with $m$ edges, i.e., that $\mathcal{H}$ is fiberwise optimal.

Figure 4: The filtration

\mathcal{H}

of

\mathcal{T}_{8,2}

from Definition 13.

Definition 13.

Let $V$ denote the vertices of $\mathcal{T}_{n,k+1}$ and label the elements of $V$ such that $v_{i}$ and $v_{i+k+1}$ are in the same partition. Writing each edge as $e_{i,j}=\{v_{i},v_{j}\}$ for $i<j$ , we order the edges by the following co-lexicographic order: $e_{i,j}<e_{k,l}$ if $\max\{i,j\}<\max\{k,l\}$ , or if $i=k$ and $j<l$ , or if $j=l$ and $i<k$ . Following this order, let $H_{i}=H_{i}^{n,k+1}$ denote the subgraph of $\mathcal{T}_{n,k+1}$ with the first $i$ edges.

Note that, since $\mathcal{T}_{n,k+1}$ contains no $k+1$ -simplices, $\beta_{k}(H_{i})$ is increasing as a function of $i$ .

Example 14.

See Figure 2 for an edgewise filtration $\mathcal{G}=\bigl{\{}G_{i}\bigr{\}}_{i=1}^{6}$ of $K_{5}$ , where $G_{i}\cong H_{i}^{5,2}$ for $i=1,\ldots,6$ . Furthermore, in Figure 4 one can find the filtration $\mathcal{H}^{8,2}$ of $\mathcal{T}_{8,2}$ .

The next lemma shows that, once a vertex has been connected to the growing component, and until the next vertex gets connected, the change in $\beta^{{\rm FL}}_{k}$ from adding a single edge increases with the number of edges already added. Its proof, similar to that of Corollary 12, can be found in the full version [3, B.3].

Lemma 15.

For $e$ edges, let $m$ be maximal such that $\mathcal{T}_{m,k+1}$ is a subgraph of $H_{e}$ . Then,

\beta^{{\rm FL}}_{k}\bigl{(}H_{e}\bigr{)}=\beta^{{\rm FL}}_{k}\bigl{(}\mathcal% {T}_{m,k+1}\bigr{)}+\beta^{{\rm FL}}_{k-1}\bigl{(}\mathcal{T}_{e-e_{m}^{k+1},k% }\bigr{)}.

In particular, for $e_{m}^{k+1}\leq e_{1}<e_{2}<e_{m+1}^{k+1}$ , we have that

\beta^{{\rm FL}}_{k}(H_{e_{1}+1})-\beta^{{\rm FL}}_{k}(H_{e_{1}})\leq\beta^{{% \rm FL}}_{k}(H_{e_{2}+1})-\beta^{{\rm FL}}_{k}(H_{e_{2}}).

Theorem 16.

Let $e\leq e_{n,k+1}$ , let $H_{e}$ be as above, and let $G$ be any other graph on $n$ vertices and $e$ edges. Then, $\beta^{{\rm FL}}_{k}(G)\leq\beta^{{\rm FL}}_{k}(H_{e}).$

Proof.

We prove this inductively on the number of edges $e$ . The statement is clearly true for $e=1$ , so let’s assume that the result holds for all $e^{\prime}<e$ .

Let $m$ be the number of vertices in $H_{e}$ with positive degree, and let $n^{\prime}$ denote the number of vertices in $G$ with positive degree. If $n^{\prime}<m$ , then by Theorem 10,

\beta^{{\rm FL}}_{k}(G)\leq\beta^{{\rm FL}}_{k}(\mathcal{T}_{m-1,k+1})\leq% \beta^{{\rm FL}}_{k}(H_{e}).

Hence, we may assume that $n^{\prime}\geq m$ . In particular, the average degree of the positive-degree-vertices in $G$ is no larger than the average degree of positive-degree-vertices in $H_{e}$ .

Choose a vertex $v$ in $G$ with minimal positive degree $d$ , and observe that

d\leq e^{k+1}_{m}-e^{k+1}_{m-1}=\Delta_{m-1,m},

since $\mathcal{T}_{m-1,k+1}\subsetneq H_{e}\subseteq\mathcal{T}_{m,k+1}$ . In fact, if $d=\Delta_{m-1,m}$ , then we must have that the average degree in $H_{e}$ is at least $d$ . Importantly, this happens if and only if $H_{e}=\mathcal{T}_{m,k+1}$ and $m$ is a multiple of $k+1$ .

By the induction assumption,

	$\displaystyle\beta^{{\rm FL}}_{k}(G-v)$	$\displaystyle\leq\beta^{{\rm FL}}_{k}(H_{e-\deg(v)}),\text{ and thus, by % Corollary \ref{cor:maxvertex},}$
	$\displaystyle\beta^{{\rm FL}}_{k}(G)$	$\displaystyle\leq\beta^{{\rm FL}}_{k}(H_{e-\deg(v)})+\beta^{{\rm FL}}_{k-1}(% \mathcal{T}_{d,k}).$

If $d=\Delta_{m-1,m}$ , then this becomes, by Lemma 15,

\beta^{{\rm FL}}_{k}(G)\leq\beta^{{\rm FL}}_{k}(\mathcal{T}_{m-1,k+1}))+\beta^% {{\rm FL}}_{k-1}(\mathcal{T}_{d,k})=\beta^{{\rm FL}}_{k}(\mathcal{T}_{m,k+1})=% \beta^{{\rm FL}}_{k}(H_{e}).

Figure 5: An illustration of Case

2

from the proof of Theorem 16.

We may therefore assume that $d\leq\Delta_{m-1,m}-1\leq\Delta_{m-2,m-1}$ .

Let $\hat{e}$ denote the number of edges that is added to $H_{e-d}$ before a new vertex gets positive degree in the filtration $\mathcal{H}$ . Let $d^{\prime}$ be the degree of the last vertex in $H_{e-d}$ that obtained positive degree in $\mathcal{H}$ . We consider two cases.

$\blacksquare$

Case 1: $\mathcal{T}_{m-1,k}\subseteq H_{e-d}$ . Then,

$\displaystyle\beta^{{\rm FL}}_{k}(G)$ $\displaystyle\leq\beta^{{\rm FL}}_{k}({H_{e-d}})+\beta^{{\rm FL}}_{k-1}(% \mathcal{T}_{d,k})$

$\displaystyle=\beta^{{\rm FL}}_{k}({H_{e-d}})+\beta^{{\rm FL}}_{k}(H_{e_{m}^{k% +1}+d})-\beta^{{\rm FL}}_{k}(H_{e_{m}^{k+1}})$

$\displaystyle\leq\beta^{{\rm FL}}_{k}({H_{e-d}})+\beta^{{\rm FL}}_{k}(H_{e})-% \beta^{{\rm FL}}_{k}(H_{e-d})$

$\displaystyle=\beta^{{\rm FL}}_{k}(H_{e}).$

\blacksquare

Case 2: $\mathcal{T}_{m-2,k}\subseteq H_{e-d}\subset\mathcal{T}_{m-1,k}$ . Note that $d^{\prime}+\hat{e}=\Delta_{m-2,m-1}\geq d$ and $d-\hat{e}\geq 0$ (see Figure 5). In particular,

	$\displaystyle\beta^{{\rm FL}}_{k}(G)$	$\displaystyle\leq\beta^{{\rm FL}}_{k}({H_{e-d}})+\beta^{{\rm FL}}_{k-1}(% \mathcal{T}_{d,k})$
		$\displaystyle=\beta^{{\rm FL}}_{k}({H_{e-d}})+\bigl{(}\beta^{{\rm FL}}_{k-1}(% \mathcal{T}_{d,k})-\beta^{{\rm FL}}_{k-1}(\mathcal{T}_{d-\hat{e},k})\bigr{)}+% \beta^{{\rm FL}}_{k-1}(\mathcal{T}_{d-\hat{e},k})$
		$\displaystyle\leq\beta^{{\rm FL}}_{k}({H_{e-d}})+\bigl{(}\beta^{{\rm FL}}_{k-1% }(\mathcal{T}_{d^{\prime}+\hat{e},k}\bigr{)}-\beta^{{\rm FL}}_{k-1}(\mathcal{T% }_{d^{\prime},k}))+\beta^{{\rm FL}}_{k-1}(\mathcal{T}_{d-\hat{e},k})$
		$\displaystyle=\beta^{{\rm FL}}_{k}(H_{e}).$

In both cases, the inequality follows from Corollary 12 and Lemma 15. $\hfill\blacktriangleleft$

5 Tight bounds on the vanishing of homology and extremal interval lengths

For a graph $G$ with $n$ vertices, it is guaranteed that there exists a vertex of degree $n-1$ when the average degree exceeds $n-2$ . Specifically, if the number of edges satisfies $m>\frac{n(n-2)}{2}$ , then $X(G)$ must be a cone, implying that $\beta^{{\rm FL}}_{k}(G)=0$ for all $k$ . In practical scenarios, however, the primary interest is with $\beta^{{\rm FL}}_{k}(G)$ for small $k$ . In this section, we provide tight bounds for the vanishing of $\beta^{{\rm FL}}_{k}(G)$ for a fixed $k$ .

Lemma 17.

Let $G$ be a graph with minimum degree $u$ . Let $v$ be a vertex of degree $u$ and let $N_{G}(v)=\bigl{\{}v_{1},\ldots,v_{u}\bigr{\}}$ . Let $d_{i}\coloneqq\deg(v_{i})$ . If $G$ has $n$ vertices and $m$ edges, then

\bigl{|}V\bigl{(}G-N_{G}[v_{i}]\bigr{)}\bigr{|}=n-d_{i}-1\text{ and }\bigl{|}E% \bigl{(}G-N_{G}[v_{i}]\bigr{)}\bigr{|}\leq m-\biggl{(}d_{i}+\biggl{\lceil}% \frac{(u-1)d_{i}}{2}\biggr{\rceil}\biggr{)}.

Proof.

Let $\widehat{G}\coloneqq G-N_{G}[v_{i}]$ . The fact that $\bigl{|}V\bigl{(}\widehat{G}\bigr{)}\bigr{|}=n-d_{i}-1$ is trivial. For showing the inequality, note that, by removing $N_{G}[v_{i}]$ from $G$ , we remove the $d_{i}$ edges containing $v_{i}$ , and all edges containing the vertices of $N_{G}(v_{i})$ . Those vertices all have degree at least $u$ , which means that they have at least $u-1$ neighbors apart from $v_{i}$ . Because it might be the case that $N_{G}\bigl{(}N_{G}[v_{i}]\bigr{)}=N_{G}[v_{i}]$ , it follows that

\bigl{|}E\bigl{(}\widehat{G}\bigr{)}\bigr{|}\leq m-\biggl{(}d_{i}+\biggl{% \lceil}\frac{(u-1)d_{i}}{2}\biggr{\rceil}\biggr{)}.\

$\hfill\blacktriangleleft$

Theorem 18.

Let $G$ be a graph with $n$ vertices and $m>\binom{n-1}{2}+k$ edges. Then $\beta^{{\rm FL}}_{k}(G)=0$ .

Proof.

Let us first consider the case $k=0$ . This case is immediate from the fact that the maximal number of edges in a graph on $n$ vertices with an isolated vertex is $\binom{n-1}{2}$ .

Working inductively on $k$ , assume that result holds for all $k^{\prime}<k$ , and that $m>\binom{n-1}{2}+k$ . Let $\overline{G}$ be the complement graph of $G$ , and note that the number of edges $\overline{m}=|E(\overline{G})|$ satisfies

\overline{m}=\binom{n}{2}-m<\binom{n}{2}-\binom{n-1}{2}-k=n-1-k.

From the proof of Theorem 10, we have that

\displaystyle\beta^{{\rm FL}}_{k}(G)=\beta_{k}({\rm Ind}(\overline{G}))\leq% \sum_{i=0}^{d-1}\beta_{k-1}({\rm Ind}(\overline{G}_{i}-N_{\overline{G}_{i}}[v_% {i+1}])),

where $\overline{G}_{i}=\overline{G}-\{v_{1},\ldots,v_{i}\}$ , and $\{v_{1},\ldots,v_{u}\}$ are the neighbors of a vertex $v\in V(\overline{G})$ with minimal degree $u$ . We shall show that all the terms in the sum are zero.

If we let $u^{\prime}\geq u-i$ denote the minimal degree of a vertex in $V(\overline{G}_{i}-N_{\overline{G}_{i}}[v_{i+1}])$ ,

	$\displaystyle\bigl{\|}E\bigl{(}\overline{G}_{i}-N_{\overline{G}_{i}}[v_{i+1}])% \bigr{\|}$
	$\displaystyle\overset{(i)}{\leq}\|E(\overline{G}_{i})\|-\biggl{(}\deg_{\overline% {G}_{i}}(v_{i+1})+\biggl{\lceil}\frac{(u^{\prime}-1)\deg_{\overline{G}_{i}}(v_% {i+1})}{2}\biggr{\rceil}\biggr{)}$
	$\displaystyle\overset{(ii)}{\leq}\|E(\overline{G}_{i})\|-\biggl{(}u-i+\biggl{% \lceil}\frac{(u-i-1)(u-i)}{2}\biggr{\rceil}\biggr{)}=\|E(\overline{G}_{i})\|-% \sum_{j=1}^{u-i}j$
	$\displaystyle\overset{(iii)}{\leq}\|E(\overline{G})\|-\sum_{j=u-i+1}^{u}j-\sum_{% j=1}^{u-i}j=\|E(\overline{G})\|-\sum_{j=1}^{u}j=\overline{m}-\left(\frac{u(u+1)}% {2}\right).$

Here, $(i)$ follows from Lemma 17, $(ii)$ from $\deg_{\overline{G}_{i}}(v_{i})\geq u^{\prime}$ , and $(iii)$ from the fact that $\overline{G}_{i}$ is obtained by removing $i$ vertices from $\overline{G}$ with degree at least $u$ in $\overline{G}$ . Now write

n^{\prime}=|V({\rm Ind}(\overline{G}_{i}-N_{\overline{G}_{i}}[v_{i+1}]))|\leq n% -u-1,

and observe that

|E({\rm Ind}(\overline{G}_{i}-N_{\overline{G}_{i}}[v_{i+1}]))|\geq\binom{n^{% \prime}}{2}-\overline{m}+u(u+1)/2.

It follows that,

	$\displaystyle\|E({\rm Ind}(\overline{G}_{i}-N_{\overline{G}_{i}}[v_{i+1}]))\|-% \binom{n^{\prime}-1}{2}$
	$\displaystyle\geq\binom{n^{\prime}}{2}-\overline{m}+u(u+1)/2-\binom{n^{\prime}% -1}{2}$
	$\displaystyle=n^{\prime}-1-\overline{m}+u(u+1)/2>n^{\prime}-1-(n-1-k)+u(u+1)/2% \geq k+u(u+1)/2\geq k.$

Hence, $\beta_{k-1}({\rm Ind}(\overline{G}_{i}-N_{\overline{G}_{i}}[v_{i+1}]))=0$ by the induction hypothesis. $\hfill\blacktriangleleft$

$\blacktriangleright$ Remark 19.

Observe that the difference between the bound for a cone and the bound given in Theorem 18 is $n/2-k-1$ . While this difference is linear in the number of vertices, it can result in a significant reduction in the number of higher-dimensional simplices; a reduction which has the potential to speed up current implementations of persistent homology for flag complexes, e.g., Ripser [2].

In the following example, we show that that bounds in the previous theorem are tight.

Example 20.

Let $n=(k+1)p$ , and let $K_{1,p-1}$ be a star graph on $p$ vertices and $p-1$ edges, i.e., a central vertex connected to all other vertices. Observe that $\beta_{0}({\rm Ind}(K_{1,p-1}))=1$ as one vertex is completely disconnected in the complement graph. If, $H=\bigsqcup_{i=1}^{k+1}K_{1,p-1}$ , then it follows from repeated application of Lemma 4 that $\beta_{k}({\rm Ind}(H))\geq\prod_{i=1}^{k+1}\beta_{0}({\rm Ind}(K_{1,p-1}))=1$ . The number of edges in ${\rm Ind}(H)$ is

\binom{n}{2}-(k+1)(p-1)=\binom{n}{2}-n+(k+1)=\binom{n}{2}-(n-1)+k=\binom{n-1}{% 2}+k.

Corollary 21.

Let $\mathcal{G}$ be an edgewise filtration on $n$ vertices. Then for any $[a,b)\in\mathcal{B}^{{\rm FL}}_{k}(\mathcal{G})$ , we have

2k(k+1)\leq a<b\leq\binom{n-1}{2}+k.

Proof.

The bound on $a$ follows from Theorem 16, and the bound on $b$ from Theorem 18. $\hfill\blacktriangleleft$ It is straightforward to define a filtration $\mathcal{F}$ of the complement graph of $H$ from Example 20 such that $\mathcal{B}^{{\rm FL}}_{k}(\mathcal{\mathcal{F}})$ contains the interval $[a,b)$ from Corollary 21.

6 The maximum value of $|\beta^{{\rm FL}}_{1}(\mathcal{G})|$

Proposition 22.

Let $\mathcal{G}=\{G_{i}\}_{i=1}^{m}$ be an edgewise filtration. Then, there exists a triangle-free subgraph $H$ of $G_{m}$ such that $\beta^{{\rm FL}}_{1}(H)\geq|\mathcal{B}^{{\rm FL}}_{1}(\mathcal{G})|.$

Proof.

Choose a representative cycle $c_{[a,b]}$ for each non-empty interval $[a,b)\in\mathcal{B}^{{\rm FL}}_{1}(\mathcal{G})$ , e.g., by running the standard algorithm for persistent homology. For a cycle $c$ , let $e(c)$ denote the set of edges on which the cycle has a non-zero coefficient, and let $H$ be the subgraph of $G_{m}$ with edges given by

\bigcup_{[a,b)\in\mathcal{B}^{{\rm FL}}_{1}(\mathcal{G})}e(c_{[a,b)]}).

Note that the cycles $\{c_{[a,b)}:[a,b)\in\mathcal{B}^{{\rm FL}}_{1}(\mathcal{G})\}$ are linearly independent (as elements of $C_{1}(G)$ ) by virtue of being representatives for non-trivial intervals.

If $X(H)$ contains a 2-simplex $\tau=\{v_{1},v_{2},v_{3}\}$ , then any cycle $c_{[a,b)}$ supported on the edge $\{v_{2},v_{3}\}$ is homologous in $\tilde{H}_{1}(X(H))$ to the cycle $c^{\prime}_{[a,b)}=c_{[a,b)}-\partial_{2}(\tau)$ . Hence, we can remove $\{v_{2},v_{3}\}$ from $H$ , without reducing the 1st Betti number. Doing this for all triangles, we end up with a triangle-free graph $\hat{H}$ containing at least $|\mathcal{B}^{{\rm FL}}_{1}(\mathcal{G})|$ linearly independent $1$ -cycles. In particular, $\beta^{{\rm FL}}_{1}(\hat{H})\geq|\mathcal{B}^{{\rm FL}}_{1}(\mathcal{G})|$ . $\hfill\blacktriangleleft$

$\blacktriangleright$ Remark 23.

This argument does not apply to homology in higher degrees. For instance, the removal of an edge can result in the removal of many $2$ -simplices, some of which are faces of $3$ -simplices, and others that are not.

The previous result actually gives a short proof of Corollary 11 for the case $k=1$ . We shall include this proof here, as it ensures uniqueness of the extremal complex.

Proposition 24.

For any graph on $n$ vertices, we have $\beta^{{\rm FL}}_{1}(G)\leq\beta^{{\rm FL}}_{1}(\mathcal{T}_{n,2})$ with equality if and only if $G=\mathcal{T}_{n,2}$ .

Proof.

Define any edgewise filtration $\mathcal{G}=\{G_{i}\}_{i=1}^{m}$ for which $G_{m}=G$ . Then, by Proposition 22, there exists a triangle-free graph $H$ such that $\beta^{{\rm FL}}_{1}(H)\geq\mathcal{B}^{{\rm FL}}_{1}(\mathcal{G})\geq\beta^{{% \rm FL}}_{1}(G)$ . Hence, it suffices to maximize $\beta^{{\rm FL}}_{1}(G)$ over triangle-free graphs. By the Euler-Poincaré formula,

\beta^{{\rm FL}}_{1}(G)=-\beta^{{\rm FL}}_{0}(G)-1-|V(G)|+|E(G)|.

In conclusion, we are seeking a triangle-free graph with a maximal number of edges, but this is well-known to be uniquely the graph $\mathcal{T}_{n,2}$ by Turán’s theorem [6, Theorem 11.17]. $\hfill\blacktriangleleft$

Combined we arrive at the following.

Corollary 25.

If $\mathcal{G}$ is a filtration of $K_{n}$ , then $|\mathcal{B}^{{\rm FL}}_{1}(\mathcal{G})|\leq\beta^{{\rm FL}}_{1}(\mathcal{T}_% {n,2})$ with equality if and only if $G_{\lceil n/2\rceil\cdot\lfloor n/2\rfloor}=\mathcal{T}_{n,2}$ .

7 Extremal filtrations for degree 1 persistent homology

In this section, we consider edgewise filtrations $\mathcal{G}=G_{1}\subseteq\cdots\subseteq G_{\binom{n}{2}}$ of the complete graph $K_{n}$ that maximize the total persistence and the number of bars for degree $1$ homology. We shall answer the following question:
For a fixed number of vertices $n$ and for $k=1$ , which edgewise filtrations of the complete graph $K_{n}$ with a maximal number of bars achieve maximal total persistence?
By Corollary 25, this translates to finding

\max\biggl{\{}\sum_{i=1}^{n(n-1)/2}\beta^{{\rm FL}}_{1}(G_{i})\colon\mathcal{G% }=\bigl{\{}G_{i}\colon 1\leq i\leq\binom{n}{2},G_{|E(\mathcal{T}_{n,2})|}=% \mathcal{T}_{n,2}\text{ and }G_{n(n-1)/2}=K_{n}\bigr{\}}\biggr{\}}.

First, we give some preliminaries and establish some notation.

$\blacksquare$

All graphs $G=(V,E)$ have $n$ vertices. The join of two graphs $G_{1}$ and $G_{2}$ , notation $G_{1}\vee G_{2}$ , is as in Section 2.
$\blacksquare$

For a filtration $\mathcal{G}=\bigl{\{}G_{i}\bigr{\}}_{i=1}^{m}$ , we write $T\beta^{{\rm FL}}_{1}\bigl{(}\mathcal{G}\bigr{)}=\sum_{i=1}^{m}\beta^{{\rm FL}% }_{1}(G_{i})$ for its total persistence of degree $1$ .
$\blacksquare$

Denote $e_{n}\coloneqq|E(\mathcal{T}_{n,2})|$ . If $|E(G)|\geq e_{n}$ , then $G$ has $\mathcal{T}_{n,2}$ as a subgraph, with partition classes $V_{1}$ and $V_{2}$ of sizes $|V_{1}|=\lceil n/2\rceil$ and $|V_{2}|=\lfloor n/2\rfloor$ .
$\blacksquare$

Let $d_{i}$ be the number of connected components of $G|_{V_{i}}$ . Then, by Proposition 5,

$\beta^{{\rm FL}}_{1}(G)=(d_{1}-1)(d_{2}-1).$ (3)

We also define what it means for two graphs and two filtrations to be (fiberwise) isomorphic.

Definition 26.

Two graphs $G_{1}$ and $G_{2}$ with vertex sets $V(G_{i})$ and edge sets $E(G_{i})$ are isomorphic, notation $G_{1}\cong G_{2}$ , if there is a bijection $\varphi\colon V(G_{1})\to V(G_{2})$ , such that $\{u_{1},u_{2}\}\in E(G_{1})$ if and only if $\{\varphi(u_{1}),\varphi(u_{2})\}\in E(G_{2}).$ Furthermore, two filtrations $\mathcal{G}^{1}=\bigl{\{}G_{i}^{1}\bigr{\}}_{i=1}^{m}$ and $\mathcal{G}^{2}=\bigl{\{}G_{i}^{2}\bigr{\}}_{i=1}^{m}$ are fiberwise isomorphic if $G_{i}^{1}\cong G_{i}^{2}$ for all $i=1,\ldots,m$ .

First, by Corollary 25, any filtration with a maximal number of bars must contain the Turán graph $\mathcal{T}_{n,2}$ . Moreover, Theorem 16 establishes that the filtration $\mathcal{H}=\bigl{\{}H_{i}\bigr{\}}_{i=1}^{e_{n}}$ from Definition 13 is fiberwise optimal, reducing our problem to maximizing the total persistence of an edgewise filtration of the complete graph, beginning with the Turán graph plus one edge. This is a bit more involved, because we cannot find a fiberwise optimal filtration of the complete graph, as is shown in the following example.

Example 27.

If $|E|=e_{n}+2$ , then one gets optimal degree $1$ homology by adding one edge to $V_{1}$ and one edge to $V_{2}$ (left graph in Figure 6). However, if $|E|=e_{n}+3$ , then optimal degree $1$ homology is obtained by adding all three edges to $V_{1}$ to form a $K_{3}$ (second-to-left graph in Figure 6). It is clear that a filtration of $K_{n}$ cannot contain both graphs.

Figure 6: The graphs from Example 27 and 29.

We can prove the following about the structure of the graphs in an optimal filtration of $K_{n}$ .

Lemma 28.

Let $\mathcal{G}$ be an edgewise filtration $\bigl{\{}G_{i}\bigr{\}}_{i=1}^{\binom{n}{2}}$ of $K_{n}$ with maximal total persistence that includes $\mathcal{T}_{n,2}$ . Then, for $t=1,2$ and $i=e_{n}+1,\ldots,\binom{n-1}{2}+1$ , one of the subgraphs $G_{i}|_{V_{t}}$ consists of isolated vertices and a single component $K_{m}$ , and the other subgraph $G_{i}|_{V_{t}}$ consists of isolated vertices, and a single component with $l$ vertices, such that $K_{l-1}$ is a subgraph of this component.

Example 29.

Cf. Figure 6 for four examples of graphs with the properties from Lemma 28.

Proof.

Suppose that for some $i$ , $E(G_{i})\setminus E(G_{i-1})=\{w_{1},w_{2}\}$ , where $w_{1}$ and $w_{2}$ are isolated vertices in $G_{j-1}|_{V_{1}}$ (without loss of generality). Also assume that $G_{j-1}|_{V_{1}}$ contains a component $C$ of size $|C|>1$ . To maximize total persistence, it is more optimal to connect $w_{1}$ to $C$ , since this allows us to add $|C|-1$ edges of the form $\{w_{1},c\}$ (where $c\in C$ ) without increasing the number of connected components (cf. (3)). Because these additional edges do not decrease the degree $1$ homology, we should add them as early in the filtration as possible to maximize total persistence. Hence, by this same argument, $G_{j-1}|_{V_{2}}$ should be isomorphic to $K_{m}$ and some isolated vertices.

Furthermore, note that we added the restriction $j\leq\binom{n-1}{2}+1$ because Theorem 18 ensures that beyond this point, $\beta^{{\rm FL}}_{1}(G_{j})=0$ . This means that

G_{\binom{n-1}{2}+1}=(K_{1}\sqcup K_{\lceil n/2\rceil-1})\vee(K_{1}\sqcup K_{% \lfloor n/2\rfloor-1}),

(4)

but if $j>\binom{n-1}{2}+1$ , then $G_{j}$ could be any graph containing $G_{\binom{n-1}{2}+1}$ as a subgraph. $\hfill\blacktriangleleft$ Because of this, we restrict our focus to edgewise filtrations of the graph $G_{\binom{n-1}{2}+1}$ from (4).

Moreover, by Lemma 28, we only have to consider filtrations of the described form. We can represent them by a sequence of tuples of the form

\bigl{(}K_{1},K_{1})=\bigl{(}K_{l_{1}},K_{r_{1}}),\bigl{(}K_{l_{2}},K_{r_{2}})% ,\ldots,\bigl{(}K_{l_{c}},K_{r_{c}})=\bigl{(}K_{\lceil n/2\rceil-1},K_{\lfloor n% /2\rfloor-1}\bigr{)},

(5)

such that $l_{i}\geq l_{i-1}$ and $r_{i}\geq r_{i-1}$ . The representation from (5) corresponds to the filtration $\mathcal{G}=\bigl{\{}G_{i}\bigr{\}}_{i=1}^{m}$ , where, for $i\geq 1$ ,

	$\displaystyle G_{e_{n}+\|E(K_{l_{i}})\|+\|E(K_{r_{i}})\|}$	$\displaystyle\cong\biggl{(}K_{l_{i}}\sqcup\bigsqcup_{j=l_{i}+1}^{\lceil n/2% \rceil}K_{1}\biggr{)}\bigvee\biggl{(}K_{r_{i}}\sqcup\bigsqcup_{j=r_{i}+1}^{% \lfloor n/2\rfloor}K_{1}\biggr{)}\text{ and }$
	$\displaystyle G_{e_{n}+\|E(K_{l_{i+1}})\|+\|E(K_{r_{i}})\|}$	$\displaystyle\cong\biggl{(}K_{l_{i+1}}\sqcup\bigsqcup_{j=l_{i}+1}^{\lceil n/2% \rceil}K_{1}\biggr{)}\bigvee\biggl{(}K_{r_{i}}\sqcup\bigsqcup_{j=r_{i}+1}^{% \lfloor n/2\rfloor}K_{1}\biggr{)}.$

In other words, the representation from (5) means that, starting from the Turán graph $\mathcal{T}_{n,2}$ :

1.

we begin adding edges by forming a $K_{l_{2}}$ in $V_{1}$ ,
2.

then add edges to form a $K_{r_{2}}$ in $V_{2}$ ,
3.

increase the sizes of the complete subgraphs in $V_{1}$ and $V_{2}$ by constructing a $K_{l_{3}}$ (containing the smaller $K_{l_{2}}$ ) in $V_{1}$ , a $K_{r_{3}}$ in $V_{2}$ , and so on.

Note that this representation is not unique ( $(K_{3},K_{1})$ is equivalent to $(K_{2},K_{1}),(K_{3},K_{1})$ ).

Figure 7: A filtration and its representation. Here,

\bigvee

denotes the join of the left and right graphs.

Example 30.

In Figure 7, one finds a filtration and a corresponding representation.

Figure 8: A filtration with the same total persistence as the one from Figure 7.

Surprisingly, the optimal strategy is to first construct two large cliques in $V_{1}$ and $V_{2}$ of sizes approximately $\frac{3}{4}|V_{1}|$ and $\frac{3}{4}|V_{2}|$ , respectively, and then, alternating between $V_{1}$ and $V_{2}$ , increase the sizes of the cliques one by one. We prove this in the main result of this section.

Theorem 31.

Let $n\geq 4$ and let $j_{n}\coloneqq\lfloor(3n-2)/8\rfloor$ and $k_{n}\coloneqq\lfloor(3n+7)/8\rfloor$ . Up to fiberwise isomorphism, the edgewise filtration $\mathcal{G}_{n,\max}=\bigl{\{}G_{i}\bigr{\}}_{i=1}^{\binom{n-1}{2}+1}$ of $G_{\binom{n-1}{2}+1}$ with maximal total persistence and a maximum number of bars is given by $G_{i}\cong H_{i}$ (Definition 13) for $i=1,\ldots,e_{n}$ . After $G_{e_{n}}=\mathcal{T}_{n,2}$ , for $n\not\equiv 0\mod 8$ , the filtration is unique up to fiberwise isomorphism and represented by a sequence of tuples (cf. (5)) as follows

\begin{cases}\bigl{(}K_{1},K_{1}\bigr{)},\bigl{(}K_{j_{n}},K_{j_{n}}\bigr{)},% \bigl{(}K_{j_{n}+1},K_{j_{n}+1}\bigr{)},\ldots,\bigl{(}K_{n/2-1},K_{n/2-1}% \bigr{)},&\text{ if }n\equiv 2,4,6\mod 8,\\ \bigl{(}K_{1},K_{1}\bigr{)},\bigl{(}K_{k_{n}},K_{k_{n}-1}\bigr{)},\bigl{(}K_{k% _{n}+1},K_{k_{n}}\bigr{)},\ldots,\bigl{(}K_{(n-1)/2},K_{(n-3)/2}\bigr{)},&% \text{ if }n\equiv 1\mod 2.\end{cases}

If $n\equiv 0\mod 8$ , then there are, up to fiberwise isomorphism, two optimal filtrations, represented by

	$\displaystyle\bigl{(}K_{1},K_{1}\bigr{)},\bigl{(}K_{j_{n}},K_{j_{n}}\bigr{)},% \bigl{(}K_{j_{n}+1},K_{j_{n}+1}\bigr{)},\ldots,\bigl{(}K_{n/2-1},K_{n/2-1}% \bigr{)}\text{ and }$
	$\displaystyle\bigl{(}K_{1},K_{1}\bigr{)},\bigl{(}K_{j_{n}+1},K_{j_{n}+1}\bigr{% )},\bigl{(}K_{j_{n}+2},K_{j_{n}+2}\bigr{)},\ldots,\bigl{(}K_{n/2-1},K_{n/2-1}% \bigr{)}.$

$\blacktriangleright$ Remark 32.

We prove the even case. The proof of the odd case is more or less the same (although the values are slightly different). However, we need to prove that, for any representation as in (5), $l_{i}\geq r_{i}$ for $i=1,\ldots,c$ . In the even case, we may assume this.

See Figure 8 for an example of and the full version [3, B.4] for a proof of this assumption.

Proof.

It follows from Corollary 25 that, for a filtration $\mathcal{G}$ to have a maximum number of bars, we must have $G_{e_{n}}=\mathcal{T}_{n,2}$ . For a filtration $\mathcal{G}$ to also have maximal total persistence, it immediately follows by Theorem 16 that $G_{i}\cong H_{i}$ for $i=1,\ldots,e_{n}$ .

Any filtration $\mathcal{G}$ that we consider in this proof will therefore be such that $G_{i}\cong H_{i}$ for $i=1,\ldots,e_{n}$ . We are interested in the remainder of the filtration, which we can represent by a sequence of tuples as in (5). Within the proof, we will further reduce it by writing

\bigl{(}l_{1},r_{1}\bigr{)},\bigl{(}l_{2},r_{2}\bigr{)},\ldots,\bigl{(}l_{c},r% _{c}\bigr{)}\text{ instead of }\bigl{(}K_{l_{1}},K_{r_{1}}),\bigl{(}K_{l_{2}},% K_{r_{2}}),\ldots,\bigl{(}K_{l_{c}},K_{r_{c}}).

(6)

Furthermore, given a filtration $\mathcal{G}$ represented by $\bigl{(}l_{1},r_{1}\bigr{)},\bigl{(}l_{2},r_{2}\bigr{)},\ldots,\bigl{(}l_{c},r% _{c}\bigr{)}$ , we define its alternation depth $d_{\mathcal{G}}$ as follows:

$\blacksquare$

We let $d_{\mathcal{G}}\coloneqq 1$ if $\bigl{(}l_{i},r_{i}\bigr{)}=\bigl{(}l_{i-1}+1,r_{i-1}+1\bigr{)}$ for all $i=2,\ldots,c$ .
$\blacksquare$

Otherwise, let $d_{\mathcal{G}}\geq 2$ be such that $\bigl{(}l_{i},r_{i}\bigr{)}=\bigl{(}l_{i-1}+1,r_{i-1}+1\bigr{)}$ for all $i=d_{\mathcal{G}}+1,\ldots,c$ , but $\bigl{(}l_{d_{\mathcal{G}}},r_{d_{\mathcal{G}}}\bigr{)}\neq\bigl{(}l_{d_{% \mathcal{G}}-1}+1,r_{d_{\mathcal{G}}-1}+1\bigr{)}$ .

The idea of the proof is to start with a filtration $\mathcal{G}=\bigl{\{}G_{i}\bigr{\}}_{i=1}^{\binom{n-1}{2}+1}$ , with a representation as in (6), and show that we can change the filtration in steps, to obtain in every step a filtration $\mathcal{G}^{\prime}$ such that $T\beta^{{\rm FL}}_{1}\bigl{(}\mathcal{G}^{\prime}\bigr{)}\geq T\beta^{{\rm FL}% }_{1}\bigl{(}\mathcal{G}\bigr{)}$ , and end up with an optimal solution.

Now, writing $n=2p$ , let $\mathcal{G}$ be a filtration, represented by

\bigl{(}1,1)=\bigl{(}l_{1},r_{1}),\bigl{(}l_{2},r_{2}\bigr{)},\ldots,\bigl{(}l% _{c},r_{c})=\bigl{(}n/2-1,n/2-1\bigr{)}=\bigl{(}p-1,p-1\bigr{)}.

We shall show that

1.

If the alternation depth $d_{\mathcal{G}}>j_{n}$ , then we can change $\mathcal{G}$ to a filtration $\mathcal{G^{\prime}}$ such that $d_{\mathcal{G}^{\prime}}<d_{\mathcal{G}}$ and $T\beta^{{\rm FL}}_{1}\bigl{(}\mathcal{G}^{\prime}\bigr{)}\geq T\beta^{{\rm FL}% }_{1}\bigl{(}\mathcal{G}\bigr{)}$ .
2.

If $l_{2}<j_{n}$ , then we can change $\mathcal{G}$ to a filtration $\mathcal{G}^{\prime}$ represented by $\bigl{(}l_{1}^{\prime},r_{1}^{\prime}\bigr{)},\ldots,\bigl{(}l_{c^{\prime}}^{% \prime},r_{c^{\prime}}^{\prime}\bigr{)}$ with $l_{2}^{\prime}=l_{2}+1$ , such that $c^{\prime}=c-1$ or $c^{\prime}=c$ (depending on $\mathcal{G}$ ) and $T\beta^{{\rm FL}}_{1}\bigl{(}\mathcal{G}^{\prime}\bigr{)}\geq T\beta^{{\rm FL}% }_{1}\bigl{(}\mathcal{G}\bigr{)}$ .

For the first part, let $\mathcal{G}$ be a filtration with alternation depth $d_{\mathcal{G}}>j_{n}$ . Its representation, substituting $n$ by $2p$ , is of the form

(1,1),\ldots,(t,u),(v,w),\bigl{(}d_{\mathcal{G}},d_{\mathcal{G}}\bigr{)},\bigl% {(}d_{\mathcal{G}}+1,d_{\mathcal{G}}+1\bigr{)},\ldots,\bigl{(}p-1,p-1\bigr{)}% \text{ with }\bigl{(}v,w\bigr{)}\neq\bigl{(}d_{\mathcal{G}}-1,d_{\mathcal{G}}-% 1\bigr{)}.

Since we assumed that $v\geq w$ , we must have $w<d_{\mathcal{G}}-1$ . We transform $\mathcal{G}$ into a filtration $\mathcal{G}^{\prime}$ which is the same as $\mathcal{G}$ , except that we add an extra alternation step. We consider two cases.

$\blacksquare$

Case $1$ : $v<d_{\mathcal{G}}-1$ . In this case, $\mathcal{G}^{\prime}$ is represented by

$(1,1),\ldots(t,u),(v,w),\bigl{(}d_{\mathcal{G}}-1,d_{\mathcal{G}}-1\bigr{)},% \bigl{(}d_{\mathcal{G}},d_{\mathcal{G}}\bigr{)},\bigl{(}d_{\mathcal{G}}+1,d_{% \mathcal{G}}+1\bigr{)},\ldots,\bigl{(}p-1,p-1\bigr{)}.$
$\blacksquare$

Case $2$ : $v=d_{\mathcal{G}}-1$ . In this case, $\mathcal{G}^{\prime}$ is represented by

$(1,1),\ldots(t,u),\bigl{(}v=d_{\mathcal{G}}-1,d_{\mathcal{G}}-1\bigr{)},\bigl{% (}d_{\mathcal{G}},d_{\mathcal{G}}\bigr{)},\bigl{(}d_{\mathcal{G}}+1,d_{% \mathcal{G}}+1\bigr{)},\ldots,\bigl{(}p-1,p-1\bigr{)}.$

In both cases, we see that $d_{\mathcal{G}^{\prime}}<d_{\mathcal{G}}$ . Moreover, as we show in more detail in [3, B.4],

T\beta^{{\rm FL}}_{1}\bigl{(}\mathcal{G}^{\prime}\bigr{)}-T\beta^{{\rm FL}}_{1% }\bigl{(}\mathcal{G}\bigr{)}=\frac{1}{6}\bigl{(}d_{\mathcal{G}}-1-w\bigr{)}% \bigl{(}d_{\mathcal{G}}-w\bigr{)}\bigl{(}4d_{\mathcal{G}}+2w-3p-2\bigr{)}\geq 0.

(7)

To see that this difference is non-negative, first recall that $w<d_{\mathcal{G}}-1$ , so the first two terms are strictly positive. Furthermore, since $d_{\mathcal{G}}>\lfloor 3p/4-1/4\rfloor$ , we have $d_{\mathcal{G}}\geq\lceil 3p/4\rceil\geq 3p/4$ , so

4d_{\mathcal{G}}+2w-3p-2\geq 2w-2\geq 0,

since $w\geq 1$ . Note that $T\beta^{{\rm FL}}_{1}\bigl{(}\mathcal{G}^{\prime}\bigr{)}-T\beta^{{\rm FL}}_{1% }\bigl{(}\mathcal{G}\bigr{)}=0$ if and only if $w=1$ and $d_{\mathcal{G}}=3p/4$ .

We now show the second part. We let $\mathcal{G}$ be a filtration with representation

(1,1),(j,k),(l,m),\ldots,(p-1,p-1)\text{ with $j\leq 3p/4-1$.}

We transform $\mathcal{G}$ into a filtration $\mathcal{G}^{\prime}$ such that its start is different from $\mathcal{G}$ ’s, but from the tuple $(l,m)$ onwards, $\mathcal{G}$ and $\mathcal{G}^{\prime}$ are the same. We again consider two cases.

$\blacksquare$

Case $1$ : $l>j+1$ . In this case, $\mathcal{G}^{\prime}$ is represented by $(1,1),(j+1,k),(l,m),\ldots,(p-1,p-1).$
$\blacksquare$

Case $2$ : $l=j+1$ . In this case, $\mathcal{G}^{\prime}$ is represented by $(1,1),(j+1=l,m),\ldots,(p-1,p-1).$

In both cases, as we show in more detail in the full version [3, B.4], we have

T\beta^{{\rm FL}}_{1}\bigl{(}\mathcal{G}^{\prime}\bigr{)}-T\beta^{{\rm FL}}_{1% }\bigl{(}\mathcal{G}\bigr{)}=(k-1)\bigl{(}j(p-j-1)-\frac{k}{6}(3p-2k-2)\bigr{)% }\overset{(i)}{\geq}2\bigl{(}(j-k+1)(j-k)\bigr{)}\overset{(ii)}{\geq}0,

(8)

where we use in $(i)$ that $j\leq 3p/4-1$ , and in $(ii)$ that $j\geq k$ . If $n\equiv 2,4,6\mod 8$ , then $j\leq 3p/4-1$ implies that $j\leq\lfloor 3p/4-1\rfloor=\lfloor 3p/4-5/4\rfloor=j_{n}-1$ . If $n\equiv 0\mod 8$ , then $j\leq 3p/4-1=j_{n}$ . Only in this case, and if $j=k=3p/4-1$ , then the inequality is sharp.

Hence, if we start with an arbitrary filtration $\mathcal{G}$ , then we can transform it step by step into a more optimal filtration $\mathcal{G}^{1}$ with $d_{\mathcal{G}^{1}}\leq j_{n}$ , by the first part. Then, by the second part, we can transform $\mathcal{G}^{1}$ step by step into a more optimal filtration $\mathcal{G}^{2}$ that starts with $(1,1),(j_{n},j_{n})$ , with alternation depth $d_{\mathcal{G}^{2}}=j_{n}$ . Hence, $\mathcal{G}^{2}$ is the optimal filtration as described in the statement for $n\equiv 2,4,6\mod 8$ .

In the case that $n\equiv 0\mod 8$ , we saw in the proof of case $1$ and case $2$ , that the filtration $\mathcal{G}^{3}$ starting with $(1,1),\bigl{(}j_{n}+1,j_{n}+1\bigr{)}$ and having alternation depth $d_{\mathcal{G}^{3}}=j_{n}+1$ satisfies $T\beta^{{\rm FL}}_{1}(\mathcal{G}^{3})=T\beta^{{\rm FL}}_{1}(\mathcal{G}^{2})$ , hence both $\mathcal{G}^{2}$ and $\mathcal{G}^{3}$ are optimal. $\hfill\blacktriangleleft$

8 Discussion

In this paper, we have answered several key questions in the context of topological data analysis. However, many questions remain open, and we propose the following conjectures.

Conjecture 33.

If $\mathcal{G}$ is a filtration on $n$ vertices, then the number of intervals in the barcode of $\mathcal{G}$ in homology degree $k$ satisfies $|\mathcal{B}^{{\rm FL}}_{k}(\mathcal{G})|\leq\beta^{{\rm FL}}_{k}(\mathcal{T}_% {n,k+1}).$

Conjecture 34.

The extremal filtrations described in Section 7 achieve the maximal total persistence over any edgewise filtration of flag complexes in homology degree 1.

Proving the latter conjecture likely requires new ideas, as no filtration $\mathcal{G}$ can maximize $\beta^{{\rm FL}}_{1}(G_{i})$ for all $i$ . In fact, extremal values need not be realized by graphs containing Turán graphs as spanning subgraphs, as illustrated by the following example.

Example 35.

Let $n=8$ and $m=16+5$ . Suppose $G$ contains the Turán graph $\mathcal{T}_{8,2}$ . By Proposition 5, we seek to add 5 edges to the Turán graph to maximize the product $(d_{1}-1)(d_{2}-1)$ . It is easy to see that this product can be at most 1. However, by partitioning the vertices as $V=V_{1}\cup V_{2}$ , with $|V_{1}|=3$ and $|V_{2}|=5$ , and adding all edges between $V_{1}$ and $V_{2}$ , we need to add 6 more edges. Adding these as a $K_{4}$ in the larger partition gives $d_{1}=2$ and $d_{2}=1$ ; see Figure 9. The value $2$ is extremal; see Figure 10.

Figure 9: Two graphs

G_{l}

(left) and

G_{r}

(right) such that

\beta^{{\rm FL}}_{1}(G_{l})=1

and

\beta^{{\rm FL}}_{1}(G_{r})=2

.

Finding extremal values of $\mathbb{Z}$ -linear functions defined on simplicial complexes with precisely $n$ vertices and $m$ edges presents a challenging and interesting direction for future research.

Conjecture 36.

Let $\mathbf{G}(n,m)$ denote the collection of graphs on $n$ vertices and $m$ edges. If $G\in\mathbf{G}(n,m)$ and $\beta^{{\rm FL}}_{1}(G)=\max_{H\in\mathbf{G}(n,m)}\beta^{{\rm FL}}_{1}(H)$ , then $G$ contains a complete bipartite spanning subgraph.

Figure 10: The vertical axis is

\beta^{{\rm FL}}_{1}

, and the value

k

along the

x

-axis represents

(n/2)^{2}+k

edges. Here

n

is the number of vertices in the underlying graph;

n=8

(left) and

n=100

(right). The solid curves give the optimal value of

\beta^{{\rm FL}}_{1}(G)

for any graph

G

containing a complete bipartite spanning subgraph, and the dashed line is an upper bound derived from the proof of Theorem 10 in conjuction with Lemma 17 (details omitted).

References

[1] Michał Adamaszek. Extremal problems related to Betti numbers of flag complexes. Discrete Applied Mathematics, 173:8–15, 2014. doi:10.1016/J.DAM.2014.04.006.
[2] Ulrich Bauer. Ripser: efficient computation of Vietoris-Rips persistence barcodes. Journal of Applied and Computational Topology, 5(3):391–423, 2021. doi:10.1007/S41468-021-00071-5.
[3] Lies Beers and Magnus Bakke Botnan. Extremal Betti Numbers and Persistence in Flag Complexes, 2025. arXiv:2502.21294.
[4] Anders Björner and Gil Kalai. An extended Euler-Poincaré theorem, 1988.
[5] Magnus Botnan and Michael Lesnick. An introduction to multiparameter persistence. In Representations of Algebras and Related Structures, pages 77–150. EMS Press, 2023.
[6] Gary Chartrand and Ping Zhang. A first course in graph theory. Courier Corporation, 2013.
[7] Frédéric Chazal and Steve Yann Oudot. Towards persistence-based reconstruction in Euclidean spaces. In Proceedings of the twenty-fourth annual symposium on Computational geometry, pages 232–241, 2008.
[8] Tamal Krishna Dey and Yusu Wang. Computational topology for data analysis. Cambridge University Press, 2022.
[9] Herbert Edelsbrunner and János Pach. Maximum Betti numbers of Čech complexes. In 40th International Symposium on Computational Geometry (SoCG 2024). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.SoCG.2024.53.
[10] Michael Goff. Extremal Betti numbers of Vietoris–Rips complexes. Discrete and Computational Geometry, 46(1):132, 2011. doi:10.1007/s00454-010-9274-z.
[11] Dmitry N Kozlov. Convex hulls of $f$ -and $\beta$ -vectors. Discrete & Computational Geometry, 18:421–431, 1997. doi:10.1007/PL00009326.

[bib.bib1] [1] Michał Adamaszek. Extremal problems related to Betti numbers of flag complexes. Discrete Applied Mathematics, 173:8–15, 2014. doi:10.1016/J.DAM.2014.04.006.

[bib.bib2] [2] Ulrich Bauer. Ripser: efficient computation of Vietoris-Rips persistence barcodes. Journal of Applied and Computational Topology, 5(3):391–423, 2021. doi:10.1007/S41468-021-00071-5.

[bib.bib3] [3] Lies Beers and Magnus Bakke Botnan. Extremal Betti Numbers and Persistence in Flag Complexes, 2025. arXiv:2502.21294.

[bib.bib4] [4] Anders Björner and Gil Kalai. An extended Euler-Poincaré theorem, 1988.

[bib.bib5] [5] Magnus Botnan and Michael Lesnick. An introduction to multiparameter persistence. In Representations of Algebras and Related Structures, pages 77–150. EMS Press, 2023.

[bib.bib6] [6] Gary Chartrand and Ping Zhang. A first course in graph theory. Courier Corporation, 2013.

[bib.bib7] [7] Frédéric Chazal and Steve Yann Oudot. Towards persistence-based reconstruction in Euclidean spaces. In Proceedings of the twenty-fourth annual symposium on Computational geometry, pages 232–241, 2008.

[bib.bib8] [8] Tamal Krishna Dey and Yusu Wang. Computational topology for data analysis. Cambridge University Press, 2022.

[bib.bib9] [9] Herbert Edelsbrunner and János Pach. Maximum Betti numbers of Čech complexes. In 40th International Symposium on Computational Geometry (SoCG 2024). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.SoCG.2024.53.

[bib.bib10] [10] Michael Goff. Extremal Betti numbers of Vietoris–Rips complexes. Discrete and Computational Geometry, 46(1):132, 2011. doi:10.1007/s00454-010-9274-z.

[bib.bib11] [11] Dmitry N Kozlov. Convex hulls of $f$ -and $\beta$ -vectors. Discrete & Computational Geometry, 18:421–431, 1997. doi:10.1007/PL00009326.

	$\displaystyle\bigl{\|}E\bigl{(}\overline{G}_{i}-N_{\overline{G}_{i}}[v_{i+1}])% \bigr{\|}$
	$\displaystyle\overset{(i)}{\leq}\|E(\overline{G}_{i})\|-\biggl{(}\deg_{\overline% {G}_{i}}(v_{i+1})+\biggl{\lceil}\frac{(u^{\prime}-1)\deg_{\overline{G}_{i}}(v_% {i+1})}{2}\biggr{\rceil}\biggr{)}$
	$\displaystyle\overset{(ii)}{\leq}\|E(\overline{G}_{i})\|-\biggl{(}u-i+\biggl{% \lceil}\frac{(u-i-1)(u-i)}{2}\biggr{\rceil}\biggr{)}=\|E(\overline{G}_{i})\|-% \sum_{j=1}^{u-i}j$
	$\displaystyle\overset{(iii)}{\leq}\|E(\overline{G})\|-\sum_{j=u-i+1}^{u}j-\sum_{% j=1}^{u-i}j=\|E(\overline{G})\|-\sum_{j=1}^{u}j=\overline{m}-\left(\frac{u(u+1)}% {2}\right).$

Extremal Betti Numbers and Persistence in Flag Complexes

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

▶ Remark 1.

1.1 Overview and contributions

1.2 Related work

2 Background

Graphs and Simplicial Complexes.

Homology.

Persistent Homology.

Example 2.

2.1 Elementary homological properties

Lemma 3.

Lemma 4.

Proposition 5.

Proof.

2.2 Turán graphs

Definition 6.

Example 7.

Proposition 8.

3 The maximum value of 𝜷𝒌⁢(𝑿⁢(𝑮))

Lemma 9.

Theorem 10.

Proof.

Corollary 11.

4 The maximum value of 𝜷𝒌⁢(𝑿⁢(𝑮)) for |𝑬⁢(𝑮)|≤|𝑬⁢(𝓣𝒏,𝒌+𝟏)|

Corollary 12.

Proof.

Definition 13.

Example 14.

Lemma 15.

Theorem 16.

Proof.

5 Tight bounds on the vanishing of homology and extremal interval lengths

Lemma 17.

Proof.

Theorem 18.

Proof.

▶ Remark 19.

Example 20.

Corollary 21.

Proof.

6 The maximum value of |𝜷𝟏𝐅𝐋⁢(𝓖)|

Proposition 22.

Proof.

▶ Remark 23.

Proposition 24.

Proof.

Corollary 25.

7 Extremal filtrations for degree 1 persistent homology

Definition 26.

Example 27.

Lemma 28.

Example 29.

Proof.

Example 30.

Theorem 31.

▶ Remark 32.

Proof.

8 Discussion

Conjecture 33.

Conjecture 34.

Example 35.

Conjecture 36.

References

$\blacktriangleright$ Remark 1.

3 The maximum value of $\beta_{k}(X(G))$

4 The maximum value of $\beta_{k}(X(G))$ for $|E(G)|\leq|E(\mathcal{T}_{n,k+1})|$

$\blacktriangleright$ Remark 19.

6 The maximum value of $|\beta^{{\rm FL}}_{1}(\mathcal{G})|$

$\blacktriangleright$ Remark 23.

$\blacktriangleright$ Remark 32.