An official website of the United States government
Hypergraphs and tensors extend classic graph and matrix theories to account for multiway relationships, which are ubiquitous in engineering, biological, and social systems. While the Kronecker product is a potent tool for analyzing the coupling of systems in a graph or matrix context, its utility in studying multiway interactions, such as those represented by tensors and hypergraphs, remains elusive. In this article, we present a comprehensive exploration of algebraic, structural, and spectral properties of the tensor Kronecker product. We express Tucker and tensor train decompositions and various tensor eigenvalues in terms of the tensor Kronecker product. Additionally, we utilize the tensor Kronecker product to form Kronecker hypergraphs, which are tensor-based hypergraph products, and investigate the structure and stability of polynomial dynamics on Kronecker hypergraphs. Finally, we provide numerical examples to demonstrate the utility of the tensor Kronecker product in computing Z-eigenvalues, performing various tensor decompositions, and determining the stability of polynomial systems.
more »
« less
This content will become publicly available on June 1, 2027
A survey of simplicial, relative, and chain complex homology theories for hypergraphs
Hypergraphs have seen widespread application in network and data science communities in recent years.We present a survey of recentwork to construct auxiliary structures fromhypergraphs—specifically simplicial, relative, and chain complexes—that can be used to build homology theories for hypergraphs. We define and describe nine different constructions and their associated homology theories.We discuss some interesting properties of each homology theory to show how various hypergraph properties imply properties of the homology groups. We also include discussion of functoriality for several of the homology theories. Finally, we provide a series of illustrative examples by computing many of these homology theories for small hypergraphs to show the variability of the methods and build intuition.
more »
« less
- Award ID(s):
- 1854705
- PAR ID:
- 10704827
- Publisher / Repository:
- Springer
- Date Published:
- Journal Name:
- Journal of Applied and Computational Topology
- Volume:
- 10
- Issue:
- 7
- ISSN:
- 2367-1726
- Page Range / eLocation ID:
- 55
- Subject(s) / Keyword(s):
- Hypergraphs, Simplicial homology, Relative homology, Chain complex
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Shadows for bicategories, defined by Ponto, provide a useful framework that generalizes classical and topological Hochschild homology. In this paper, we define Hochschild-type invariants for monoids in a symmetric monoidal, simplicial model category $$\mathsf V$$, as well as for small $$\mathsf V$$-categories. We show that each of these constructions extends to a shadow on an appropriate bicategory, which implies in particular that they are Morita invariant. We also define a generalized theory of Hochschild homology twisted by an automorphism and show that it is Morita invariant. Hochschild homology of Green functors and $$C_n$$-twisted topological Hochschild homology fit into this framework, which allows us to conclude that these theories are Morita invariant. We also study linearization maps relating the topological and algebraic theories, proving that the linearization map for topological Hochschild homology arises as a lax shadow functor, and constructing a new linearization map relating topological restriction homology and algebraic restriction homology. Finally, we construct a twisted Dennis trace map from the fixed points of equivariant algebraic $$K$$-theory to twisted topological Hochschild homology.more » « less
-
In this paper generalizes the work of the second author and prove a grading shifting property, in sutured monopole and instanton Floer theories, for general balanced sutured manifolds. This result has a few consequences. First, we offer an algorithm that computes the Floer homologies of a family of sutured handle-bodies. Second, we obtain a canonical decomposition of sutured monopole and instanton Floer homologies and build polytopes for these two theories, which was initially achieved by Juhász for sutured (Heegaard) Floer homology. Third, we establish a Thurston-norm detection result for monopole and instanton knot Floer homologies, which were introduced by Kronheimer and Mrowka. The same result was originally proved by Ozsváth and Szabó for link Floer homology. Last, we generalize the construction of minus versions of monopole and instanton knot Floer homology, which was initially done for knots by the second author, to the case of links. Along with the construction of polytopes, we also proved that, for a balanced sutured manifold with vanishing second homology, the rank of the sutured monopole or instanton Floer homology bounds the depth of the balanced sutured manifold. As a corollary, we obtain an independent proof that monopole and instanton knot Floer homologies, as mentioned above, both detect fibred knots in S3. This result was originally achieved by Kronheimer and Mrowka.more » « less
-
Abstract. We develop persistent homology in the setting of filtrations of (Cˇech) closure spaces. Examples of filtrations of closure spaces include metric spaces, weighted graphs, weighted directed graphs, and filtrations of topological spaces. We use various products and intervals for closure spaces to obtain six homotopy theories, six cubical singular homology theories, and three simplicial singular homology theories. Applied to filtrations of closure spaces, these homology theories produce persistence modules. We extend the definition of Gromov-Hausdorff distance from metric spaces to filtrations of closure spaces and use it to prove that any persistence module obtained from a homotopy-invariant functor on closure spaces is stable.more » « less
-
Censor-Hillel, Keren; Grandoni, Fabrizio; Ouaknine, Joel; Puppis, Gabriele (Ed.)Scarf’s algorithm - a pivoting procedure that finds a dominating extreme point in a down-monotone polytope - can be used to show the existence of a fractional stable matching in hypergraphs. The problem of finding a fractional stable matching in hypergraphs, however, is PPAD-complete. In this work, we study the behavior of Scarf’s algorithm on arborescence hypergraphs, the family of hypergraphs in which hyperedges correspond to the paths of an arborescence. For arborescence hypergraphs, we prove that Scarf’s algorithm can be implemented to find an integral stable matching in polynomial time. En route to our result, we uncover novel structural properties of bases and pivots for the more general family of network hypergraphs. Our work provides the first proof of polynomial-time convergence of Scarf’s algorithm on hypergraphic stable matching problems, giving hope to the possibility of polynomial-time convergence of Scarf’s algorithm for other families of polytopes.more » « less
