Search

Nowadays, the users’ privacy concerns mandate data publishers to protect privacy by anonymizing the data before sharing it with data consumers. Thus, the ultimate goal of privacy-preserving representation learning is to protect user privacy while ensuring the utility, e.g., the accuracy of the published data, for future tasks and usages. Privacy-preserving embeddings are usually functions that are encoded to low-dimensional vectors to protect privacy while preserving important semantic information about an input text. We demonstrate that these embeddings still leak private information, even though the low dimensional embeddings encode generic semantics. In this dissertation, we first develop two classes of attacks, i.e., adversarial classification (AC) attack and adversarial generation (AG) attack, to study the new threats for these embeddings. In particular, the threats are (1) these embeddings may reveal sensitive attributes letting alone if they explicitly exist in the input text, and (2) the embedding vectors can be partially recovered via generation models. We further propose a semi-supervised generative adversarial network that inverts the given embeddings back to the sensitive raw text inputs via querying the model. This approach can produce higher-performing adversary models than other AC and AG baselines. Besides, we argue that privacy protection of privacy-preserving representation learning breaks during inference with model partitioning. Specifically, the hidden representations are easy to be eavesdropped during uploading the data from the local devices to the cloud. Based on the aforementioned two attack models, i.e., AC and AG, we correspondingly propose two defenses: defending the adversarial classification (DAC) and defending the adversarial generation (DAG). Both methods optimally modify a subpopulation of the neural representations that are subject to maximally decreasing the adversary’s ability. The representations trained with this bilevel optimiz

We show that the decision problem of determining whether a given (abstract simplicial) k-complex has a geometric embedding in Rd is complete for the Existential Theory of the Reals for all d ≥ 3 and k ∈ {d− 1, d}. Consequently, the problem is polynomial time equivalent to determining whether a polynomial equation system has a real solution and other important problems from various fields related to packing, Nash equilibria, minimum convex covers, the Art Gallery Problem, continuous constraint satisfaction problems, and training neural networks. Moreover, this implies NP-hardness and constitutes the first hardness result for the algorithmic problem of geometric embedding (abstract simplicial) complexes. This complements recent breakthroughs for the computational complexity of piece-wise linear embeddability.

Variational auto-encoders (VAEs) are deep generative models used for unsupervised learning, however their standard version is not topology-aware in practice since the data topology may not be taken into consideration. In this paper, we propose two different approaches with the aim to preserve the topological structure between the input space and the latent representation of a VAE. Firstly, we introduce InvMap-VAE as a way to turn any dimensionality reduction technique, given an embedding it produces, into a generative model within a VAE framework providing an inverse mapping into original space. Secondly, we propose the Witness Simplicial VAE as an extension of the simplicial auto-encoder to the variational setup using a witness complex for computing the simplicial regularization, and we motivate this method theoretically using tools from algebraic topology. The Witness Simplicial VAE is independent of any dimensionality reduction technique and together with its extension, Isolandmarks Witness Simplicial VAE, preserves the persistent Betti numbers of a dataset better than a standard VAE., QC 20230425

Geometric realization of simplicial complexes makes them a unique representation of complex systems. The existence of local continuous spaces at the simplices level with global discrete connectivity between simplices makes the analysis of dynamical systems on simplicial complexes a challenging problem. In this work, we provide some examples of complex systems in which this representation would be a more appropriate model of real-world phenomena. Here, we generalize the concept of metaplexes to embrace that of geometric simplicial complexes, which also includes the definition of dynamical systems on them. A metaplex is formed by regions of a continuous space of any dimension interconnected by sinks and sources that works controlled by discrete (graph) operators. The definition of simplicial metaplexes given here allows the description of the diffusion dynamics of this system in a way that solves the existing problems with previous models. We make a detailed analysis of the generalities and possible extensions of this model beyond simplicial complexes, e.g., from polytopal and cell complexes to manifold complexes, and apply it to a real-world simplicial complex representing the visual cortex of a macaque., M.M. and E.E. acknowledge support from Project OLGRA (PID2019-107603GB-I00) funded by the Spanish Ministry of Science and Innovation, as well as by the Maria de Maeztu project CEX2021-001164-M funded by the MCIN/AEI/10.13039/501100011033. G.E.-R acknowledges support from the project macroKNIGHTs (PID2022-143012NA-100) funded by the Spanish Ministry of Science and Innovation., Peer Reviewed, Postprint (published version)

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}. Consequently, the problem is polynomial time equivalent to determining whether a polynomial equation system has a real solution and other important problems from various fields related to packing, Nash equilibria, minimum convex covers, the Art Gallery Problem, continuous constraint satisfaction problems, and training neural networks. Moreover, this implies NP-hardness and constitutes the first hardness result for the algorithmic problem of geometric embedding (abstract simplicial) complexes. This complements recent breakthroughs for the computational complexity of piece-wise linear embeddability.

