Tootfinder

Extremal Zagreb indices of bicyclic hypergraphs
Hong Zhou, Changjiang Bu
https://arxiv.org/abs/2506.08875 https://arxiv.org/pdf/2506.…

Extremal Zagreb indices of bicyclic hypergraphs
The Zagreb index of a hypergraph is defined as the sum of the squares of the degrees of its vertices. A connected $k$-uniform hypergraph with $n$ vertices and $m$ edges is called bicyclic if $n=m(k-1)-1$. In this paper, we determine the hypergraphs with the maximum and minimum Zagreb indices among all linear bicyclic uniform hypergraphs.

Compressing Hypergraphs using Suffix Sorting
Enno Adler, Stefan B\"ottcher, Rita Hartel
https://arxiv.org/abs/2506.05023 https://

Compressing Hypergraphs using Suffix Sorting
Hypergraphs model complex, non-binary relationships like co-authorships, social group memberships, and recommendations. Like traditional graphs, hypergraphs can grow large, posing challenges for storage, transmission, and query performance. We propose HyperCSA, a novel compression method for hypergraphs that maintains support for standard queries over the succinct representation. HyperCSA achieves compression ratios of 26% to 79% of the original file size on real-world hypergraphs - outperformi…

Uniform \v{S}olt\'es' hypergraphs and \v{S}olt\'es' weighted graphs
Stijn Cambie, Ajay Tiwari
https://arxiv.org/abs/2506.07511 https://

Uniform Šoltés' hypergraphs and Šoltés' weighted graphs
A Šoltés' hypergraph is a hypergraph for which the removal of any of its vertices does not change its total distance. We prove that every uniform Šoltés' hypergraph has order at least $10$, there exist uniform Šoltés' hypergraphs for almost every order or uniformity, and there exist a non-regular uniform Šoltés' hypergraph. By also providing infinitely many weighted Šoltés' graphs, we conclude that Šoltés' problem can be answered positively for the most natural generalisations of gr…

This https://arxiv.org/abs/2411.18264 has been replaced.
initial toot: https://mastoxiv.page/@arXiv_nli…

Hypergraphs and Lotka-Volterra systems with linear Darboux polynomials
We associate parametric classes of $n$-component Lotka-Volterra systems which admit $k$ additional linear Darboux polynomials, with admissible loopless hypergraphs of order $n$ and size $k$. We study the equivalence relation on admissible hypergraphs induced by linear transformations of the associated LV-systems, for $n\leq 5$. We present a new 13-parameter 5-component superintegrable Lotka-Volterra system, i.e. one that is not equivalent to a so-called tree-system. We conjecture that tree-syst…

Exploring the Non-uniqueness of Node Co-occurrence Matrices of Hypergraphs
Timothy LaRock, Renaud Lambiotte
https://arxiv.org/abs/2506.01479 https://

Exploring the Non-uniqueness of Node Co-occurrence Matrices of Hypergraphs
Hypergraphs extend traditional networks by capturing multi-way or group interactions. Given the complexity of hypergraph data and the wide range of methodology available for pairwise network analysis, hypergraph data is often projected onto a weighted and undirected network. The simplest of these projections, often referred to as a node co-occurrence matrix, is known to be non-unique, as distinct non-isomorphic hypergraphs can produce the same weighted adjacency matrix. This non-uniqueness rais…

Modeling temporal hypergraphs
J\"urgen Lerner, Marian-Gabriel H\^ancean, Matjaz Perc
https://arxiv.org/abs/2506.01408 https://ar…

Modeling temporal hypergraphs
Networks representing social, biological, technological or other systems are often characterized by higher-order interaction involving any number of nodes. Temporal hypergraphs are given by ordered sequences of hyperedges representing sets of nodes interacting at given points in time. In this paper we discuss how a recently proposed model family for time-stamped hyperedges - relational hyperevent models (RHEM) - can be employed to define tailored null distributions for temporal hypergraphs. RHE…

This https://arxiv.org/abs/2505.05702 has been replaced.
initial toot: https://mastoxiv.page/@arXiv_csLG_…

