Narrow Results

Given a hypergraph ${\mathscr{H}}$, we introduce a new class of evaluation toric codes called edge codes derived from ${\mathscr{H}}$. We analyze these codes, focusing on determining their basic parameters. We provide estimations for the minimum distance, particularly in scenarios involving $d$-uniform clutters. Additionally, we demonstrate that these codes exhibit self-orthogonality. Furthermore, we compute the minimum distances of edge codes for all graphs with five vertices.

A hypergraph is called uniformly δ-sparse if for every nonempty subset X ⊆ V of vertices, the average degree of the sub-hypergraph of induced by X is at most δ. We show that there is a deterministic algorithm that, given a uniformly δ-sparse hypergraph , and a positive integer k, outputs k or all minimal transversals for in O(δlog(1 + k)polylog(δ|V|))-time using |V|^O(logδ)k^O(δ) processors. Equivalently, the algorithm can be used to compute in parallel k or all maximal independent sets for .

We define a new combinatorial object, which we call a labeled hypergraph, uniquely associated to any square-free monomial ideal. We prove several upper bounds on the regularity of a square-free monomial ideal in terms of simple combinatorial properties of its labeled hypergraph. We also give specific formulas for the regularity of square-free monomial ideals with certain labeled hypergraphs. Furthermore, we prove results in the case of one-dimensional labeled hypergraphs.

Given a finite simple undirected graph G there is a simplicial complex Ind(G), called the independence complex, whose faces correspond to the independent sets of G. This is a well-studied concept because it provides a fertile ground for interactions between commutative algebra, graph theory and algebraic topology. In this paper, we consider a generalization of independence complex. Given $r\ge 1$, a subset of the vertex set is called r-independent if the connected components of the induced subgraph have cardinality at most r. The collection of all r-independent subsets of G form a simplicial complex called the r-independence complex and is denoted by Ind_r(G). It is known that when G is a chordal graph the complex Ind_r(G) has the homotopy type of a wedge of spheres. Hence, it is natural to ask which of these complexes are shellable or even vertex decomposable. We prove, using Woodroofe’s chordal hypergraph notion, that these complexes are always shellable when the underlying chordal graph is a tree. Using the notion of vertex splittable ideals we show that for caterpillar graphs the associated r-independence complex is vertex decomposable for all values of r. Further, for any $r\ge 2$ we construct chordal graphs on $2r+2$ vertices such that their r-independence complexes are not sequentially Cohen–Macaulay.

In this paper, we give the users an introduction about the framework of persistent homology methods for hypergraphs. We list the steps for standard computations of the persistent homology and discuss about the algorithms. We also give some potential mathematical tools for efficient computing.

Let $L$ be a simplicial complex. In this paper, we study random sub-hypergraphs and random sub-complexes of $L$. By considering the minimal complex that a sub-hypergraph can be embedded in and the maximal complex that can be embedded in a sub-hypergraph, we define some maps on the space of probability functions on sub-hypergraphs of $L$. We study the compositions of these maps as well as their actions on the space of probability functions.

Let $R$ be a commutative ring with identity, $Q$ be a prime ideal of $R$ and $F$ be a free $R$-module of finite rank. In this paper, we use hypergraphs to give a full characterization of prime submodules of $F$. Also we define a hypergraph $P{H}_Q(F)$ called the prime submodules hypergraph of $F$ with respect to $Q$ and use properties of Steiner systems for counting the number of $Q$-prime submodules of $F$ when the number of cosets of $Q$ in $R$ is finite.

Recent advances in data collection and storage have allowed both researchers and industry alike to collect data in real time. Much of this data comes in the form of ‘events’, or timestamped interactions, such as email and social media posts, website clickstreams, or protein–protein interactions. This type of data poses new challenges for modeling, especially if we wish to preserve all temporal features and structure. We highlight several recent approaches in modeling higher-order temporal interaction and bring them together under the umbrella of event graphs. Through examples, we demonstrate how event graphs can be used to understand the higher-order topological-temporal structure of temporal networks and capture properties of the network that are unobservable when considering either a static (or time-aggregated) model. We introduce new algorithms for temporal motif enumeration and provide a novel analysis of the communicability centrality for temporal networks. Furthermore, we show that by modeling a temporal network as an event graph our analysis extends easily to non-dyadic interactions, known as hyper-events.