Geometric realization of simplicial complexes makes them a unique representation of complex systems. The existence of local continuous spaces at the simplices level with global discrete connectivity between simplices makes the analysis of dynamical systems on simplicial complexes a challenging problem. In this work, we provide some examples of complex systems in which this representation would be a more appropriate model of real-world phenomena. Here, we generalize the concept of metaplexes to embrace that of geometric simplicial complexes, which also includes the definition of dynamical systems on them. A metaplex is formed by regions of a continuous space of any dimension interconnected by sinks and sources that works controlled by discrete (graph) operators. The definition of simplicial metaplexes given here allows the description of the diffusion dynamics of this system in a way that solves the existing problems with previous models. We make a detailed analysis of the generalities and possible extensions of this model beyond simplicial complexes, e.g., from polytopal and cell complexes to manifold complexes, and apply it to a real-world simplicial complex representing the visual cortex of a macaque.

We show that the decision problem of determining whether a given (abstract simplicial) k-complex has a geometric embedding in Rd is complete for the Existential Theory of the Reals for all d ≥ 3 and k ∈ {d− 1, d}. Consequently, the problem is polynomial time equivalent to determining whether a polynomial equation system has a real solution and other important problems from various fields related to packing, Nash equilibria, minimum convex covers, the Art Gallery Problem, continuous constraint satisfaction problems, and training neural networks. Moreover, this implies NP-hardness and constitutes the first hardness result for the algorithmic problem of geometric embedding (abstract simplicial) complexes. This complements recent breakthroughs for the computational complexity of piece-wise linear embeddability.

Variational Auto-Encoders (VAEs) are one of the most famous deep generative models. After showing that standard VAEs may not preserve the topology, that is the shape of the data, between the input and the latent space, we tried to modify them so that the topology is preserved. This would help in particular for performing interpolations in the latent space. Our main contribution is two folds. Firstly, we propose successfully the InvMap-VAE which is a simple way to turn any dimensionality reduction technique, given its embedding, into a generative model within a VAE framework providing an inverse mapping, with all the advantages that this implies. Secondly, we propose the Witness Simplicial VAE as an extension of the Simplicial Auto-Encoder to the variational setup using a Witness Complex for computing a simplicial regularization. The Witness Simplicial VAE is independent of any dimensionality reduction technique and seems to better preserve the persistent Betti numbers of a data set than a standard VAE, although it would still need some further improvements. Finally, the two first chapters of this master thesis can also be used as an introduction to Topological Data Analysis, General Topology and Computational Topology (or Algorithmic Topology), for any machine learning student, engineer or researcher interested in these areas with no background in topology., Variations autokodare (VAE) är en av de mest kända djupa generativa modellerna. Efter att ha visat att standard VAE inte nödvändigtvis bevarar topologiska egenskaper, det vill säga formen på datan, mellan inmatningsdatan och det latenta rummet, försökte vi modifiera den så att topologin är bevarad. Det här skulle i synnerhet underlätta när man genomför interpolering i det latenta rummet. Denna avhandling består av två centrala bidrag. I första hand så utvecklar vi InvMap-VAE, som är en enkel metod att omvandla vilken metod inom dimensionalitetsreducering, givet dess inbäddning, till en generativ modell inom VAE ramverket, vilket ger en invers avbildning och dess tillhörande fördelar. För det andra så presenterar vi Witness Simplicial VAE som en förlängning av en Simplicial Auto-Encoder till dess variationella variant genom att använda ett vittneskomplex för att beräkna en simpliciel regularisering. Witness Simplicial VAE är oberoende av dimensionalitets reducerings teknik och verkar bättre bevara Betti-nummer av ett dataset än en vanlig VAE, även om det finns utrymme för förbättring. Slutligen så kan de första två kapitlena av detta examensarbete också användas som en introduktion till Topologisk Data Analys, Allmän Topologi och Beräkningstopologi (eller Algoritmisk Topologi) till vilken maskininlärnings student, ingenjör eller forskare som är intresserad av dessa ämnesområden men saknar bakgrund i topologi.

