Search

We show that the decision problem of determining whether a given (abstract simplicial) k-complex has a geometric embedding in ℝd is complete for the Existential Theory of the Reals for all d ≥ 3 and k ∈ {d-1, d} by reducing from pseudoline stretchability. Consequently, the problem is polynomial time equivalent to determining whether a polynomial equation system has a real solution. Moreover, this implies NP-hardness and constitutes the first hardness result for the algorithmic problem of geometrically embedding (abstract simplicial) complexes. This complements recent breakthroughs for the computational complexity of piece-wise linear embeddability [Matoušek, Sedgwick, Tancer, and Wagner, J. ACM 2018, and de Mesmay, Rieck, Sedgwick and Tancer, J. ACM 2020] and establishes connections to computational topology. [ABSTRACT FROM AUTHOR]

Simplicial complexes are higher-order combinatorial structures which have been used to represent real-world complex systems. In this paper, we focus on the local patterns in simplicial complexes called simplets, a generalization of graphlets. We study the problem of counting simplets of a given size in a given simplicial complex. For this problem, we extend a sampling algorithm based on color coding, from graphs to simplicial complexes, with essential technical novelty. We theoretically analyze our proposed algorithm named SC3, showing its correctness, unbiasedness, convergence, and time/space complexity. Through extensive experiments on sixteen real-world datasets, we show the superiority of SC3 in terms of accuracy, speed, and scalability, compared to the baseline methods. We use the counts given by SC3 for simplicial complex analysis, especially for characterization, which is further used for simplicial complex clustering, where SC3 shows a strong ability of characterization with domain-based similarity. Additionally, we explore a variant of simplet counting (specifically, estimating the relative counts of simplets) under realistic scenarios where the entire simplicial complex is not provided at once but can only be partially accessed, for instance, through a limited number of API calls. For such scenarios, we propose a random-walk-based sampling algorithm, SCRW, and analyze its theoretical properties. In our experiments, SCRW requires, on average, 16.5 × less memory than SC3, while the speed-accuracy trade-offs provided by the two methods are comparable. [ABSTRACT FROM AUTHOR]

Graph convolutional neural networks (GCNs) are deep learning methods for processing graph-structured data. Usually, GCNs mainly consider pairwise connections and ignore higher-order interactions between nodes. Recently, simplices have been shown to encode not only pairwise relations between nodes but also encode higher-order interactions between nodes. Researchers have been concerned with how to design simplicial-based convolutional neural networks. The existing simplicial neural networks can achieve good performance in tasks such as missing value imputation, graph classification, and node classification. However, due to issues of gradient vanishing, over-smoothing, and over-fitting, they are typically limited to very shallow models. Therefore, we innovatively propose a simplicial convolutional neural network for deep learning (DeepSCNN). Firstly, simplicial edge sampling technology (SES) is introduced to prevent over-fitting caused by deepening network layers. Subsequently, initial residual connection technology is added to simplicial convolutional layers. Finally, to verify the validity of the DeepSCNN, we conduct missing data imputation and node classification experiments on citation networks. Additionally, we compare the experimental performance of the DeepSCNN with that of simplicial neural networks (SNN) and simplicial convolutional networks (SCNN). The results show that our proposed DeepSCNN method outperforms SNN and SCNN. [ABSTRACT FROM AUTHOR]

Coupled map lattices are a popular and computationally simpler model of pattern formation in nonlinear systems. In this work, we investigate three-site interactions with linear multiplicative coupling in one-dimensional coupled logistic maps that cannot be decomposed into pairwise interactions. We observe the transition to synchronization and the transition to long-range order in space. We coarse-grain the phase space in regions and denote them by spin values. We use two quantifiers the flip rate F(t) that quantify departure from expected band-periodicity as an order parameter. We also study a non-Markovian quantity, known as persistence P(t) to study dynamic phase transitions. Following transitions are observed. (a) Transition to two band attractor state: At this transition F(t) as well as P(t) shows a power-law decay in the range of coupling parameters. Here all sites reach one of the bands. The F(t) as well as P(t) decays as power-law with the decay exponent δ1=0.46 and η1=0.28, respectively. (b) The transition from a fluctuating chaotic state to a homogeneous synchronized fixed point: Here both the quantifiers F(t) and P(t) show power-law decay with decay exponent δ2=1 and η2=0.11, respectively. We compare the transitions with the case, where pairwise interactions are also present. The spatiotemporal evolution is analyzed as the coupling parameter is varied. [ABSTRACT FROM AUTHOR]