Hypergraph Neural Sheaf Diffusion: A Symmetric Simplicial Set Framework for Higher-Order Learning
The absence of intrinsic adjacency relations and orientation systems in hypergraphs creates fundamental challenges for constructing sheaf Laplacians of arbitrary degrees. We resolve these limitations through symmetric simplicial sets derived directly from hypergraphs, which encode all possible oriented subrelations within each hyperedge as ordered tuples. This construction canonically defines adjacency via facet maps while inherently preserving hyperedge provenance. We establish that the normal…

Sperner's colorings of hypergraphs arising from edgewise triangulations
Du\v{s}ko Joji\'c, Ognjen Papaz
https://arxiv.org/abs/2506.07201 https://…

Sperner's colorings of hypergraphs arising from edgewise triangulations
We investigate Sperner's labelings of $H^π_{k,q}$, the hypergraph whose hyperedges are facets of the edgewise triangulation of a $(k-1)$-simplex defined by a permutation $π\in \mathbb{S}_{k-1}$. Mirzakhani and Vondr\' ak showed that the greedy coloring of $H^{\mathrm{Id}}_{k,q}$ produces the maximal number of monochromatic hyperedges. The line graph of $H_{k,q}^π$ is built from the copies of the graph $G_π$ that represents which subsets of consecutive numbers of $[k-1]$ are contiguous in $�…

Assembly in Directed Hypergraphs
Christoph Flamm, Daniel Merkle, Peter F. Stadler
https://arxiv.org/abs/2505.22826 https://arxiv.org/…

Assembly in Directed Hypergraphs
Assembly theory has received considerable attention in the recent past. Here we analyze the formal framework of this model and show that assembly pathways coincide with certain minimal hyperpaths in B-hypergraphs. This makes it possible to generalize the notion of assembly to general chemical reaction systems and to make explicit the connection to rule based models of chemistry, in particular DPO graph rewriting. We observe, furthermore, that assembly theory is closely related to retrosynthetic…

Consistent line clustering using geometric hypergraphs
Kalle Alaluusua, Konstantin Avrachenkov, B. R. Vinay Kumar, Lasse Leskel\"a
https://arxiv.org/abs/2505.24868

Consistent line clustering using geometric hypergraphs
Traditional data analysis often represents data as a weighted graph with pairwise similarities, but many problems do not naturally fit this framework. In line clustering, points in a Euclidean space must be grouped so that each cluster is well approximated by a line segment. Since any two points define a line, pairwise similarities fail to capture the structure of the problem, necessitating the use of higher-order interactions modeled by geometric hypergraphs. We encode geometry into a 3-unifor…

This https://arxiv.org/abs/2206.04913 has been replaced.
link: https://scholar.google.com/scholar?q=a

Powers of the edge ideals and matchings in hypergraphs
In this work, some combinatorial lower bound for regularity of powers of the edge ideal of a uniform hypergarph is gained. A family of hypergraphs whose regularity of edge ideal attains this bound and has a significant difference from the lower bounds heretofore obtained have also been introduced.

This https://arxiv.org/abs/2505.12894 has been replaced.
initial toot: https://mastoxiv.page/@arXiv_csSI_…

HyperDet: Source Detection in Hypergraphs via Interactive Relationship Construction and Feature-rich Attention Fusion
Hypergraphs offer superior modeling capabilities for social networks, particularly in capturing group phenomena that extend beyond pairwise interactions in rumor propagation. Existing approaches in rumor source detection predominantly focus on dyadic interactions, which inadequately address the complexity of more intricate relational structures. In this study, we present a novel approach for Source Detection in Hypergraphs (HyperDet) via Interactive Relationship Construction and Feature-rich At…

This https://arxiv.org/abs/2504.05039 has been replaced.
initial toot: https://mastoxiv.page/@arXiv_mat…

Supports for Outerplanar and Bounded Treewidth Graphs
We study the existence and construction of sparse supports for hypergraphs derived from subgraphs of a graph $G$. For a hypergraph $(X,\mathcal{H})$, a support $Q$ is a graph on $X$ s.t. $Q[H]$, the graph induced on vertices in $H$ is connected for every $H\in\mathcal{H}$. We consider \emph{primal}, \emph{dual}, and \emph{intersection} hypergraphs defined by subgraphs of a graph $G$ that are \emph{non-piercing}, (i.e., each subgraph is connected, their pairwise differences remain connected). …