In 1950 when JHC Whitehead introduced the idea of elementary collapse of simplicial complexes and the simple homotopy type. In 2012 Barmar and Minian return to the topic and develop the theory of strong collapse of simplicial complexes, which has interesting applications to collapsibility problems. In this thesis we first review both concepts and a third one - edge contraction- and explore their consequences on matroids (a special kind of simplicial complexes). Secondly, we study a generalization of the idea of strong collapse to (non-finite) Alexandroff spaces. Finally, we present several algorithms to facilitate the exploration of all these concepts in the case of finite simplicial complexes and directed graphs.

An online algorithm for missing data imputation for networks with signals defined on the edges is presented. Leveraging the prior knowledge intrinsic to real-world networks, we propose a bi-level optimization scheme that exploits the causal dependencies and the flow conservation, respectively via (i) a sparse line graph identification strategy based on a group-Lasso and (ii) a Kalman filtering-based signal reconstruction strategy developed using simplicial complex (SC) formulation. The advantages of this first SC-based attempt for time-varying signal imputation have been demonstrated through numerical experiments using EPANET models of both synthetic and real water distribution networks., Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public., Multimedia Computing

Graphs can model networked data by representing them as nodes and their pairwise relationships as edges. Recently, signal processing and neural networks have been extended to process and learn from data on graphs, with achievements in tasks like graph signal reconstruction, graph or node classifications, and link prediction. However, these methods are only suitable for data defined on the nodes of a graph. In this paper, we propose a simplicial convolutional neural network (SCNN) architecture to learn from data defined on simplices, e.g., nodes, edges, triangles, etc. We study the SCNN permutation and orientation equivariance, complexity, and spectral analysis. Finally, we test the SCNN performance for imputing citations on a coauthorship complex., Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public., Multimedia Computing, Signal Processing Systems

Much discussion exists about what is computation, but less about is a computational problem. Turing’s definition of computation was based on computing functions. When we move from sequential computing to interactive computing, discussions concentrate on computations that do not terminate, overlooking notions of distributed problems. Many models where concurrency happens have been proposed, ranging from those equivalent to a Turing machine, to those where much heated discussion has taken place, claiming that interactive models are fundamentally different from Turing machines. It is argued here that there is no need to go all the way to non-terminating interaction, to appreciate how different distributed computation is from sequential computation. The discussion concentrates on the various ways that exist of representing a distributed decision problem. Each process of a distributed system starts with an initial private input value, and after communicating with other processes in the system, produces a local output value. An input/output relation is needed, to specify which output values are legal for a particular assignment of input values to the processes. An overview is provided of some results that show how rich the topic of distributed decision problems can be, when asynchronous processes can fail, but mostly independent of particular models of distributed computing and their many intricate details (types of failures and of communication). We are in a world very different from that of the functions of sequential computation; moving away from the world of graphs beyond binary relations, to the world of simplicial complexes.

In this work, we define cooperative games on simplicial complexes, generalizing the study of probabilistic values of Weber (1988) and quasi-probabilistic values of Bilbao et al. (2001). Applications to Multi-Touch Attribution and the interpretability of the Machine-Learning prediction models motivate these new developments (Lundberg and Lee, 2017; Ribeiro et al., 2016; Strumbelj and Kononenko, 2013; Shrikumar et al., 2017; Datta et al., 2016; Bach et al., 2015). We deal with the axiomatization provided by the λi-dummy and the monotonicity requirements together with a probabilistic form of the symmetric and the efficiency axioms. We also characterize combinatorially the set of probabilistic participation influences as the facet polytope of the simplicial complex. © 2020 The Author(s), QC 20201203

Artificial Intelligence in the form of neural networks is becoming wide spread. This report focuses on a specific form of neural networks, Simplicial Neural Networks. After presenting their advantages and how they were implemented in Python by using the code of [1], they are tested in 2 experiments to explore their applicability in solving physical problems. The first experiment aimed to test the feasibility of the approach as well as to compare them to traditional neural networks. The second experiment aimed at testing the use of SNNs in predicting pressures through a Stokes Flow when the flow is known. Although the experiment was carried out incorrectly the network still produced accurate results in the context of the experiment, and SNNs could present an alternative to Finite Element Solvers., Applied Mathematics

Toric Topology 2021 in Osaka is aimed to present recent achievements in toric topology and related topics, and to discuss perspectives of further researches. The conference is supported by OCAMI.