Abstract The design of the novel metaheuristic method, called Topological Variable Neighborhood Search, is presented and its theoretical properties are elaborated. The proposed metaheuristic method is implemented, applied to several well-known NP-hard problems on graphs (metric dimension problem, roman domination problem and maximum betweeness problem) and compared with the relevant optimization methods for these problems. The obtained experimental results clearly show that the proposed method achieves a significant improvement for the investigated problems and outperforms other methods that participated in the comparison (number of successfully solved problems is increased by 11.5%, 3% and 31.8%, respectively). In particular, it was shown that the Topological Variable Neighborhood Search is consistently better than the classical Variable Neighborhood Search.

The design of the novel metaheuristic method, called Topological Variable Neighborhood Search, is presented and its theoretical properties are elaborated. The proposed metaheuristic method is implemented, applied to several well-known NP-hard problems on graphs (metric dimension problem, roman domination problem and maximum betweeness problem) and compared with the relevant optimization methods for these problems. The obtained experimental results clearly show that the proposed method achieves a significant improvement for the investigated problems and outperforms other methods that participated in the comparison (number of successfully solved problems is increased by 11.5%, 3% and 31.8%, respectively). In particular, it was shown that the Topological Variable Neighborhood Search is consistently better than the classical Variable Neighborhood Search. [ABSTRACT FROM AUTHOR]

The increasing prevalence of relational data describing interactions among a target population has motivated a wide literature on statistical network analysis. In many applications, interactions may involve more than two members of the population and this data is more appropriately represented by a hypergraph. In this article, we present a model for hypergraph data that extends the well-established latent space approach for graphs and, by drawing a connection to constructs from computational topology, we develop a model whose likelihood is inexpensive to compute. A delayed acceptance MCMC scheme is proposed to obtain posterior samples and we rely on Bookstein coordinates to remove the identifiability issues associated with the latent representation. We theoretically examine the degree distribution of hypergraphs generated under our framework and, through simulation, we investigate the flexibility of our model and consider estimation of predictive distributions. Finally, we explore the application of our model to two real-world datasets. for this article are available online. [ABSTRACT FROM AUTHOR]

Developing an algorithm for computing the Betti numbers of semi-algebraic sets with singly exponential complexity has been a holy grail in algorithmic semi-algebraic geometry and only partial results are known. In this paper we consider the more general problem of computing the image under the homology functor of a continuous semi-algebraic map f : X → Y between closed and bounded semi-algebraic sets. For every fixed ℓ ≥ 0 we give an algorithm with singly exponential complexity that computes bases of the homology groups H i (X) , H i (Y) (with rational coefficients) and a matrix with respect to these bases of the induced linear maps H i (f) : H i (X) → H i (Y) , 0 ≤ i ≤ ℓ . We generalize this algorithm to more general (zigzag) diagrams of continuous semi-algebraic maps between closed and bounded semi-algebraic sets and give a singly exponential algorithm for computing the homology functors on such diagrams. This allows us to give an algorithm with singly exponential complexity for computing barcodes of semi-algebraic zigzag persistent homology in small dimensions. [ABSTRACT FROM AUTHOR]

