Tootfinder

The Complexity of Counting Small Sub-Hypergraphs
Marco Bressan, Julian Brinkmann, Holger Dell, Marc Roth, Philip Wellnitz
https://arxiv.org/abs/2506.14081 …

The Complexity of Counting Small Sub-Hypergraphs
Subgraph counting is a fundamental and well-studied problem whose computational complexity is well understood. Quite surprisingly, the hypergraph version of subgraph counting has been almost ignored. In this work, we address this gap by investigating the most basic sub-hypergraph counting problem: given a (small) hypergraph $H$ and a (large) hypergraph $G$, compute the number of sub-hypergraphs of $G$ isomorphic to $H$. Formally, for a family $\mathcal{H}$ of hypergraphs, let #Sub($\mathcal{H}$…

Is it easy to regularize a hypergraph with easy links?
Lior Gishboliner, Asaf Shapira, Yuval Wigderson
https://arxiv.org/abs/2506.15582 https://

Is it easy to regularize a hypergraph with easy links?
A partition of a (hyper)graph is $\varepsilon$-homogenous if the edge densities between almost all clusters are either at most $\varepsilon$ or at least $1-\varepsilon$. Suppose a $3$-graph has the property that the link of every vertex has an $\varepsilon$-homogenous partition of size $\text{poly}(1/\varepsilon)$. Does this guarantee that the $3$-graph also has a small homogenous partition? Terry and Wolf proved that such a $3$-graph has an $\varepsilon$-homogenous partition of size given by a…

Solving Package Management via Hypergraph Dependency Resolution
Ryan Gibb, Patrick Ferris, David Allsopp, Michael Winston Dales, Mark Elvers, Thomas Gazagnaire, Sadiq Jaffer, Thomas Leonard, Jon Ludlam, Anil Madhavapeddy
https://arxiv.org/abs/2506.10803

Solving Package Management via Hypergraph Dependency Resolution
Package managers are everywhere, with seemingly every language and operating system implementing their own solution. The lack of interoperability between these systems means that multi-lingual projects are unable to express precise dependencies across language ecosystems, and external system and hardware dependencies are typically implicit and unversioned. We define HyperRes, a formal system for describing versioned dependency resolution using a hypergraph that is expressive enough to model man…

Minimal hypergraph non-jumps
Benedict Randall Shaw
https://arxiv.org/abs/2506.09620 https://arxiv.org/pdf/2506.09620

Minimal hypergraph non-jumps
An $r$-uniform hypergraph, or $r$-graph, has density $|E(G)|/|V(G)^{(r)}|$. We say $α$ is a jump for $r$-graphs if there is some constant $δ=δ(α)$ such that, for each $\varepsilon>0$ and $n\geq r$, any sufficiently large $r$-graph of density at least $\varepsilon$ has a subgraph of order $n$ and density at least $α+δ$. For $r=2$, all $α$ are jumps. For $r\geq 3$, Erdős showed all $[0,\frac{r!}{r^r})$ are jumps, and conjectured all $[0,1)$ are jumps. Since then, a var…

Dynamic Hypergraph Partitioning of Quantum Circuits with Hybrid Execution
Shane Sweeney, Krishnendu Guha
https://arxiv.org/abs/2506.09963 https://

Dynamic Hypergraph Partitioning of Quantum Circuits with Hybrid Execution
Quantum algorithms offer an exponential speedup over classical algorithms for a range of computational problems. The fundamental mechanisms underlying quantum computation required the development and construction of quantum computers. These devices are referred to as NISQ (Noisy Intermediate-Scale Quantum) devices. Not only are NISQ devices extremely limited in their qubit count but they also suffer from noise during computation and this problem only gets worse as the size of the circuit increa…

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

Optimizing hypergraph product codes with random walks, simulated annealing and reinforcement learning
Hypergraph products are quantum low-density parity-check (LDPC) codes constructed from two classical LDPC codes. Although their dimension and distance depend only on the parameters of the underlying classical codes, optimizing their performance against various noise channels remains challenging. This difficulty partly stems from the complexity of decoding in the quantum setting. The standard, ad hoc approach typically involves selecting classical LDPC codes with large girth. In this work, we fo…

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

Hypergraph Tversky-Aware Domain Incremental Learning for Brain Tumor Segmentation with Missing Modalities
Existing methods for multimodal MRI segmentation with missing modalities typically assume that all MRI modalities are available during training. However, in clinical practice, some modalities may be missing due to the sequential nature of MRI acquisition, leading to performance degradation. Furthermore, retraining models to accommodate newly available modalities can be inefficient and may cause overfitting, potentially compromising previously learned knowledge. To address these challenges, we p…

Oriented hypergraphs and generalizing the Harary-Sachs theorem to integer matrices
Blake Dvarishkis, Josephine Reynes, Lucas J. Rusnak
https://arxiv.org/abs/2506.12271