We consider the embeddability problem of a graph G into a two-dimensional simplicial complex C: Given G and C, decide whether G admits a topological embedding into C. The problem is NP-hard, even in the restricted case where C is homeomorphic to a surface. It is known that the problem admits an algorithm with running time f(c)n^{O(c)}, where n is the size of the graph G and c is the size of the two-dimensional complex C. In other words, that algorithm is polynomial when C is fixed, but the degree of the polynomial depends on C. We prove that the problem is fixed-parameter tractable in the size of the two-dimensional complex, by providing a deterministic f(c)n³-time algorithm. We also provide a randomized algorithm with expected running time 2^{c^{O(1)}}n^{O(1)}. Our approach is to reduce to the case where G has bounded branchwidth via an irrelevant vertex method, and to apply dynamic programming. We do not rely on any component of the existing linear-time algorithms for embedding graphs on a fixed surface; the only elaborated tool that we use is an algorithm to compute grid minors.

Voronoi diagrams and their dual, the Delaunay complex, are two fundamental geometric concepts that lie at the foundation of many machine learning algorithms and play a role in particular in classical piecewise linear interpolation and regression methods. More recently, they are also crucial for the construction of a common class of simplicial complexes such as Alpha and Delaunay-\vC ech complexes in topological data analysis. We propose a randomized approximation approach that mitigates the prohibitive cost of exact computation of Voronoi diagrams in high dimensions for machine learning applications. In experiments with data in up to 50 dimensions, we show that this allows us to significantly extend the use of Voronoi-based simplicial complexes in Topological Data Analysis (TDA) to higher dimensions. We confirm prior TDA results on image patches that previously had to rely on sub-sampled data with increased resolution and demonstrate the scalability of our approach by performing a TDA analysis on synthetic data as well as on filters of a ResNet neural network architecture. Secondly, we propose an application of our approach to piecewise linear interpolation of high dimensional data that avoids explicit complete computation of an associated Delaunay triangulation., QC 20201217Part of proceedings: ISBN 978-1-4503-7998-4

The Eulerian polynomials and derangement polynomials are two well-studied generating functions that frequently arise in combinatorics, algebra, and geometry. When one makes an appearance, the other often does so as well, and their corresponding generalizations are similarly linked. This is this case in the theory of subdivisions of simplicial complexes, where the Eulerian polynomial is an h-polynomial and the derangement polynomial is its local h-polynomial. Separately, in Ehrhart theory the Eulerian polynomials are generalized by the h*-polynomials of s-lecture hall simplices. Here, we show that derangement polynomials are analogously generalized by the box polynomials, or local h*-polynomials, of the s-lecture hall simplices, and that these polynomials are all real-rooted. We then connect the two theories by showing that the local h-polynomials of common subdivisions in algebra and topology are realized as local h*-polynomials of s-lecture hall simplices. We use this connection to address some open questions on real-rootedness and unimodality of generating polynomials, some from each side of the story., QC 20200616

Efficient robustness and fault tolerance of complex network is significantly influenced by its connectivity, commonly modeled by the structure of pairwise relations between network elements, i.e., nodes. Nevertheless, aggregations of nodes build higher-order structures embedded in complex network, which may be more vulnerable when the fraction of nodes is removed. The structure of higher-order aggregations of nodes can be naturally modeled by simplicial complexes, whereas the removal of nodes affects the values of topological invariants, like the number of higher-dimensional holes quantified with Betti numbers. Following the methodology of percolation theory, as the fraction of nodes is removed, new holes appear, which have the role of merger between already present holes. In the present article, relationship between the robustness and homological properties of complex network is studied, through relating the graph-theoretical signatures of robustness and the quantities derived from topological invariants. The simulation results of random failures and intentional attacks on networks suggest that the changes of graph-theoretical signatures of robustness are followed by differences in the distribution of number of holes per cluster under different attack strategies. In the broader sense, the results indicate the importance of topological invariants research for obtaining further insights in understanding dynamics taking place over complex networks.

Intricacies of the structure of social relations are realized by representing a collection of overlapping opinions as a simplicial complex, thus building latent multidimensional structures, through which agents are, virtually, moving as they exchange opinions. The influence of opinion space structure on the distribution of opinions is demonstrated by modeling consensus phenomena when the opinion exchange between individuals may be affected by the false consensus effect. The results indicate that in the cases with and without bias, the road toward consensus is influenced by the structure of multidimensional space of opinions, and in the biased case, complete consensus is achieved. The applications of proposed modeling framework can easily be generalized, as they transcend opinion formation modeling. (C) 2017 Elsevier B.V. All rights reserved.