Recent studies on international networks have investigated the role of global cities as catalysts of knowledge flows. In this paper, we examine global cities in transnational networks of innovators. To assess the likelihood of scientists and inventors from different cities to take part in international teams, we propose a measure based on 3-hyperedges in the collaboration network constructed from scientific publications and patents. This measure is used to identify the most competitive global cities in the international network of innovators. To this end, we construct a null model based on the hypergeometric ensembles of random graphs. We find that five US cities play a leading role in transnational networks of innovators. Among them, San Francisco stands out as the most globalized city.

Hypergraphs serve as models of complex networks that capture more general structures than binary relations. For graphs, a wide array of statistics has been devised to gauge different aspects of their structures. Hypergraphs lack behind in this respect. The Forman–Ricci curvature is a statistics for graphs based on Riemannian geometry, which stresses the relational character of vertices in a network by focusing on the edges rather than on the vertices. Despite many successful applications of this measure to graphs, Forman–Ricci curvature has not been introduced for hypergraphs. Here, we define the Forman–Ricci curvature for directed and undirected hypergraphs such that the curvature for graphs is recovered as a special case. It quantifies the trade-off between hyperedge (arc) size and the degree of participation of hyperedge (arc) vertices in other hyperedges (arcs). Here, we determine upper and lower bounds for Forman–Ricci curvature both for hypergraphs in general and for graphs in particular. The measure is then applied to two large networks: the Wikipedia vote network and the metabolic network of the bacterium Escherichia coli. In the first case, the curvature is governed by the size of the hyperedges, while in the second example, it is dominated by the hyperedge degree. We found that the number of users involved in Wikipedia elections goes hand-in-hand with the participation of experienced users. The curvature values of the metabolic network allowed detecting redundant and bottle neck reactions. It is found that ADP phosphorylation is the metabolic bottle neck reaction but that the reverse reaction is not similarly central for the metabolism. Furthermore, we show the utility of the Forman–Ricci curvature for quantification of assortativity in hypergraphs and illustrate the idea by investigating three metabolic networks.

A hypergraph is given by $H=(V,E)$, where $V$ is a set of vertices and $E$ is a set of nonempty subsets of $V$, the member of $E$ is named hyperedge. So, a hypergraph is a nature generalization of a graph. A hypergraph has a complex structure, thus some researchers try to transform a hypergraph to a graph. In this paper, we define two graphs, Clique graph and Persian graph. These relations are one to one. We can find the shortest path between two vertices in a hypergraph $H$, by using the Dijkstra algorithm in graph theory on the graphs corresponding to $H$.

The drug development pipeline for a new compound can last 10-20 years and cost over $10 billion. Drug repurposing offers a more time- and cost-effective alternative. Computational approaches based on network graph representations, comprising a mixture of disease nodes and their interactions, have recently yielded new drug repurposing hypotheses, including suitable candidates for COVID-19. However, these interactomes remain aggregate by design and often lack disease specificity. This dilution of information may affect the relevance of drug node embeddings to a particular disease, the resulting drug-disease and drug-drug similarity scores, and therefore our ability to identify new targets or drug synergies. To address this problem, we propose constructing and learning disease-specific hypergraphs in which hyperedges encode biological pathways of various lengths. We use a modified node2vec algorithm to generate pathway embeddings. We evaluate our hypergraph’s ability to find repurposing targets for an incurable but prevalent disease, Alzheimer’s disease (AD), and compare our ranked-ordered recommendations to those derived from a state-of-the-art knowledge graph, the multiscale interactome. Using our method, we successfully identified 7 promising repurposing candidates for AD that were ranked as unlikely repurposing targets by the multiscale interactome but for which the existing literature provides supporting evidence. Additionally, our drug repositioning suggestions are accompanied by explanations, eliciting plausible biological pathways. In the future, we plan on scaling our proposed method to 800+ diseases, combining single-disease hypergraphs into multi-disease hypergraphs to account for subpopulations with risk factors or encode a given patient’s comorbidities to formulate personalized repurposing recommendations.

Supplementary materials and code: https://github.com/ayujain04/psb_supplement

We present results of the recent research on sparse graphs and finite structures in the context of contemporary combinatorics, graph theory, model theory and mathematical logic, complexity of algorithms and probability theory. The topics include: complexity of subgraph- and homomorphism- problems; model checking problems for first order formulas in special classes; property testing in sparse classes of structures. All these problems can be studied under the umbrella of classes of structures which are Nowhere Dense and in the context of Nowhere Dense – Somewhere Dense dichotomy. This dichotomy presents the classification of the general classes of structures which proves to be very robust and stable as it can be defined alternatively by most combinatorial extremal invariants as well as by algorithmic and logical terms. We give examples from logic, geometry and extremal graph theory. Finally we characterize the existence of all restricted dualities in terms of limit objects defined on the homomorphism order of graphs.