Oriented hypergraphs and generalizing the Harary-Sachs theorem to integer matrices
Incidence-based generalizations of cycle covers, called contributors, extend the Harary-Sachs coefficient theorem for characteristic polynomials of the adjacency matrix of graphs. All minors of the Laplacian resulting from an integer matrix are characterized using their associated oriented hypergraph through a new minimal collection of contributors to produce the coefficients of the total-minor polynomial. We prove that the natural grouping of contributors via tail-equivalence is necessarily ca…

ELRUHNA: Elimination Rule-basedHypergraph Alignment
Cameron Ibrahim, S M Ferdous, Ilya Safro, Marco Minutoli, Mahantesh Halappanavar
https://arxiv.org/abs/2506.09866

ELRUHNA: Elimination Rule-basedHypergraph Alignment
Hypergraph alignment is a well-known NP-hard problem with numerous practical applications across domains such as bioinformatics, social network analysis, and computer vision. Despite its computational complexity, practical and scalable solutions are urgently needed to enable pattern discovery and entity correspondence in high-order relational data. The problem remains understudied in contrast to its graph based counterpart. In this paper, we propose ELRUHNA, an elimination rule-based framework …

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/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…

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…

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.

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

Graded Betti numbers of a hyperedge ideal associated to join of graphs
Let $G$ be a finite simple graph on the vertex set $V(G)$ and let $r$ be a positive integer. We consider the hypergraph $\mathrm{Con}_r(G)$ whose vertices are the vertices of $G$ and the (hyper)edges are all $A\subseteq V(G)$ such that $|A|=r+1$ and the induced subgraph $G[A]$ is connected. The (hyper)edge ideal $I_r(G)$ of $\mathrm{Con}_r(G)$ is also the Stanley-Reisner ideal of a generalisation of the independence complex of $G$, called the $r$-independence complex $\mathrm{Ind}_r(G…

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…

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…

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). …

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

Graded Betti numbers of a hyperedge ideal associated to join of graphs
Let $G$ be a finite simple graph on the vertex set $V(G)$ and let $r$ be a positive integer. We consider the hypergraph $\mathrm{Con}_r(G)$ whose vertices are the vertices of $G$ and the (hyper)edges are all $A\subseteq V(G)$ such that $|A|=r+1$ and the induced subgraph $G[A]$ is connected. The (hyper)edge ideal $I_r(G)$ of $\mathrm{Con}_r(G)$ is also the Stanley-Reisner ideal of a generalisation of the independence complex of $G$, called the $r$-independence complex $\mathrm{Ind}_r(G…

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 $�…

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…

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

Graded Betti numbers of a hyperedge ideal associated to join of graphs
Let $G$ be a finite simple graph on the vertex set $V(G)$ and let $r$ be a positive integer. We consider the hypergraph $\mathrm{Con}_r(G)$ whose vertices are the vertices of $G$ and the (hyper)edges are all $A\subseteq V(G)$ such that $|A|=r+1$ and the induced subgraph $G[A]$ is connected. The (hyper)edge ideal $I_r(G)$ of $\mathrm{Con}_r(G)$ is also the Stanley-Reisner ideal of a generalisation of the independence complex of $G$, called the $r$-independence complex $\mathrm{Ind}_r(G…

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…

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.

On the quadratic 8-edge case of the Brown-Erd\H{o}s-S\'os problem
Oleg Pikhurko, Shumin Sun
https://arxiv.org/abs/2506.01739 https://

On the quadratic 8-edge case of the Brown-Erdős-Sós problem
Let $f^{(r)}(n;s,k)$ be the maximum number of edges in an $n$-vertex $r$-uniform hypergraph containing no $k$ edges on at most $s$ vertices. Brown, Erdős and Sós conjectured in 1973 that the limit $\lim_{n\rightarrow \infty}n^{-2}f^{(3)}(n;k+2,k)$ exists for all $k$. Recently, Delcourt and Postle settled the conjecture and their approach was generalised by Shangguan to every uniformity $r\ge 4$: the limit $\lim_{n\rightarrow \infty}n^{-2}f^{(r)}(n;rk-2k+2,k)$ exists for all $r\ge 3$ and $k\ge…

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 …

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

Multipartite nearly orthogonal sets over finite fields
For a field $\mathbb{F}$ and integers $d, k$ and $\ell$, a set $A \subseteq \mathbb{F}^d$ is called $(k,\ell)$-nearly orthogonal if all vectors in $A$ are non-self-orthogonal and every $k+1$ vectors in $A$ contain $\ell + 1$ pairwise orthogonal vectors. Recently, Haviv, Mattheus, Milojević and Wigderson have improved the lower bound on nearly orthogonal sets over finite fields, using counting arguments and a hypergraph container lemma. They showed that for every prime $p$ and an integer $\ell$…