Let S = K [ x 1 , ... , x n ] , where K is a field, and t i (S / I) denotes the maximal shift in the minimal graded free S-resolution of the graded algebra S/I at degree i, where I is an edge ideal. In this paper, we prove that if t b (S / I) ≥ ⌈ 3 b 2 ⌉ for some b ≥ 0 , then the subadditivity condition t a + b (S / I) ≤ t a (S / I) + t b (S / I) holds for all a ≥ 0 . In addition, we prove that t a + 4 (S / I) ≤ t a (S / I) + t 4 (S / I) for all a ≥ 0 (the case b = 0 , 1 , 2 , 3 is known). We conclude that if the projective dimension of S/I is at most 9, then I satisfies the subadditivity condition. [ABSTRACT FROM AUTHOR]

To every simple toric ideal I T one can associate the strongly robust simplicial complex Δ T , which determines the strongly robust property for all ideals that have I T as their bouquet ideal. We show that for the simple toric ideals of monomial curves in A s , the strongly robust simplicial complex Δ T is either { ∅ } or contains exactly one 0-dimensional face. In the case of monomial curves in A 3 , the strongly robust simplicial complex Δ T contains one 0-dimensional face if and only if the toric ideal I T is a complete intersection ideal with exactly two Betti degrees. Finally, we provide a construction to produce infinitely many strongly robust ideals with bouquet ideal the ideal of a monomial curve and show that they are all produced this way. [ABSTRACT FROM AUTHOR]

Techniques based on kth order Hodge Laplacian operators Lk are widely used to describe the topology as well as the governing dynamics of high-order systems modeled as simplicial complexes. In all of them, it is required to solve a number of least-squares problems with Lk as coefficient matrix, for example, in order to compute some portions of the spectrum or integrate the dynamical system, thus making a fast and efficient solver for the least-squares problems highly desirable. To this aim, we introduce the notion of an optimal weakly collapsible subcomplex used to construct an effective sparse Cholesky-like preconditioner for Lk that exploits the topological structure of the simplicial complex. The performance of the preconditioner is tested for the conjugate gradient method for least-squares problems (CGLS) on a variety of simplicial complexes with different dimensions and edge densities. We show that, for sparse simplicial complexes, the new preconditioner significantly reduces the condition number of Lk and performs better than the standard incomplete Cholesky factorization. [ABSTRACT FROM AUTHOR]

In this article we mainly study linear codes over F 2 n and their binary subfield codes. We construct linear codes over F 2 n whose defining sets are the certain subsets of F 2 n m obtained from mathematical objects called simplicial complexes. We will consider simplicial complexes with one maximal element. The relation of the weights of codewords in two special codes obtained from simplicial complexes is illustrated by using LFSR sequences. And then we determine the parameters of these codes with the help of Boolean functions. As a result, we obtain five infinite families of distance optimal codes and give sufficient conditions for these codes to be minimal. [ABSTRACT FROM AUTHOR]

Robin Forman’s highly influential 2002 paper A User’s Guide to Discrete Morse Theory presents an overview of the subject in a very readable manner. As a proof of concept, the author determines the topology (homotopy type) of the abstract simplicial complex of disconnected graphs of order n (which was previously done by Victor Vassiliev using classical topological methods) using discrete Morse theoretic techniques, which are purely combinatorial in nature. The techniques involve the construction (and verification) of a discrete gradient vector field on the complex. However, the verification part relies on a claim that does not seem to hold. In this note, we provide a couple of counterexamples against this specific claim. We also provide an alternative proof of the bigger claim that the constructed discrete vector field is indeed a gradient vector field. Our proof technique relies on a key observation which is not specific to the problem at hand, and thus is applicable while verifying a constructed discrete vector field is a gradient one in general.

We consider the homotopy theory of polyhedral products arising from the operation of stellar subdivision on simplicial complexes. In the special case of polyhedral products formed from pairs where the 's are simply connected spheres, information is deduced about the growth of the rational and torsion homotopy groups. [ABSTRACT FROM AUTHOR]

We investigate the Buchstaber invariant of the skeletons of simplices for a prime number and compare such invariants for different values of . For , the invariant is the real Buchstaber invariant. Our findings reveal that their values are generally distinct. Additionally, we determine or estimate the Buchstaber invariants of certain universal simplicial complexes . [ABSTRACT FROM AUTHOR]