We present criteria for establishing a triangulation of a manifold. Given a manifold M, a simplicial complex A, and a map H from the underlying space of A to M, our criteria are presented in local coordinate charts for M, and ensure that H is a homeomorphism. These criteria do not require a differentiable structure, or even an explicit metric on M. No Delaunay property of A is assumed. The result provides a triangulation guarantee for algorithms that construct a simplicial complex by working in local coordinate patches. Because the criteria are easily verified in such a setting, they are expected to be of general use.

We consider the problem of deciding whether an input graph G admits a topological embedding into a two-dimensional simplicial complex C. This problem includes, among others, the embeddability problem of a graph on a surface and the topological crossing number of a graph, but is more general. The problem is NP-complete when C is part of the input, and we give a polynomial-time algorithm if the complex C is fixed. Our strategy is to reduce the problem to an embedding extension problem on a surface, which has the following form: Given a subgraph H' of a graph G', and an embedding of H' on a surface S, can that embedding be extended to an embedding of G' on S? Such problems can be solved, in turn, using a key component in Mohar's algorithm to decide the embeddability of a graph on a fixed surface (STOC 1996, SIAM J. Discr. Math. 1999).

A numerical characterization is given of the h-triangles of sequentially Cohen-Macaulay simplicial complexes. This result determines the number of faces of various dimensions and codimensions that are possible in such a complex, generalizing the classical Macaulay-Stanley theorem to the nonpure case. Moreover, we characterize the possible Betti tables of componentwise linear ideals. A key tool in our investigation is a bijection between shifted multicomplexes of degree <= d and shifted pure. (d - 1)-dimensional simplicial complexes., QC 20171207

We examine and prove the Borsuk-Ulam theorem and its combinatorial equivalent Fan's lemma. The theory of simplicial complexes and triangulations plays an important role in this. The Borsuk-Ulam theorem and Fan's lemma will be used to provide proofs for the Brouwer fixed point theorem and the combinatorial Sperner's lemma. Lastly the Borsuk-Ulam theorem will be applied in determining the chromatic number of Kneser graphs.

The method of partial derivatives is one of the most successful lower bound methods for arithmetic circuits. It uses as a complexity measure the dimension of the span of the partial derivatives of a polynomial. In this paper, we consider this complexity measure as a computational problem: for an input polynomial given as the sum of its nonzero monomials, what is the complexity of computing the dimension of its space of partial derivatives? We show that this problem is #P-hard and we ask whether it belongs to #P. We analyze the "trace method", recently used in combinatorics and in algebraic complexity to lower bound the rank of certain matrices. We show that this method provides a polynomial-time computable lower bound on the dimension of the span of partial derivatives, and from this method we derive closed-form lower bounds. We leave as an open problem the existence of an approximation algorithm with reasonable performance guarantees.

We consider the problem of finding a subcomplex K' of a simplicial complex K such that K' is homeomorphic to the 2-dimensional sphere, S^2. We study two variants of this problem. The first asks if there exists such a K' with at most k triangles, and we show that this variant is W[1]-hard and, assuming ETH, admits no O(n^(o(sqrt(k)))) time algorithm. We also give an algorithm that is tight with regards to this lower bound. The second problem is the dual of the first, and asks if K' can be found by removing at most k triangles from K. This variant has an immediate O(3^k poly(|K|)) time algorithm, and we show that it admits a polynomial kernelization to O(k^2) triangles, as well as a polynomial compression to a weighted version with bit-size O(k log k).

We prove that it is NP-complete to decide whether a given (3-dimensional) simplicial complex is collapsible. This work extends a result of Malgouyres and Francés showing that it is NP-complete to decide whether a given simplicial complex collapses to a 1-complex., QC 20160203

One of the principle concerns of computational mathematics is the discrete representation and approximation of mathematical objects. It is common for classical definitions of mathematical objects to allow for elegant mathematical analysis yet lead to computational models which are either inefficient or unimplementable. One mathematical object that fits this mold is a differentiable manifold. Differentiable manifolds are of increasing interest in modern computational mathematics as more geometrically complex problems are considered. In this dissertation, we propose a computational model for representing compact $C^1$ differentiable manifolds without boundary and their function spaces. This model is based on a combination of simplicial complexes and splines. Simplicial complexes are a standard tool for computing in both the pure and applied math settings. Splines are piecewise polynomials relative to some tessellation of a domain of interest whose coefficients have been chosen to enforce differentiability at all points of the domain.

