Tootfinder

Spectral extremal problems for the $(p,Q)$-spectral radius of hypergraphs
Jian Zheng, Honghai Li, Li Su
https://arxiv.org/abs/2510.02776 https://arxiv.org/…

Spectral extremal problems for the $(p,Q)$-spectral radius of hypergraphs
Let $Q$ be an $s$-vertex $r$-uniform hypergraph, and let $H$ be an $n$-vertex $r$-uniform hypergraph. Denote by $\mathcal{N}(Q,H)$ the number of isomorphic copies of $Q$ in $H$. For a hereditary family $\mathcal{P}$ of $r$-uniform hypergraphs, define $$π(Q,\mathcal{P}):=\lim\limits_{n\to \infty}\binom{n}{s}^{-1}\max\{\mathcal{N}(Q,H): H\in \mathcal{P}~~\mbox{and}~~|V(H)|=n\}.$$ For $p\geq1$, the $(p,Q)$-spectral radius of $H$ is defined as $$λ^{(p)}(Q,H):=\max_{\|\mathbf{x}\
…

On the global linear Zarankiewicz problem
Pantelis E. Eleftheriou, Aris Papadopoulos
https://arxiv.org/abs/2510.03546 https://arxiv.org/pdf/2510.03546

On the global linear Zarankiewicz problem
The `global' Zarankiewicz problem for hypergraphs asks for an upper bound on the number of edges of a finite $r$-hypergraph $V$ in terms of the number $|V|$ of its vertices, assuming the edge relation is induced by a fixed $K_{k, \dots, k}$-free $r$-hypergraph $E$, for some $k\in\mathbb N$. In [4], such bounds of size $O(|V|^{r-1})$ were achieved for a semilinear $E$, namely, definable in a linear o-minimal structure. We establish the same bounds in five new settings: when $…

On the Hardness of the One-Sided Code Sparsifier Problem
Elena Grigorescu, Alice Moayyedi
https://arxiv.org/abs/2510.03184 https://arxiv.org/pdf/2510.03184…

On the Hardness of the One-Sided Code Sparsifier Problem
The notion of code sparsification was introduced by Khanna, Putterman and Sudan (arxiv.2311.00788), as an analogue to the the more established notion of cut sparsification in graphs and hypergraphs. In particular, for $α\in (0,1)$ an (unweighted) one-sided $α$-sparsifier for a linear code $\mathcal{C} \subseteq \mathbb{F}_2^n$ is a subset $S\subseteq [n]$ such that the weight of each codeword projected onto the coordinates in $S$ is preserved up to an $α$ fraction. Recently, Gharan and Saham…

A High-Dimensional Extension of Wagner's Theorem and the Geometrization of Hypergraphs
Qiming Fang, Sihong Shao
https://arxiv.org/abs/2510.01926 https://

A High-Dimensional Extension of Wagner's Theorem and the Geometrization of Hypergraphs
This paper introduces a geometric representation of hypergraphs by representing hyperedges as simplices. Building on this framework, we employ homotopy groups to analyze the topological structure of hypergraphs embedded in high-dimensional Euclidean spaces. Leveraging this foundation, we extend Wagner's theorem to $\mathbb{R}^d$. Specifically, we establish that a triangulated $d$-uniform topological hypergraph embeds into $\mathbb{R}^d$ if and only if it contains neither $K_{d+3}^d$ nor $K_{3,d…

Hypergraphs on high dimensional time series sets using signature transform
R\'emi Vaucher, Paul Minchella
https://arxiv.org/abs/2507.15802 https://

Hypergraphs on high dimensional time series sets using signature transform
In recent decades, hypergraphs and their analysis through Topological Data Analysis (TDA) have emerged as powerful tools for understanding complex data structures. Various methods have been developed to construct hypergraphs -- referred to as simplicial complexes in the TDA framework -- over datasets, enabling the formation of edges between more than two vertices. This paper addresses the challenge of constructing hypergraphs from collections of multivariate time series. While prior work has fo…

Hyper-Zagreb Indices of Hypergraphs with Application in Drug Design
Abdulkafi Sanad
https://arxiv.org/abs/2509.13787 https://arxiv.org/pdf/2509.13787

Hyper-Zagreb Indices of Hypergraphs with Application in Drug Design
Let $\mathcal{H}$ be a hypergraph on the non-empty finite vertex set $V(\mathcal{H})$ with the hyperedge set $E(\mathcal{H})$, where each hyperedge $e \in E(\mathcal{H})$ is a subset of $V(\mathcal{H})$ with at least two vertices. This paper introduces the first and second Hyper-Zagreb indices for hypergraphs, extending these well-known graph indices to hypergraphs. We discuss bounds on these indices for general hypergraphs, weak bipartite hypergraphs, hypertrees, $k$-uniform hypergraphs, $k$-u…

Structural-Aware Key Node Identification in Hypergraphs via Representation Learning and Fine-Tuning
Xiaonan Ni, Guangyuan Mei, Su-Su Zhang, Yang Chen, Xin Xu, Chuang Liu, Xiu-Xiu Zhan
https://arxiv.org/abs/2507.20682

Structural-Aware Key Node Identification in Hypergraphs via Representation Learning and Fine-Tuning
Evaluating node importance is a critical aspect of analyzing complex systems, with broad applications in digital marketing, rumor suppression, and disease control. However, existing methods typically rely on conventional network structures and fail to capture the polyadic interactions intrinsic to many real-world systems. To address this limitation, we study key node identification in hypergraphs, where higher-order interactions are naturally modeled as hyperedges. We propose a novel framework,…

Spectral Theory of Hypergraphs: A Survey
Shashwath S Shetty, K Arathi Bhat
https://arxiv.org/abs/2507.13664 https://arxiv.org/pdf/2507.13664

Spectral Theory of Hypergraphs: A Survey
Hypergraphs require higher-dimensional representations, which makes it more difficult to compute and interpret their spectral properties. This survey article uses the framework of hypermatrices to give an in-depth overview of the spectral theory of hypergraphs. Our focus in this article relies on the theoretical aspects of hypergraphs that help to ease the computational methods. Spectral theory hypergraphs, one of the most advanced fields of study, are constantly finding novel applications in v…

Some Maker-Breaker games on hypergraphs
Patrick Bennett, Alan Frieze, Wesley Pegden
https://arxiv.org/abs/2509.02788 https://arxiv.org/pdf/2509.02788

Some Maker-Breaker games on hypergraphs
We consider some biased Maker-Breaker games. Starting with the complete $k$-uniform hypergraph on $n$ vertices, at each turn Maker claims one edge, and then Breaker claims $b$ edges. Maker's goal is to obtain a set of edges having some increasing property. We consider the case where Maker's desired property is minimum degree $m$, or having a full-rank incidence matrix, or having a Berge Hamilton cycle or having a perfect matching or a Hamilton $\ell$-cycle.

Parameterised Counting Constraint Satisfaction Problems via Holants on Hypergraphs
Panagiotis Aivasiliotis, Andreas G\"obel, Marc Roth
https://arxiv.org/abs/2508.19794 http…

Parameterised Counting Constraint Satisfaction Problems via Holants on Hypergraphs
We study the complexity of the parameterised counting constraint satisfaction problem: given a set of constraints over a set of variables and a positive integer $k$, how many ways are there to assign $k$ variables to 1 (and the others to 0) such that all constraints are satisfied. Existing work has so far exclusively focused on restricted settings such as finding and counting homomorphisms between relational structures due to Grohe (JACM 2007) and Dalmau and Jonsson (TCS 2004), or the case of f…

Domination, matching and transversal numbers for Berge-$G$ hypergraphs
Mar\'ia Jos\'e Ch\'avez de Diego, Pablo Montero Moreno, Mar\'ia Trinidad Villar-Li\~n\'an
https://arxiv.org/abs/2507.22957

Domination, matching and transversal numbers for Berge-$G$ hypergraphs
Let $G=(V(G),E(G))$ be a graph and $H=(V(H),E(H))$ be a hypergraph. The hypergraph $H$ is a {\it Berge-G} if there is a bijection $f : E(G) \mapsto E(H)$ such that for each $e \in E(G)$ we have $e \subseteq f(e)$. We define {\it dilations of $G$} as a particular subfamily of not necessarily uniform Berge-$G$ hypergraphs. We examine domination, matching and transversal numbers and some relation between these parameters in that family of hypergraphs. Our work generalizes previous results concer…

Scalable Sample-to-Population Estimation of Hyperbolic Space Models for Hypergraphs
Cornelius Fritz, Yubai Yuan, Michael Schweinberger
https://arxiv.org/abs/2509.07031 https://

Scalable Sample-to-Population Estimation of Hyperbolic Space Models for Hypergraphs
Hypergraphs are useful mathematical representations of overlapping and nested subsets of interacting units, including groups of genes or brain regions, economic cartels, political or military coalitions, and groups of products that are purchased together. Despite the vast range of applications, the statistical analysis of hypergraphs is challenging: There are many hyperedges of small and large sizes, and hyperedges can overlap or be nested. We develop a novel statistical approach to hypergraphs…

A Fast Coloring Oracle for Average Case Hypergraphs
Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld, Asaf Shapira, Shlomo Tauber
https://arxiv.org/abs/2507.10691

A Fast Coloring Oracle for Average Case Hypergraphs
Hypergraph $2$-colorability is one of the classical NP-hard problems. Person and Schacht [SODA'09] designed a deterministic algorithm whose expected running time is polynomial over a uniformly chosen $2$-colorable $3$-uniform hypergraph. Lee, Molla, and Nagle recently extended this to $k$-uniform hypergraphs for all $k\geq 3$. Both papers relied heavily on the regularity lemma, hence their analysis was involved and their running time hid tower-type constants. Our first result in this paper is…

Lin-Lu-Yau Ricci curvature on hypergraphs
Yulu Tian, Liang Zhao
https://arxiv.org/abs/2507.04109 https://arxiv.org/pdf/2507.04109

Lin-Lu-Yau Ricci curvature on hypergraphs
In this paper, we introduce a unified framework for defining Lin-Lu-Yau (LLY) Ricci curvature on both undirected and directed hypergraphs. By establishing upper bounds and monotonicity properties for the parameterized curvature $κ_α$, we justify the well-posedness and compatibility of our definitions. Furthermore, we prove a Bonnet-Myers-type theorem for hypergraphs, which highlights the potential of LLY Ricci curvature in hypergraph analysis, particularly in studying geometric and structural…

Upper tails for homomorphism counts in sparse random hypergraphs
Nicholas A. Cook, Nguyen Nguyen
https://arxiv.org/abs/2509.26569 https://arxiv.org/pdf/250…

Upper tails for homomorphism counts in sparse random hypergraphs
The "infamous upper tail problem" for $r$-uniform hypergraphs is to estimate the probability that the number of copies of a fixed hypergraph $H$ in a large binomial $r$-uniform hypergraph $\boldsymbol{G}$ exceeds its expectation by a constant factor. The problem was popularized by Janson and Ruciński and, particularly in the case of graphs ($r=2$), has been a driving example in the development of nonlinear large deviations theory. Recent work of the first author with Dembo and Pham has accompl…

Uncovering multi-technology convergence patterns with hypergraphs: Evolution and prediction using patent data
Yiwei Huang, Shuqi Xu, Shimin Cai, Linyuan L\"u
https://arxiv.org/abs/2509.15521

Uncovering multi-technology convergence patterns with hypergraphs: Evolution and prediction using patent data
Technology convergence integrates distinct domains to create novel combinations, driving radical innovation that reshapes markets and industries. However, most approaches rely on pairwise networks that cannot capture multi-technology interactions and suffer scale biases from heterogeneous patenting activity. To overcome these gaps, we propose a hypergraph-based framework that directly models multi-technology convergence and identifies statistically significant convergence via a probabilistic nu…

Functional limit theorems for edge counts in dynamic random connection hypergraphs
Christian Hirsch, Benedikt Jahnel, P\'eter Juh\'asz
https://arxiv.org/abs/2507.16270

Functional limit theorems for edge counts in dynamic random connection hypergraphs
We introduce a dynamic random hypergraph model constructed from a bipartite graph. In this model, both vertex sets of the bipartite graph are generated by marked Poisson point processes. Vertices of both vertex sets are equipped with marks representing their weight that influence their connection radii. Additionally, we also assign the vertices of the first vertex set a birth-death process with exponential lifetimes and the vertices of the second vertex set a time instant representing the occur…

Local Clustering in Hypergraphs through Higher-Order Motifs
Giuseppe F. Italiano, Athanasios L. Konstantinidis, Anna Mpanti, Fariba Ranjbar
https://arxiv.org/abs/2507.10570

Local Clustering in Hypergraphs through Higher-Order Motifs
Hypergraphs provide a powerful framework for modeling complex systems and networks with higher-order interactions beyond simple pairwise relationships. However, graph-based clustering approaches, which focus primarily on pairwise relations, fail to represent higher-order interactions, often resulting in low-quality clustering outcomes. In this work, we introduce a novel approach for local clustering in hypergraphs based on higher-order motifs, small connected subgraphs in which nodes may be lin…

On the Chromatic Number of Stable Kneser Hypergraphs: Verifying the Conjecture for New Families
Hamid Reza Daneshpajouh
https://arxiv.org/abs/2509.22026 https://

On the Chromatic Number of Stable Kneser Hypergraphs: Verifying the Conjecture for New Families
One of the key unsolved conjectures in hypergraph coloring is about the chromatic number of $s$-stable $r$-uniform Kneser hypergraphs $\mathrm{KG}^r(n,k)_{s\textup{-stab}}$. The problem remains largely open, particularly in the case where $s > r\geq 3$. To the best of our knowledge, no information is available except a limited number of computations conducted for the instances when $r=3, 4$, $s=4, 5$, $k=2,3$ with some $n$ does not exceed 14. In this study, we verify the conjecture for infinity…

Modeling Non-Uniform Hypergraphs Using Determinantal Point Processes
Yichao Chen, Jingfei Zhang, Ji Zhu
https://arxiv.org/abs/2509.12028 https://arxiv.org/…

Modeling Non-Uniform Hypergraphs Using Determinantal Point Processes
Most statistical models for networks focus on pairwise interactions between nodes. However, many real-world networks involve higher-order interactions among multiple nodes, such as co-authors collaborating on a paper. Hypergraphs provide a natural representation for these networks, with each hyperedge representing a set of nodes. The majority of existing hypergraph models assume uniform hyperedges (i.e., edges of the same size) or rely on diversity among nodes. In this work, we propose a new hy…

Generalized Adaptation-Induced Non-universal Synchronization Transitions in Random Hypergraphs
Sangita Dutta, Pinaki Pal, Chittaranjan Hens
https://arxiv.org/abs/2507.18421 http…

Generalized Adaptation-Induced Non-universal Synchronization Transitions in Random Hypergraphs
We investigate the effect of partial order parameter adaptation in form of general functions on the synchronization behavior of coupled Kuramoto oscillators on top of random hypergraph models. The interactions between the oscillators are considered as pairwise and triangular. Using the Ott-Antonsen ansatz, we obtain a set of self-consistent equations of the order parameter that describe the synchronization diagrams. A broad diversity of synchronization transitions are observed as a result of th…

Constraint Hypergraphs as a Unifying Framework for Digital Twins
John Morris, Douglas L. Van Bossuyt, Edward Louis, Gregory Mocko, John Wagner
https://arxiv.org/abs/2507.05494

Constraint Hypergraphs as a Unifying Framework for Digital Twins
Digital twins, used to represent physical systems, have been lauded as tools for understanding reality. Complex system behavior is typically captured in domain-specific models crafted by subject experts. Contemporary methods for employing models in a digital twin require prescriptive interfaces, resulting in twins that are difficult to connect, redeploy, and modify. The limited interoperability of these twins has prompted calls for a universal framework enabling observability across model aggre…

Monadic non-definability and gain-graphic matroids
Daryl Funk, Angus Matthews, Dillon Mayhew
https://arxiv.org/abs/2510.00139 https://arxiv.org/pdf/2510.00…

Monadic non-definability and gain-graphic matroids
We present an analogue of a Myhill-Nerode characterisation which will allow us to prove that classes of hypergraphs cannot be defined by sentences in the counting monadic second-order logic of hypergraphs. We apply this to classes of gain-graphic matroids, and show that if the group $Γ$ is not uniformly locally finite, then the class of $Γ$-gain-graphic matroids is not monadically definable. (A group is uniformly locally finite if and only if there is a maximum size amongst subgroups generate…

Transitivity Preserving Projection in Directed Hypergraphs
Eric Parsonage, Matthew Roughan, Hung X Nguyen
https://arxiv.org/abs/2509.04543 https://arxiv.or…

Transitivity Preserving Projection in Directed Hypergraphs
Directed hypergraphs are vital for modeling complex polyadic relationships in domains such as discrete mathematics, computer science, network security, and systems modeling. However, their inherent complexity often impedes effective visualization and analysis, particularly for large graphs. This paper introduces a novel Transitivity Preserving Projection (TPP) to address the limitations of the computationally intensive Basu and Blanning projection (BBP), which can paradoxically increase complex…

Hypergraph modelling of wave scattering to speed-up material design
Kunwoo Park, Ikbeom Lee, Seungmok Youn, Gitae Lee, Namkyoo Park, Sunkyu Yu
https://arxiv.org/abs/2507.15329

Hypergraph modelling of wave scattering to speed-up material design
Hypergraphs offer a generalized framework for understanding complex systems, covering group interactions of different orders beyond traditional pairwise interactions. This modelling allows for the simplified description of simultaneous interactions among multiple elements in coupled oscillators, graph neural networks, and entangled qubits. Here, we employ this generalized framework to describe wave-matter interactions for material design acceleration. By devising the set operations for multipar…

Marked multi-colorings and marked chromatic polynomials of hypergraphs and subspace arrangements
Chaithra P, Shushma Rani, R. Venkatesh
https://arxiv.org/abs/2507.20847 https://…

Marked multi-colorings and marked chromatic polynomials of hypergraphs and subspace arrangements
We introduce the concepts of marked multi-colorings, marked chromatic polynomials, and marked (multivariate) independence series for hypergraphs. We show that the coefficients of the q-th power of the marked independence series of a hypergraph coincide with its marked chromatic polynomials in q, thereby generalizing a corresponding result for graphs established in Chaithra et al. 2025 (arXiv:2503.11230). These notions are then naturally extended to subspace arrangements. In particular, we prove…

Replaced article(s) found for cs.DM. https://arxiv.org/list/cs.DM/new
[1/1]:
- A Tale of Santa Claus, Hypergraphs and Matroids
Sami Davies, Thomas Rothvoss, Yihao Zhang

Spectral Tur\'an-type problems for the $\alpha$-spectral radius of hypergraphs with degree stability
Jian Zheng, Honghai Li, Li Su
https://arxiv.org/abs/2509.24354 https://

Spectral Turán-type problems for the $α$-spectral radius of hypergraphs with degree stability
An $r$-pattern $P$ is defined as an ordered pair $P=([l],E)$, where $l$ is a positive integer and $E$ is a set of $r$-multisets with elements from $[l]$. An $r$-graph $H$ is said to be $P$-colorable if there is a homomorphism $ϕ$: $V(H)\rightarrow [l]$ such that the $r$-multiset $\{ϕ(v_{1}),\ldots,ϕ(v_{r})\}$ is in $E$ for every edge $\{v_{1},\ldots,v_{r}\}\in E(H)$. Let $Col(P)$ denote the family of all $P$-colorable $r$-graphs. This paper establishes spectral extremal results for $α$-spec…

Uncovering High-Order Cohesive Structures: Efficient (k,g)-Core Computation and Decomposition for Large Hypergraphs
Dahee Kim, Hyewon Kim, Song Kim, Minseok Kim, Junghoon Kim, Yeon-Chang Lee, Sungsu Lim
https://arxiv.org/abs/2507.08328

Uncovering High-Order Cohesive Structures: Efficient (k,g)-Core Computation and Decomposition for Large Hypergraphs
Hypergraphs, increasingly utilised to model complex and diverse relationships in modern networks, have gained significant attention for representing intricate higher-order interactions. Among various challenges, cohesive subgraph discovery is one of the fundamental problems and offers deep insights into these structures, yet the task of selecting appropriate parameters is an open question. To address this question, we aim to design an efficient indexing structure to retrieve cohesive subgraphs …

Replaced article(s) found for nlin.PS. https://arxiv.org/list/nlin.PS/new
[1/1]:
- Chimera states on m-directed hypergraphs
Rommel Tchinda Djeudjo, Timoteo Carletti, Hiroya Nakao, Riccardo Muolo

Replaced article(s) found for cs.DS. https://arxiv.org/list/cs.DS/new
[1/1]:
- A Tale of Santa Claus, Hypergraphs and Matroids
Sami Davies, Thomas Rothvoss, Yihao Zhang

A Smooth Computational Transition in Tensor PCA
Zhangsong Li
https://arxiv.org/abs/2509.09904 https://arxiv.org/pdf/2509.09904

A Smooth Computational Transition in Tensor PCA
We propose an efficient algorithm for tensor PCA based on counting a specific family of weighted hypergraphs. For the order-$p$ tensor PCA problem where $p \geq 3$ is a fixed integer, we show that when the signal-to-noise ratio is $λn^{-\frac{p}{4}}$ where $λ=Ω(1)$, our algorithm succeeds and runs in time $n^{C+o(1)}$ where $C=C(λ)$ is a constant depending on $λ$. This algorithm improves a poly-logarithmic factor compared to previous algorithms based on the Sum-of-Squares hierarchy \cite{H…

Spectral radius of simplicial complexes without holes
Yi-Zheng Fan, Chuan-Ming She
https://arxiv.org/abs/2507.22518 https://arxiv.org/pdf/2507.22518…

Spectral radius of simplicial complexes without holes
The Turán problem for hypergraphs and its spectral version is a central and challenging topic in extremal combinatorics. In this paper, we view hypergraphs from the perspective of simplicial complexes, and investigate the spectral version of Turán problem for simplicial complexes. We characterize the simplicial complex that maximizes the signless Laplacian spectral radius among all hole-free simplicial complexes, and establish an upper bound on the spectral radius for simplicial complexes wit…

HIP: Model-Agnostic Hypergraph Influence Prediction via Distance-Centrality Fusion and Neural ODEs
Su-Su Zhang, JinFeng Xie, Yang Chen, Min Gao, Cong Li, Chuang Liu, Xiu-Xiu Zhan
https://arxiv.org/abs/2508.15312

HIP: Model-Agnostic Hypergraph Influence Prediction via Distance-Centrality Fusion and Neural ODEs
Predicting user influence in social networks is a critical problem, and hypergraphs, as a prevalent higher-order modeling approach, provide new perspectives for this task. However, the absence of explicit cascade or infection probability data makes it particularly challenging to infer influence in hypergraphs. To address this, we introduce HIP, a unified and model-independent framework for influence prediction without knowing the underlying spreading model. HIP fuses multi-dimensional centralit…

Approximating 1-in-3 SAT by linearly ordered hypergraph 3-colouring is NP-hard
Andrei Krokhin, Danny Vagnozzi
https://arxiv.org/abs/2508.14606 https://arxi…

Approximating 1-in-3 SAT by linearly ordered hypergraph 3-colouring is NP-hard
Given a satisfiable instance of 1-in-3 SAT, it is NP-hard to find a satisfying assignment for it, but it may be possible to efficiently find a solution subject to a weaker (not necessarily Boolean) predicate than `1-in-3'. There is a folklore conjecture predicting which choices of weaker predicates lead to tractability and for which the task remains \NP-hard. One specific predicate, corresponding to the problem of linearly ordered $3$-colouring of 3-uniform hypergraphs, has been mentioned in se…

Replaced article(s) found for physics.data-an. https://arxiv.org/list/physics.data-an/new
[1/1]:
- Entropy-based models to randomize real-world hypergraphs
Fabio Saracco, Giovanni Petri, Renaud Lambiotte, Tiziano Squartini

Odd Ramsey numbers of multipartite graphs and hypergraphs
Nicholas Crawford, Emily Heath, Owen Henderschedt, Coy Schwieder, Shira Zerbib
https://arxiv.org/abs/2507.19456 https:/…

Odd Ramsey numbers of multipartite graphs and hypergraphs
Given a hypergraph $G$ and a subhypergraph $H$ of $G$, the \emph{odd Ramsey number} $r_{odd}(G,H)$ is the minimum number of colors needed to edge-color $G$ so that every copy of $H$ intersects some color class in an odd number of edges. Generalizing a result of \cite{BHZ} in two different ways, in this paper we prove $r_{odd} \left(K_{n,n}, K_{2,t} \right)=\frac{n}{t} + o(n)$ for all $t\geq 2$, and $r_{odd} \left(\mathcal{K}^{(k)}_{n,\dots,n}, \mathcal{K}_{1,\dots,1,2,2} \right) = \frac{n}{2} +…

Hypergraph Splitting-Off via Element-Connectivity Preserving Reductions
Karthekeyan Chandrasekaran, Chandra Chekuri, Shubhang Kulkarni
https://arxiv.org/abs/2508.18637 https://

Hypergraph Splitting-Off via Element-Connectivity Preserving Reductions
Bérczi, Chandrasekaran, Király, and Kulkarni (ICALP 2024) recently described a splitting-off procedure in hypergraphs that preserves local-connectivity and outlined some applications. In this note we give an alternative proof via element-connectivity preserving reduction operations in graphs.

Perfect Matchings in Random Sparsifications of Dense Hypergraphs
Jie Han, Jingwen Zhao
https://arxiv.org/abs/2507.11359 https://arxiv…

Perfect Matchings in Random Sparsifications of Dense Hypergraphs
The decision problem of perfect matchings in uniform hypergraphs is famously an NP-complete problem. It has been shown by Keevash--Knox--Mycroft [STOC, 2013] that for every $\varepsilon>0$, such decision problem restricted to $k$-uniform hypergraphs $H$ satisfying that every $(k-1)$-set of vertices is in at least $(1/k+\varepsilon)|H|$ edges is tractable, and the quantity $1/k$ is best possible. In this paper we study the existence of perfect matchings in the random $p$-sparsification…

Replaced article(s) found for nlin.PS. https://arxiv.org/list/nlin.PS/new
[1/1]:
- Chimera states on m-directed hypergraphs
Rommel Tchinda Djeudjo, Timoteo Carletti, Hiroya Nakao, Riccardo Muolo

HIF: The hypergraph interchange format for higher-order networks
Mart\'in Coll, Cliff A. Joslyn, Nicholas W. Landry, Quintino Francesco Lotito, Audun Myers, Joshua Pickard, Brenda Praggastis, Przemys{\l}aw Szufel
https://arxiv.org/abs/2507.11520

HIF: The hypergraph interchange format for higher-order networks
Many empirical systems contain complex interactions of arbitrary size, representing, for example, chemical reactions, social groups, co-authorship relationships, and ecological dependencies. These interactions are known as higher-order interactions and the collection of these interactions comprise a higher-order network, or hypergraph. Hypergraphs have established themselves as a popular and versatile mathematical representation of such systems and a number of software packages written in vario…

Replaced article(s) found for nlin.AO. https://arxiv.org/list/nlin.AO/new
[1/1]:
- Chimera states on m-directed hypergraphs
Rommel Tchinda Djeudjo, Timoteo Carletti, Hiroya Nakao, Riccardo Muolo

Statistical Inference for Subgraph Frequencies of Exchangeable Hyperedge Models
Ayoushman Bhattacharya, Nilanjan Chakraborty, Robert Lunde
https://arxiv.org/abs/2508.13258 https…

Statistical Inference for Subgraph Frequencies of Exchangeable Hyperedge Models
In statistical network analysis, models for binary adjacency matrices satisfying vertex exchangeability are commonly used. However, such models may fail to capture key features of the data-generating process when interactions, rather than nodes, are fundamental units. We study statistical inference for subgraph counts under an exchangeable hyperedge model. We introduce several classes of subgraph statistics for hypergraphs and develop inferential tools for subgraph frequencies that account for …

Eigenvalue Distribution of Large Weighted Random Sparse Uniform $q$-Hypergraphs
Valentin Vengerovsky
https://arxiv.org/abs/2508.13297 https://arxiv.org/pdf…

Eigenvalue Distribution of Large Weighted Random Sparse Uniform $q$-Hypergraphs
We study eigenvalue distribution of the adjacency matrix $A^{(N,p,q)}$ of weighted random uniform $q$-hypergraphs $Γ= Γ_{N,p,q}$. We assume that the graphs have $N$ vertices and the average number of hyperedges attached to one vertex is $(q-1)!\cdot p$. To each edge of the graph $e_{ij}$ we assign a weight given by a random variable $a_{ij}$ with all moments finite. We consider the moments of normalized eigenvalue counting function $σ_{N,p,q}$ of $A^{(N,p,q)}$. Assuming all moments of $a$ fi…

On the Complexity of Hyperpath and Minimal Separator Enumeration in Directed Hypergraphs
Kazuhiro Kurita, Kevin Mann
https://arxiv.org/abs/2507.07528 https…

On the Complexity of Hyperpath and Minimal Separator Enumeration in Directed Hypergraphs
In this paper, we address the enumeration of (induced) $s$-$t$ paths and minimal $s$-$t$ separators. These problems are some of the most famous classical enumeration problems that can be solved in polynomial delay by simple backtracking for a (un)directed graph. As a generalization of these problems, we consider the (induced) $s$-$t$ hyperpath and minimal $s$-$t$ separator enumeration in a \emph{directed hypergraph}. We show that extending these classical enumeration problems to directed hyperg…

Unbounded degree spanning hypertrees in Dirac hypergraphs
Yaobin Chen, Seonghyuk Im, Junchi Zhang
https://arxiv.org/abs/2508.06843 https://arxiv.org/pdf/25…

Unbounded degree spanning hypertrees in Dirac hypergraphs
In 2001, Komlós, Sárközy, and Szemerédi proved that every sufficiently large $n$-vertex graph with minimum degree at least $\left(1/2+γ\right)n$ contains all spanning trees with maximum degree at most $cn/\log n$. We extend this result to hypergraphs by considering loose hypertrees, which are linear hypergraphs obtained by successively adding edges that share exactly one vertex with a previous edge. For all $k > \ell \geq 2$, we determine asymptotically optimal $\ell$-degree conditions t…

Optimization of geometric hypergraph embedding
Francesco Zigliotto, Desmond J. Higham
https://arxiv.org/abs/2509.08772 https://arxiv.org/pdf/2509.08772

Optimization of geometric hypergraph embedding
We consider the problem of embedding the nodes of a hypergraph into Euclidean space under the assumption that the interactions arose through closeness to unknown hyperedge centres. In this way, we tackle the inverse problem associated with the generation of geometric random hypergraphs. We propose two new spectral algorithms; both of these exploit the connection between hypergraphs and bipartite graphs. The assumption of an underlying geometric structure allows us to define a concrete measure o…

Source characterization of the hypergraphic posets
F\'elix G\'elinas
https://arxiv.org/abs/2508.16006 https://arxiv.org/pdf/2508.16006

Source characterization of the hypergraphic posets
For a hypergraph $\mathbb{H}$ on $[n]$, the hypergraphic poset $P_\mathbb{H}$ is the transitive closure of the oriented $1$-skeleton of the hypergraphic polytope $Δ_\mathbb{H}$. In a recent paper, N. Bergeron and V. Pilaud provided a characterization of $P_\mathbb{H}$ based on the sources of acyclic orientations for interval hypergraphs. The goal of this work is to extend this source characterization of $P_\mathbb{H}$ for arbitrary hypergraphs on $[n]$.

Replaced article(s) found for nlin.AO. https://arxiv.org/list/nlin.AO/new
[1/1]:
- Chimera states on m-directed hypergraphs
Rommel Tchinda Djeudjo, Timoteo Carletti, Hiroya Nakao, Riccardo Muolo

On the Estrada Index and Spectral Properties of $k$-Uniform Hypergraphs
Liya Jess Kurian, Chithra A. V
https://arxiv.org/abs/2507.06322 https://

On the Estrada Index and Spectral Properties of $k$-Uniform Hypergraphs
Various properties of a hypergraph can be explored through its spectrum. In this paper,we estimate the bound for the sum of $t,\,t\in[1,n]$, largest eigenvalues of a $k$-uniform hypergraph of order $n$. Also, we characterize the $k$-uniform hypergraph with two distinct eigenvalues. We establish bounds for the Estrada index of $k$-uniform hypergraphs based on their number of edges, order and energy. In addition, we obtain the second largest Estrada index among the unicyclic hypergraphs.

Replaced article(s) found for physics.soc-ph. https://arxiv.org/list/physics.soc-ph/new
[1/1]:
- Hypermodularity and community detection in hypergraphs
Charo I. del Genio

On Sidorenko exponents of hypergraphs
Hyunwoo Lee
https://arxiv.org/abs/2509.08680 https://arxiv.org/pdf/2509.08680…

On Sidorenko exponents of hypergraphs
For an $r$-graph $F$, define Sidorenko exponent $s(F)$ as $$s(F):= \sup \{s \geq 0: \exists \text{$r$-graph $H$ s.t. } t_F(H) = t_{K^{(r)}_r} (H)^s > 0\},$$ where $t_{H_1}(H_2)$ denotes the homomorphism density of $H_1$ in $H_2$. The celebrated Sidorenko's conjecture states that $s(F) = e(F)$ holds for every bipartite graph $F$. It is known that for all $r \geq 3$, the $r$-uniform version of Sidorenko's conjecture is false, and only a few hypergraphs are known to be Sidorenko. In this paper, …

Uniform Tur\'an density beyond 3-graphs
Ander Lamaison
https://arxiv.org/abs/2508.20696 https://arxiv.org/pdf/2508.20696…

Uniform Turán density beyond 3-graphs
In the 1980s, Erdős and Sós first introduced an extremal problem on hypergraphs with density constraints. Given an $r$-uniform hypergraph $F$ (or $r$-graph for short), its uniform Turán density $π_u(F)$ is the smallest value of $d$ in which every hypergraph $H$ in which every linear-sized subhypergraph of $H$ has edge density at least $d$ contains $F$ as a subgraph. The first non-zero value of $π_u(F)$ was not found until 30 years later. Progress in studying the set of values of the unif…

Off-Diagonal Ramsey Numbers for Linear Hypergraphs
Xiaoyu He, Jiaxi Nie, Yuval Wigderson, Hung-Hsun Hans Yu
https://arxiv.org/abs/2507.05641 https://

Off-Diagonal Ramsey Numbers for Linear Hypergraphs
We study off-diagonal Ramsey numbers $r(H, K_n^{(k)})$ of $k$-uniform hypergraphs, where $H$ is a fixed linear $k$-uniform hypergraph and $K_n^{(k)}$ is complete on $n$ vertices. Recently, Conlon et al.\ disproved the folklore conjecture that $r(H, K_n^{(3)})$ always grows polynomially in $n$. In this paper we show that much larger growth rates are possible in higher uniformity. In uniformity $k\ge 4$, we prove that for any constant $C>0$, there exists a linear $k$-uniform hypergraph $H$ for wh…

Replaced article(s) found for cs.SI. https://arxiv.org/list/cs.SI/new
[1/1]:
- Entropy-based models to randomize real-world hypergraphs
Fabio Saracco, Giovanni Petri, Renaud Lambiotte, Tiziano Squartini

Transversal packings in families of percolated hypergraphs
Jie Han, Jie Hu, Shunan Wei, Donglei Yang
https://arxiv.org/abs/2507.12740 https://

Transversal packings in families of percolated hypergraphs
Let $F$ be a strictly $1$-balanced $k$-graph on $s$ vertices with $t$ edges and $δ_{F,d}^T$ be the infimum of $δ>0$ such that for every $α>0$ and sufficiently large $n\in \mathbb{N}$, every $k$-graph system $\mathbf H=\{H_{1}, H_{2}, \dots ,H_{tn}\}$ on the same $sn$ vertices with $δ_d(H_i)\ge (δ+α)\binom{sn-d}{k-d}$, $i\in [tn]$ contains a transversal $F$-factor, that is, an $F$-factor consisting of exactly one edge from each $H_i$. In this paper we prove the following result. Let $\math…

Replaced article(s) found for nlin.AO. https://arxiv.org/list/nlin.AO/new
[1/1]:
- Edge Correlations and Link Prediction in Growing Hypergraphs
Xie He, Philip S. Chodrow, Peter J. Mucha

Finding Partite Hypergraphs Efficiently
Ferran Espu\~na
https://arxiv.org/abs/2508.10641 https://arxiv.org/pdf/2508.10641

Finding Partite Hypergraphs Efficiently
We provide a deterministic polynomial-time algorithm that, for a given $k$-uniform hypergraph $H$ with $n$ vertices and edge density $d$, finds a complete $k$-partite subgraph of $H$ with parts of size at least ${c(d, k)(\log n)^{1/(k-1)}}$. This generalizes work by Mubayi and Turán on bipartite graphs. The value we obtain for the part size matches the order of magnitude guaranteed by the non-constructive proof due to Erdős and is tight up to a constant factor.

Parking functions and chip-firing on hypergraphs
Timothy Blanton, Anton Dochtermann, Isabelle Hong, SuHo Oh, Zhan Zhan
https://arxiv.org/abs/2508.09720 https://

Parking functions and chip-firing on hypergraphs
For a connected graph $G$ with sink vertex $q$, a $G$-parking function is a vector of nonnegative integers whose entries are determined by cut-sets in $G$. Such objects also arise as the superstable configurations in the context of chip-firing. The set of all $G$-parking functions have various algebraic and combinatorial properties; for instance they relate to evaluations of the Tutte polynomial and in particular are counted by spanning trees of $G$. We extend these constructions to the setting…

Effective and Efficient Attributed Hypergraph Embedding on Nodes and Hyperedges
Yiran Li, Gongyao Guo, Chen Feng, Jieming Shi
https://arxiv.org/abs/2508.08807 https://

Effective and Efficient Attributed Hypergraph Embedding on Nodes and Hyperedges
An attributed hypergraph comprises nodes with attributes and hyperedges that connect varying numbers of nodes. Attributed hypergraph node and hyperedge embedding (AHNEE) maps nodes and hyperedges to compact vectors for use in important tasks such as node classification, hyperedge link prediction, and hyperedge classification. Generating high-quality embeddings is challenging due to the complexity of attributed hypergraphs and the need to embed both nodes and hyperedges, especially in large-scal…

Averages of hypergraphs and higher arity stability
Artem Chernikov, Henry Towsner
https://arxiv.org/abs/2508.05839 https://arxiv.org/pdf/2508.05839

Averages of hypergraphs and higher arity stability
We show that $k$-ary functions giving the measure of the intersection of multi-parametric families of sets in probability spaces, e.g. $(x,y,z) \in X \times Y \times Z \mapsto μ(P_{x,y} \cap Q_{x,z} \cap R_{y,z})$, satisfy a particularly strong form of hypergraph regularity. More generally, this applies to the (integral) averages of continuous combinations of functions of smaller arity. This result is connected to higher arity stability in model theory, that we discuss in the second part of th…

When higher-order interactions enhance synchronization: the case of the Kuramoto model
Riccardo Muolo, Hiroya Nakao, Marco Coraggio
https://arxiv.org/abs/2508.10992 https://

When higher-order interactions enhance synchronization: the case of the Kuramoto model
Synchronization is a fundamental phenomenon in complex systems, observed across a wide range of natural and engineered contexts. The Kuramoto model provides a foundational framework for understanding synchronization among coupled oscillators, traditionally assuming pairwise interactions. However, many real-world systems exhibit group and many-body interactions, which can be effectively modeled through hypergraphs. Previous studies suggest that higher-order interactions shrink the attraction bas…

Property O and Erd\H{o}s--Szekeres properties in linear hypergraphs
Suyun Jiang, Ander Lamaison, Minghui Ouyang
https://arxiv.org/abs/2509.08692 https://ar…

Property O and Erdős--Szekeres properties in linear hypergraphs
An oriented $k$-uniform hypergraph, or oriented $k$-graph, is said to satisfy Property O if, for every linear ordering of its vertex set, there is some edge oriented consistently with this order. The minimum number $f(k)$ of edges in a $k$-graph with Property O was first studied by Duffus, Kay, and Rödl, and later improved by Kronenberg, Kusch, Lamaison, Micek, and Tran. In particular, they established the bounds $k! + 1 \le f(k) \le \left(\lfloor\tfrac{k}{2}\rfloor+1 \right) k! - \lfloor\tfra…

Hypergraphs without complete partite subgraphs
Dhruv Mubayi
https://arxiv.org/abs/2507.06390 https://arxiv.org/pdf/2507.06390

Hypergraphs without complete partite subgraphs
Fix integers $r \ge 2$ and $2\le s_1\le \cdots \le s_{r-1}\le s_r$ and set $S=\prod_{i=1}^{r-1}s_i$. Let $K=K(s_1, \ldots, s_{r-1}, s_r)$ denote the complete $r$-partite $r$-uniform hypergraph with parts of size $s_1, \ldots, s_{r-1}, s_r$. We prove that the maximum number of edges in an $r$-partite $r$-uniform hypergraph with parts $X_1, \ldots, X_r$ each of size $n$ with no copy of $K$ where the part of size $s_i$ is in $X_i$ for all $i$ is $n^{r-1/S-o(1)}$ provided $s_r> 3^{S+o(S)}$. In othe…

On the Independence Numbers of the Cyclic Van der Waerden Hypergraphs
Benjamin Liber
https://arxiv.org/abs/2509.07926 https://arxiv.org/pdf/2509.07926

On the Independence Numbers of the Cyclic Van der Waerden Hypergraphs
Building upon the work of Berglund (2018), we establish a method for constructing subsets $B \subseteq \mathbb{Z}_{mk}$ such that $B$ does not contain any $k$-term cyclic arithmetic progressions mod $mk$, where $m,k \in \mathbb{Z}^+$ with $k \geq 3$. This construction thereby provides concrete lower bounds for the maximum size of such subsets. Additionally, it allows us to tightly bound specific chromatic numbers $χ(mk,k)$ of $\mathbb{Z}_{mk}$ and helps increase the lower bounds of certain cyc…

Spectrum and local weak convergence of sparse random uniform hypergraphs
Kartick Adhikari, Samiron Parui
https://arxiv.org/abs/2509.05102 https://arxiv.org…

Spectrum and local weak convergence of sparse random uniform hypergraphs
The notion of local weak convergence, also known as Benjamini--Schramm convergence, was introduced by Benjamini and Schramm \cite{Benjamini-Schramm-convergence}. It is known that the local weak limit of sparse Erd\H os--Rényi graphs is the Galton--Watson measure with Poisson offspring almost surely. Recently, Adhikari, Kumar and Saha \cite{adhikari2023spectrumrandomsimplicialcomplexes} showed that the local weak limit of the line graph of sparse Linial--Meshulam complexes is the $d$-block Galt…

Replaced article(s) found for math.CO. https://arxiv.org/list/math.CO/new
[1/1]:
- The chromatic number of triangle-free hypergraphs
Lina Li, Luke Postle
https:…

Replaced article(s) found for math.CO. https://arxiv.org/list/math.CO/new
[1/1]:
- The Matching Ramsey Number of Hypergraphs, Revisited
Saeed Shaebani, Meysam Alishahi

A simple proof of a $(p,2)$-theorem for non-piercing regions
Chaya Keller, Shakhar Smorodinsky
https://arxiv.org/abs/2507.07269 https://

A simple proof of a $(p,2)$-theorem for non-piercing regions
A family of sets satisfies the $(p,2)$-property if among any $p$ sets in the family, some two intersect. Two recent works used elaborate geometric techniques to show that any family of non-piercing regions in the plane that satisfies the $(p,2)$-property can be pierced by $O(p^9)$ points. In this note we show that even in a much more general setting, piercing by $O(p)$ points can be deduced from known results on hypergraphs with a hereditarily linear Delaunay graph, which include intersection h…