A Ranking Framework for Network Resource Allocation and Scheduling via Hypergraphs
Rajpreet Singh, Novak Bo\v{s}kov, Aditya Gudal, Manzoor A. Khan
https://arxiv.org/abs/2506.01571

A Ranking Framework for Network Resource Allocation and Scheduling via Hypergraphs
Resource allocation and scheduling are a common problem in various distributed systems. Although widely studied, the state-of-the-art solutions either do not scale or lack the expressive power to capture the most complex instances of the problem. To that end, we present a mathematical framework for hypergraph ranking and analysis, unifying graph theory, lattice theory, and semantic analysis. In our fundamental theorem, we prove the existence of partial order on entities of hypergraphs, extendin…

This https://arxiv.org/abs/2110.06506 has been replaced.
link: https://scholar.google.com/scholar?q=a

Network analysis using Forman curvature and Shapley values on hypergraphs
In recent years, network models have become more complex with the development of big data. Therefore, more advanced network analysis is required. In this paper, we introduce a new quantitative measure named combinatorial evaluation, which combines the discrete geometry concept of Forman Ricci curvature and the game theory concept of the Shapley value. We elucidated the characteristics of combinatorial evaluation by proving several properties of this indicator. Furthermore, we demonstrated the u…

This https://arxiv.org/abs/2001.09029 has been replaced.
link: https://scholar.google.com/scholar?q=a

Rewriting Structured Cospans
To support the study of compositional networks, we further develop the formalism of structured cospans. To enable rewriting, we introduce a category whose objects are structured cospans and characterize conditions under which this category is a topos or is adhesive. We then define a structured cospan grammar and language, using a 2-category framework. As an application, we demonstrate that for various sorts of graphs, hypergraphs, and Petri nets, any grammar induces the same language as its cor…

This https://arxiv.org/abs/2502.19030 has been replaced.
initial toot: https://mastoxiv.page/@arXiv_csSI_…

Sampling nodes and hyperedges via random walks on large hypergraphs
Hypergraphs provide a fundamental framework for representing complex systems involving interactions among three or more entities. As empirical hypergraphs grow in size, characterizing their structural properties becomes increasingly challenging due to computational complexity and, in some cases, restricted access to complete data, requiring efficient sampling methods. Random walks offer a practical approach to hypergraph sampling, as they rely solely on local neighborhood information from nodes…

Hypergraphs accumulate infinitely often
David Conlon, Bjarne Sch\"ulke
https://arxiv.org/abs/2506.03080 https://arxiv.org/pdf/25…

Hypergraphs accumulate infinitely often
We show that the set $Π^{(k)}$ of Turán densities of $k$-uniform hypergraphs has infinitely many accumulation points in $[0,1)$ for every $k \geq 3$. This extends an earlier result of ours showing that $Π^{(k)}$ has at least one such accumulation point.

Detecting Patterns of Interaction in Temporal Hypergraphs via Edge Clustering
Ryan DeWolfe, Fran\c{c}ois Th\'eberge
https://arxiv.org/abs/2506.03105 ht…

Detecting Patterns of Interaction in Temporal Hypergraphs via Edge Clustering
Finding densely connected subsets of vertices in an unsupervised setting, called clustering or community detection, is one of the fundamental problems in network science. The edge clustering approach instead detects communities by clustering the edges of the graph and then assigning a vertex to a community if it has at least one edge in that community, thereby allowing for overlapping clusters of vertices. We apply the idea behind edge clustering to temporal hypergraphs, an extension of a graph…

This https://arxiv.org/abs/2505.12910 has been replaced.
initial toot: https://mastoxiv.page/@arXiv_csSI_…

SourceDetMamba: A Graph-aware State Space Model for Source Detection in Sequential Hypergraphs
Source detection on graphs has demonstrated high efficacy in identifying rumor origins. Despite advances in machine learning-based methods, many fail to capture intrinsic dynamics of rumor propagation. In this work, we present SourceDetMamba: A Graph-aware State Space Model for Source Detection in Sequential Hypergraphs, which harnesses the recent success of the state space model Mamba, known for its superior global modeling capabilities and computational efficiency, to address this challenge. …

Effects of higher-order interactions and homophily on information access inequality
Moritz Laber, Samantha Dies, Joseph Ehlert, Brennan Klein, Tina Eliassi-Rad
https://arxiv.org/abs/2506.00156