The notion of $\mathcal{H}$-matroids was introduced by U. Faigle and S. Fujishige in 2009 as a general model for matroids and the greedy algorithm. They gave a characterization of $\mathcal{H}$-matroids by the greedy algorithm. In this note, we give a characterization of some $\mathcal{H}$-matroids by rank functions.

This report examines the co-authorship network from the publication record of the Communication and Networks Collaborative Technology Alliance (C&N CTA). In addition to several traditional graph properties, we examine various simplicial complex properties of the network where the simplex structure is generated by the group of co-authors on individual papers. In particular, we study aspects of the connectivity of k-simplices and k-facets. We study particular centrality characteristics, revealing inherent properties of co-authorship networks, including facet degrees follow a power law distribution, homology cycles intersect, and minimal non-faces are due to independent clustering. We also study more traditional topological properties of the network, including Q-analysis, f-vectors, and the Euler characteristic., The original document contains color images.

In this paper we establish a natural definition of Lusternik-Schnirelmann category for simplicial complexes via the well known notion of contiguity. This simplicial category has the property of being invariant under strong equivalences, and it only depends on the simplicial structure rather than its geometric realization. In a similar way to the classical case, we also develop a notion of simplicial geometric category. We prove that the maximum value over the simplicial homotopy class of a given complex is attained in the core of the complex. Finally, by means of well known relations between simplicial complexes and posets, specific new results for the topological notion of LS-category are obtained in the setting of finite topological spaces.

The Simplex Tree (ST) is a recently introduced data structure that can represent abstract simplicial complexes of any dimension and allows efficient implementation of a large range of basic operations on simplicial complexes. In this paper, we show how to optimally compress the Simplex Tree while retaining its functionalities. In addition, we propose two new data structures called Maximal Simplex Tree (MxST) and Simplex Array List (SAL). We analyze the compressed Simplex Tree, the Maximal Simplex Tree, and the Simplex Array List under various settings.

A fundamental question for simplicial complexes is to find the lowest dimensional Euclidean space in which they can be embedded. We investigate this question for order complexes of posets. We show that order complexes of thick geometric lattices as well as several classes of finite buildings, all of which are order complexes, are hard to embed. That means that such -dimensional complexes require -dimensional Euclidean space for an embedding. (This dimension is always sufficient for any -complex.) We develop a method to show non-embeddability for general order complexes of posets., Updated from "Submitted" to "Published". QC 20140707

Geometric realization of an opinion is considered as a simplex and the opinion space of a group of individuals is a simplicial complex whose topological features are monitored in the process of opinion formation. The agents are physically located at the nodes of a scale-free and a random network. Social interactions include all concepts of social dynamics present in the mainstream models, augmented by four additional interaction mechanisms which depend on the local properties of opinions and their overlapping properties. The results pertaining to the formation of consensus are of particular interest. An analogy with quantum mechanical pure states is established through the application of the high-dimensional combinatorial Laplacian. (C) 2013 Elsevier B.V. All rights reserved.

Let S be a k-colored (finite) set of n points in , da parts per thousand yen3, in general position, that is, no (d+1) points of S lie in a common (d-1)-dimensional hyperplane. We count the number of empty monochromatic d-simplices determined by S, that is, simplices which have only points from one color class of S as vertices and no points of S in their interior. For 3a parts per thousand currency signka parts per thousand currency signd we provide a lower bound of and strengthen this to Omega(n (d-2/3)) for k=2.; On the way we provide various results on triangulations of point sets in . In particular, for any constant dimension da parts per thousand yen3, we prove that every set of n points (n sufficiently large), in general position in , admits a triangulation with at least dn+Omega(logn) simplices., Postprint (author’s final draft)

For delta >= 1 and n >= 1, consider the simplicial complex of graphs on n vertices in which each vertex has degree at most delta; we identify a given graph with its edge set and admit one loop at each vertex. This complex is of some importance in the theory of semigroup algebras. When delta = 1, we obtain the matching complex, for which it is known that there is 3-torsion in degree d of the homology whenever (n - 4)/3 <= d <= (n - 6)/2. This paper establishes similar bounds for delta >= 2. Specifically, there is 3-torsion in degree d whenever (3 delta - 1)n - 8/6 <= d <= delta(n - 1) - 4/2. The procedure for detecting torsion is to construct an explicit cycle z that is easily seen to have the property that 3z is a boundary. Defining a homomorphism that sends z to a non-boundary element in the chain complex of a certain matching complex, we obtain that z itself is a non-boundary. In particular, the homology class of z has order 3., QC 20130905