Methods used in topological data analysis naturally capture higher-order interactions in point cloud data embedded in a metric space. This methodology was recently extended to data living in an information space, by which we mean a space measured with an information theoretical distance. One such setting is a finite collection of discrete probability distributions embedded in the probability simplex measured with the relative entropy (Kullback–Leibler divergence). More generally, one can work with a Bregman divergence parameterized by a different notion of entropy. While theoretical algorithms exist for this setup, there is a paucity of implementations for exploring and comparing geometric-topological properties of various information spaces. The interest of this work is therefore twofold. First, we propose the first robust algorithms and software for geometric and topological data analysis in information space. Perhaps surprisingly, despite working with Bregman divergences, our design reuses robust libraries for the Euclidean case. Second, using the new software, we take the first steps towards understanding the geometric-topological structure of these spaces. In particular, we compare them with the more familiar spaces equipped with the Euclidean and Fisher metrics. [ABSTRACT FROM AUTHOR]

The classical Shapley value for cooperative games determines a payoff vector considering that the formation of the grand coalition is made by incorporating players one by one. Later, this method was generalized for games with restricted cooperation by several known mathematical structures: partitions, graphs, convex geometries, antimatroids, matroids or simplicial complexes. In this paper we consider games over simplicial complex with an extra information about the relationships of the agents, a filtration of the complex. Filtrations are very known simplicial structures in the social and neuronal networks. We propose a Shapley value for these situations and an axiomatization. [ABSTRACT FROM AUTHOR]

A family Δ of subsets of { 1 , 2 , … , n } is a simplicial complex if all subsets of F are in Δ for any F ∈ Δ , and the element of Δ is called the face of Δ. Let V (Δ) = ⋃ F ∈ Δ F. A simplicial complex Δ is a near-cone with respect to an apex vertex v ∈ V (Δ) if for every face F ∈ Δ , the set (F \ { w }) ∪ { v } is also a face of Δ for every w ∈ F. Denote by f i (Δ) = | { A ∈ Δ : | A | = i + 1 } | and h i (Δ) = | { A ∈ Δ : | A | = i + 1 , n ∉ A } | for every i, and let link Δ (v) = { E : E ∪ { v } ∈ Δ , v ∉ E } for every v ∈ V (Δ). Assume that p is a prime and k ⩾ 2 is an integer. In this paper, some extremal problems on k-wise L-intersecting families for simplicial complexes are considered. (i) Let L = { l 1 , l 2 , … , l s } be a subset of s nonnegative integers. If F = { F 1 , F 2 , … , F m } is a family of faces of the simplicial complex Δ such that | F i 1 ∩ F i 2 ∩ ⋯ ∩ F i k | ∈ L for any collection of k distinct sets from F , then m ⩽ (k - 1) ∑ i = - 1 s - 1 f i (Δ). In addition, if the size of every member of F belongs to the set K : = { k 1 , k 2 , … , k r } with min K > s - r , then m ⩽ (k - 1) ∑ i = s - r s - 1 f i (Δ). (ii) Let L = { l 1 , l 2 , … , l s } and K = { k 1 , k 2 , … , k r } be two disjoint subsets of { 0 , 1 , … , p - 1 } such that min K > s - 2 r + 1. Assume that Δ is a simplicial complex with n ∈ V (Δ) and F = { F 1 , F 2 , … , F m } is a family of faces of Δ such that | F j | (mod p) ∈ K for every j and | F i 1 ∩ F i 2 ∩ ⋯ ∩ F i k | (mod p) ∈ L for any collection of k distinct sets from F. Then m ⩽ (k - 1) ∑ i = s - 2 r s - 1 h i (Δ). (iii) Let L = { l 1 , l 2 , … , l s } be a subset of { 0 , 1 , … , p - 1 }. Assume that Δ is a near-cone with apex vertex v and F = { F 1 , F 2 , … , F m } is a family of faces of Δ such that | F j | (mod p) ∉ L for every j and | F i 1 ∩ F i 2 ∩ ⋯ ∩ F i k | (mod p) ∈ L for any collection of k distinct sets from F. Then m ⩽ (k - 1) ∑ i = - 1 s - 1 f i (link Δ (v)). [ABSTRACT FROM AUTHOR]