Effects of higher-order interactions and homophily on information access inequality
The spread of information through socio-technical systems determines which individuals are the first to gain access to opportunities and insights. Yet, the pathways through which information flows can be skewed, leading to systematic differences in access across social groups. These inequalities remain poorly characterized in settings involving nonlinear social contagion and higher-order interactions that exhibit homophily. We introduce a enerative model for hypergraphs with hyperedge homophily…

This https://arxiv.org/abs/2409.19908 has been replaced.
link: https://scholar.google.com/scholar?q=a

Independent Sets in Hypergraphs
A theorem of Shearer states that every $n$-vertex triangle-free graph of maximum degree $d \geq 2$ contains an independent set of size at least $(d\log d - d + 1)/(d - 1)^2 \cdot n$. Ajtai, Komlós, Pintz, Spencer and Szemerédi proved that every $(r + 1)$-uniform $n$-vertex ``uncrowded'' hypergraph of maximum degree $d \geq 1$ has an independent set of size at least $c_r(\log d)^{1/r}/d^{1/r} \cdot n$ for some $c_r > 0$ depending only on $r$. Shearer asked whether his method for triangle-free …

Meta-heuristic Hypergraph-Assisted Robustness Optimization for Higher-order Complex Systems
Xilong Qu, Wenbin Pei, Haifang Li, Qiang Zhang, Bing Xue, Mengjie Zhang, del Genio Charo, Stefano Boccaletti
https://arxiv.org/abs/2505.24123

Meta-heuristic Hypergraph-Assisted Robustness Optimization for Higher-order Complex Systems
In complex systems (e.g., communication, transportation, and biological networks), high robustness ensures sustained functionality and stability even when resisting attacks. However, the inherent structure complexity and the unpredictability of attacks make robustness optimization challenging. Hypergraphs provide a framework for modeling complicated higher-order interactions in complex systems naturally, but their potential has not been systematically investigated. Therefore, we propose an effe…

Broad Spectrum Structure Discovery in Large-Scale Higher-Order Networks
John Hood, Caterina De Bacco, Aaron Schein
https://arxiv.org/abs/2505.21748 https:/…

Broad Spectrum Structure Discovery in Large-Scale Higher-Order Networks
Complex systems are often driven by higher-order interactions among multiple units, naturally represented as hypergraphs. Understanding dependency structures within these hypergraphs is crucial for understanding and predicting the behavior of complex systems but is made challenging by their combinatorial complexity and computational demands. In this paper, we introduce a class of probabilistic models that efficiently represents and discovers a broad spectrum of mesoscale structure in large-scal…

This https://arxiv.org/abs/2502.19799 has been replaced.
initial toot: https://mastoxiv.page/@arXiv_mat…

New recursion formula for the interior polynomial based on non-expanding sets
The interior polynomial was originally defined for hypergraphs and later shown to coincide with the Ehrhart polynomial of the root polytope of an associated bipartite graph. In previous work, we derived an alternating cycle recursion formula for the interior polynomial. Here, we introduce a new, more transparent recursion formula based on the structure of non-expanding sets. This formula offers a clearer combinatorial interpretation of the interior polynomial and its connection to polyhedral ge…

This https://arxiv.org/abs/2505.22561 has been replaced.
initial toot: https://mastoxiv.page/@arXiv_mat…

On Big Ramsey degrees of universal $ω$-edge-labeled hypergraphs
We show that the big Ramsey degrees of every countable universal $u$-uniform $ω$-edge-labeled hypergraph are infinite for every $u\geq 2$. Together with a recent result of Braunfeld, Chodounský, de Rancourt, Hubička, Kawach, and Konečný this finishes full characterisation of unrestricted relational structures with finite big Ramsey degrees.

Representing Higher-Order Networks with Spectral Moments
Hao Tian, Shengmin Jin, Reza Zafarani
https://arxiv.org/abs/2505.23691 https://

Representing Higher-Order Networks with Spectral Moments
The spectral properties of traditional (dyadic) graphs, where an edge connects exactly two vertices, are widely studied in different applications. These spectral properties are closely connected to the structural properties of dyadic graphs. We generalize such connections and characterize higher-order networks by their spectral information. We first split the higher-order graphs by their ``edge orders" into several uniform hypergraphs. For each uniform hypergraph, we extract the corresponding s…