This Demo presents an application for gait recognition using persistent homology. Using a background subtraction approach, a silhouette sequence is obtained from a camera in a controlled environment. A border simplicial complex is built stacking silhouettes aligned by their gravity center. A multifiltration is applied on the border simplicial complex which captures relations among the parts of the human body when walking. Finally, the topological gait signature is extracted from the persistence barcode according to each filtration. The measure cosine is used to give a similarity value between topological signatures. The input of this Demo are videos with resolution 320x240 to 25f ps. The videos in CASIA-B database are used to prove the efficacy and efficiency. A computer with 2Gb of RAM memory and a DualCore processor was used to test the implementation of the proposed algorithm. In this Demo all related tasks have been programmed by the authors in the C++ programming language. OpenCV library has been used for the image processing part.

We consider the broadcasting problem in multi-radio multi-channel ad hoc networks. The objective is to minimize the total cost of the network-wide broadcast, where the cost can be of any form that is summable over all the transmissions (e.g., the transmission and reception energy, the price for accessing a specific channel). Our technical approach is based on a simplicial complex model that allows us to capture the broadcast nature of the wireless medium and the heterogeneity across radios and channels. Specifically, we show that broadcasting in multi-radio multi-channel ad hoc networks can be formulated as a minimum spanning problem in simplicial complexes. We establish the NP-completeness of the minimum spanning problem and propose two approximation algorithms with order-optimal performance guarantee. The first approximation algorithm converts the minimum spanning problem in simplical complexes to a minimum connected set cover problem. The second algorithm converts it to a node-weighted Steiner tree problem under the classic graph model. These two algorithms offer tradeoffs between performance and time-complexity. In a broader context, this work appears to be the first that studies the minimum spanning problem in simplicial complexes and weighted minimum connected set cover problem., Submitted to IEEE Transactions on Wireless Communications, October 2011.

[EN] The approach we present is a modification of the Morse theory for unital C*-algebras. We provide tools for the geometric interpretation of noncommutative CW complexes. Some examples are given to illustrate these geometric information. The main object of this work is a classification of unital C*-algebras by noncommutative CW complexes and the modified Morse functions on them.

This paper is focused on the study of perfect discrete Morse functions on a 2-simplicial complex. These are those discrete Morse functions such that the number of critical i-simplices coincides with the i-th Betti number of the complex. In particular, we establish conditions under which a 2-complex admits a perfect discrete Morse function and conversely, we get topological properties of a 2-complex admitting such kind of functions. This approach is more general than the known results in the literature [7], since our study is not restricted to surfaces. These results can be considered as a first step in the study of perfect discrete Morse functions on 3-manifolds.