This is the first of a series of papers that develop a systematic bridge between constructions in discrete mathematics and the corresponding continuous analogs. In this paper, we establish an equivalence between Forman's discrete Morse theory on a simplicial complex and the continuous Morse theory (in the sense of any known non-smooth Morse theory) on the associated order complex via the Lovász extension. Furthermore, we propose a new version of the Lusternik–Schnirelman category on abstract simplicial complexes to bridge the classical Lusternik–Schnirelman theorem and its discrete analog on finite complexes. More generally, we can suggest a discrete Morse theory on hypergraphs by employing piecewise-linear (PL) Morse theory and Lovász extension, hoping to provide new tools for exploring the structure of hypergraphs. [ABSTRACT FROM AUTHOR]

The aim of this paper is to extend Sperner's lemma for a new class of complexes, called n-Sperner. Next, we consider a topological version of Sperner's lemma, which leads to characterization of the covering dimension and KKM-principle. Finally, for an arbitrary topological space a new dimension is defined. [ABSTRACT FROM AUTHOR]

Quantum walks have emerged as a transformative paradigm in quantum information processing and can be applied to various graph problems. This study explores discrete-time quantum walks on simplicial complexes, a higher-order generalization of graph structures. Simplicial complexes, encoding higher-order interactions through simplices, offer a richer topological representation of complex systems. Since the conventional classical random walk cannot directly detect community structures, we present a quantum walk algorithm to detect higher-order community structures called simplicial communities. We utilize the Fourier coin to produce entangled translation states among adjacent simplices in a simplicial complex. The potential of our quantum algorithm is tested on Zachary's karate club network. This study may contribute to understanding complex systems at the intersection of algebraic topology and quantum walk algorithms. [ABSTRACT FROM AUTHOR]

Each connected graded, graded-commutative algebra A of finite type over a field k of characteristic zero defines a complex of finitely generated, graded modules over a symmetric algebra, whose homology graded modules are called the (higher) Koszul modules of A. In this note, we investigate the geometry of the support loci of these modules, called the resonance schemes of the algebra. When A = k ⟨ Δ ⟩ is the exterior Stanley–Reisner algebra associated to a finite simplicial complex Δ , we show that the resonance schemes are reduced. We also compute the Hilbert series of the Koszul modules and give bounds on the regularity and projective dimension of these graded modules. This leads to a relationship between resonance and Hilbert series that generalizes a known formula for the Chen ranks of a right-angled Artin group. [ABSTRACT FROM AUTHOR]

We study ring-theoretic properties of the Stanley–Reisner rings of simplicial complexes that undergo the interval subdivisions. In particular, we establish results concerning computational description of dimension, Hilbert series, multiplicity, local cohomology, depth and regularity of the Stanley–Reisner ring of interval subdivided simplicial complex. We also prove results regarding the non-vanishing of graded Betti numbers and bounds on Betti numbers for these Stanley–Reisner rings. [ABSTRACT FROM AUTHOR]

It is shown that the Ranicki–Weiss assembly functor, going from chain complex valued presheaves on a simplicial complex to comodules over its Alexander–Whitney coalgebra, factors fully faithfully through the category of comodules over its Steenrod cup-i coalgebra. [ABSTRACT FROM AUTHOR]

Ecosystems are nowadays a dominant organizational form in the digital age. But this construct lacks consensus on its empirical scope, its key theoretical features and its theoretical roots. The paper proposes an integrative framework as well as a method and a tool for calculating an ecosystem based on simplicial complexes and the HYPE platform. It concludes that a data-driven and visualization approach is needed to the study of the dynamic, emergent and adaptive dimensions of today's platform-based ecosystems. [ABSTRACT FROM AUTHOR]

Abstract Higher-order networks are widely used to describe complex systems in which interactions can involve more than two entities at once. In this paper, we focus on inclusion within higher-order networks, referring to situations where specific entities participate in an interaction, and subsets of those entities also interact with each other. Traditional modeling approaches to higher-order networks tend to either not consider inclusion at all (e.g., hypergraph models) or explicitly assume perfect and complete inclusion (e.g., simplicial complex models). To allow for a more nuanced assessment of inclusion in higher-order networks, we introduce the concept of “simpliciality” and several corresponding measures. Contrary to current modeling practice, we show that empirically observed systems rarely lie at either end of the simpliciality spectrum. In addition, we show that generative models fitted to these datasets struggle to capture their inclusion structure. These findings suggest new modeling directions for the field of higher-order network science.

Higher-order networks are widely used to describe complex systems in which interactions can involve more than two entities at once. In this paper, we focus on inclusion within higher-order networks, referring to situations where specific entities participate in an interaction, and subsets of those entities also interact with each other. Traditional modeling approaches to higher-order networks tend to either not consider inclusion at all (e.g., hypergraph models) or explicitly assume perfect and complete inclusion (e.g., simplicial complex models). To allow for a more nuanced assessment of inclusion in higher-order networks, we introduce the concept of "simpliciality" and several corresponding measures. Contrary to current modeling practice, we show that empirically observed systems rarely lie at either end of the simpliciality spectrum. In addition, we show that generative models fitted to these datasets struggle to capture their inclusion structure. These findings suggest new modeling directions for the field of higher-order network science. [ABSTRACT FROM AUTHOR]

Let Δ be an (abstract) simplicial complex on n vertices. One can define the Artinian monomial algebra A (Δ) = k [ x 1 , ... , x n ] / 〈 x 1 2 , ... , x n 2 , I Δ 〉 , where k is a field of characteristic 0 and I Δ is the Stanley-Reisner ideal associated to Δ. In this paper, we aim to characterize the Weak Lefschetz Property (WLP) of A (Δ) in terms of the simplicial complex Δ. We are able to completely analyze when the WLP holds in degree 1, complementing work by Migliore, Nagel and Schenck on the WLP for quotients by quadratic monomials. We give a complete characterization of all 2-dimensional pseudomanifolds Δ such that A (Δ) satisfies the WLP. We also construct Artinian Gorenstein algebras that fail the WLP by combining our results and the standard technique of Nagata idealization. [ABSTRACT FROM AUTHOR]

In this paper, we first give two new methods for constructing self-orthogonal codes from known self-orthogonal codes. On the basis of this, we construct four infinite classes of binary self-orthogonal codes. Moreover, we also determine their weight distributions and the minimum distances of their dual codes. Furthermore, we present a class of optimal linear codes and a class of almost optimal linear codes with respect to the Sphere Packing Bound. [ABSTRACT FROM AUTHOR]

In this paper, we study almost Cohen–Macaulay bipartite graphs. In particular, we prove that if G is an almost Cohen–Macaulay bipartite graph with at least one vertex of positive degree, then there is a vertex of deg(v) ≤ 2. In particular, if G is an almost Cohen–Macaulay bipartite graph and u is a vertex of degree one of G and v its adjacent vertex, then G∖{v} is almost Cohen–Macaulay. Also, we show that an unmixed Ferrers graph is almost Cohen–Macaulay if and only if it is connected in codimension two. Moreover, we give some examples. [ABSTRACT FROM AUTHOR]

In this article, we construct linear codes over the commutative non-unital ring I of size four. We obtain their Lee-weight distributions and study their binary Gray images. Under certain mild conditions, these classes of binary codes are minimal and self-orthogonal. All codes in this article are few-weight codes. Besides, an infinite class of these binary codes consists of distance optimal codes with respect to the Griesmer bound. [ABSTRACT FROM AUTHOR]