Let S be a finite alphabet. An injective word over S is a word over S such that each letter in S appears at most once in the word. For an abstract simplicial complex Delta, let Gamma(Delta) be the Boolean cell complex whose cells are indexed by all injective words over the sets forming the faces of Delta. The boundary of a cell indexed by a given word w consists of those cells that are indexed by subwords of w. For a partial order P on S, we study the subcomplex Gamma(Delta, P) of Gamma(Delta) consisting of those cells that are indexed by words whose letters are arranged in increasing order with respect to some linear extension of the order P. For a graph G = (S, E) on vertex set S and a word w over S, let [w] be the class of all words that we can obtain from w via a sequence of commutations ss' -> s's s such that {s, s'} g is not an edge in E. We study the Boolean cell complex Gamma/G(Delta) whose cells are indexed by commutation classes [w] of words indexing cells in Gamma(Delta). We prove: If Delta is shellable then so are Gamma(Delta, P) and Gamma/G(Delta). If Delta is Cohen-Macaulay (respectively sequentially Cohen-Macaulay) then so are Gamma(Delta, P) and Gamma/G(Delta). The complex Gamma(Delta) is partitionable. Our work generalizes work by Farmer and by Bjorner and Wachs on the complex of all injective words., QC 20100525

Let X be a simplicial complex with ground set V. Define its Alexander dual as the simplicial complex X* = {sigma subset of V vertical bar V \ sigma is not an element of X}. The combinatorial Alexander duality states that the ith reduced homology group of X is isomorphic to the (vertical bar V vertical bar - i - 3) th reduced cohomology group of X* (over a given commutative ring R). We give a self-contained proof from first principles accessible to a nonexpert., QC 20100525

El método más común de representar objetos de tres dimensiones (3D) en computación gráfica es la malla poligonal, que aproxima la superficie del objeto utilizando polígonos. Aquí, por desempeño y eficiencia de procesamiento, el triángulo es el polígono más usual. Sin embargo, el número de triángulos requeridos para crear una representación de una forma compleja aumenta en la medida en que se busca mayor exactitud o resolución. Por esta razón, se han creado técnicas de optimización de mallas que buscan disminuir el número de polígonos sin perder resolución. De esta manera, la malla poligonal puede ocupar menos espacio en memoria. Este artículo presenta una técnica de compresión de mallas que se basa en la teoría matemática de la topología y la representación de símplices. Esta técnica fue creada con el fin de comprimir mallas que van a ser transmitidas a través de internet para ser usadas en aplicaciones interactivas a través de la red., Polygonal meshes, which approxi­mate the surface of an object, are the most common method for repre­senting three dimensional objects. Here, in order to attain efficiency, the triangle is the most used polygon. However, the number of required triangles increases as more realism is needed in a complex form. For this reason, mesh optimization techniques have been created that keep resolu­tion and enhances performance. This way, the polygonal mesh occupies less memory space. This paper presents a mesh compression technique which is based on mathematical topology and the simplicial representation. This technique was developed in order to compress meshes that were going to be sent through Internet.

Polygonal meshes, which approxi­mate the surface of an object, are the most common method for repre­senting three dimensional objects. Here, in order to attain efficiency, the triangle is the most used polygon. However, the number of required triangles increases as more realism is needed in a complex form. For this reason, mesh optimization techniques have been created that keep resolu­tion and enhances performance. This way, the polygonal mesh occupies less memory space. This paper presents a mesh compression technique which is based on mathematical topology and the simplicial representation. This technique was developed in order to compress meshes that were going to be sent through Internet., El método más común de representar objetos de tres dimensiones (3D) en computación gráfica es la malla poligonal, que aproxima la superficie del objeto utilizando polígonos. Aquí, por desempeño y eficiencia de procesamiento, el triángulo es el polígono más usual. Sin embargo, el número de triángulos requeridos para crear una representación de una forma compleja aumenta en la medida en que se busca mayor exactitud o resolución. Por esta razón, se han creado técnicas de optimización de mallas que buscan disminuir el número de polígonos sin perder resolución. De esta manera, la malla poligonal puede ocupar menos espacio en memoria. Este artículo presenta una técnica de compresión de mallas que se basa en la teoría matemática de la topología y la representación de símplices. Esta técnica fue creada con el fin de comprimir mallas que van a ser transmitidas a través de internet para ser usadas en aplicaciones interactivas a través de la red.

Let G be a finite graph with vertex set V and edge set E. A graph complex on G is an abstract simplicial complex consisting of subsets of E. In particular, we may interpret such a complex as a family of subgraphs of G. The subject of this thesis is the topology of graph complexes, the emphasis being placed on homology, homotopy type, connectivity degree, Cohen-Macaulayness, and Euler characteristic. We are particularly interested in the case that G is the complete graph on V. Monotone graph properties are complexes on such a graph satisfying the additional condition that they are invariant under permutations of V. Some well-studied monotone graph properties that we discuss in this thesis are complexes of matchings, forests, bipartite graphs, disconnected graphs, and not 2-connected graphs. We present new results about several other monotone graph properties, including complexes of not 3-connected graphs and graphs not coverable by p vertices. Imagining the vertices as the corners of a regular polygon, we obtain another important class consisting of those graph complexes that are invariant under the natural action of the dihedral group on this polygon. The most famous example is the associahedron, whose faces are graphs without crossings inside the polygon. Restricting to matchings, forests, or bipartite graphs, we obtain other interesting complexes of noncrossing graphs. We also examine a certain "dihedral" variant of connectivity. The third class to be examined is the class of digraph complexes. Some well-studied examples are complexes of acyclic digraphs and not strongly connected digraphs. We present new results about a few other digraph complexes, including complexes of graded digraphs and non-spanning digraphs. Many of our proofs are based on Robin Forman's discrete version of Morse theory. As a byproduct, this thesis provides a loosely defined toolbox for attacking problems in topological combinatorics via discrete Morse theory. In terms of simplicity and powe, QC 20100622

A combinatorial description of the minimal free resolution of a lattice ideal allows us to the connection of Integer Linear Programming and Algebra. The non null reduced homology spaces of some simplicial complexes are the key. The extremal rays of the associated cone reduce the number of variables.

QS 2015