Oriented hypergraphs: Balanceability

An oriented hypergraph is an oriented incidence structure that extends the concepts of signed graphs, balanced hypergraphs, and balanced matrices. We introduce hypergraphic structures and techniques that generalize the circuit classification of the signed graphic frame matroid to any oriented hypergraphic incidence matrix via its locally-signed-graphic substructure. To achieve this, Camion's algorithm is applied to oriented hypergraphs to provide a generalization of reorientation sets and frustration that is only well-defined on balanceable oriented hypergraphs. A simple partial characterization of unbalanceable circuits extends the applications to representable matroids demonstrating that the difference between the Fano and non-Fano matroids is one of balance.     

An algorithmic hypergraph regularity lemma

Szemerédi 's Regularity Lemma is a powerful tool in graph theory. It asserts that all large graphs admit bounded partitions of their edge sets, most classes of which consist of uniformly distributed edges. The original proof of this result was nonconstructive, and a constructive proof was later given by Alon, Duke, Lefmann, Rödl, and Yuster. Szemerédi's Regularity Lemma was extended to hypergraphs by various authors. Frankl and Rödl gave one such extension in the case of 3‐uniform hypergraphs, which was later extended to k‐uniform hypergraphs by Rödl and Skokan. W.T. Gowers gave another such extension, using a different concept of regularity than that of Frankl, Rödl, and Skokan. Here, we give a constructive proof of a regularity lemma for hypergraphs.     

On a question of Sós about 3‐uniform friendship hypergraphs

The well‐known Friendship Theorem states that if G is a graph in which every pair of vertices has exactly one common neighbor, then G has a single vertex joined to all others (a “universal friend”). V. Sós defined an analogous friendship property for 3‐uniform hypergraphs, and gave a construction satisfying the friendship property that has a universal friend. We present new 3‐uniform hypergraphs on 8, 16, and 32 vertices that satisfy the friendship property without containing a universal friend. We also prove that if n ≤ 10 and n ≠ 8, then there are no friendship hypergraphs on n vertices without a universal friend. These results were obtained by computer search using integer programming. © 2008 Wiley Periodicals, Inc. J Combin Designs 16: 253–261, 2008     

On the Existence of Friendship Hypergraphs

A 3‐uniform friendship hypergraph is a 3‐uniform hypergraph in which, for all triples of vertices x, y, z there exists a unique vertex w, such that , and are edges in the hypergraph. Sós showed that such 3‐uniform friendship hypergraphs on n vertices exist with a so‐called universal friend if and only if a Steiner triple system, exists. Hartke and Vandenbussche used integer programming to search for 3‐uniform friendship hypergraphs without a universal friend and found one on 8, three nonisomorphic on 16 and one on 32 vertices. So far, these five hypergraphs are the only known 3‐uniform friendship hypergraphs. In this paper we construct an infinite family of 3‐uniform friendship hypergraphs on 2^k vertices and edges. We also construct 3‐uniform friendship hypergraphs on 20 and 28 vertices using a computer. Furthermore, we define r‐uniform friendship hypergraphs and state that the existence of those with a universal friend is dependent on the existence of a Steiner system, . As a result hereof, we know infinitely many 4‐uniform friendship hypergraphs with a universal friend. Finally we show how to construct a 4‐uniform friendship hypergraph on 9 vertices and with no universal friend.     

The poset of hypergraph quasirandomness

Chung and Graham began the systematic study of k‐uniform hypergraph quasirandom properties soon after the foundational results of Thomason and Chung‐Graham‐Wilson on quasirandom graphs. One feature that became apparent in the early work on k‐uniform hypergraph quasirandomness is that properties that are equivalent for graphs are not equivalent for hypergraphs, and thus hypergraphs enjoy a variety of inequivalent quasirandom properties. In the past two decades, there has been an intensive study of these disparate notions of quasirandomness for hypergraphs, and an open problem that has emerged is to determine the relationship between them. Our main result is to determine the poset of implications between these quasirandom properties. This answers a recent question of Chung and continues a project begun by Chung and Graham in their first paper on hypergraph quasirandomness in the early 1990's. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46,762–800, 2015     

Counting acyclic hypergraphs

Acyclic hypergraphs are analogues of forests in graphs. They are very useful in the design of databases. The number of distinct acyclic uniform hypergraphs withn labeled vertices is studied. With the aid of the principle of inclusion-exclusion, two formulas are presented. One is the explicitformula for strict (d)-connected acyclic hypergraphs, the other is the recurrence formula for linear acyclic hypergraphs.     

The maximum spectral radius of uniform hypergraphs with given number of pendant edges

In this paper, we introduce the operations of grafting an edge and subdividing an edge on hypergraphs, and consider how spectral radius of a hypergraph behaves by grafting an edge or subdividing an edge. As an application, we determine the unique hypergraphs with the maximum spectral radius among all the uniform supertrees and all the connected uniform unicyclic hypergraphs with given number of pendant edges, respectively. Moreover, we determine the unique uniform supertree which attains the maximum spectral radius among all the uniform supertrees with given number of pendant vertices.     

The analytic connectivity in uniform hypergraphs: Properties and computation

The analytic connectivity (AC), defined via solving a series of constrained polynomial optimization problems, serves as a measure of connectivity in hypergraphs. How to compute such a quantity efficiently is important in practice and of theoretical challenge as well due to the non-convex and combinatorial features in its definition. In this article, we first perform a careful analysis of several widely used structured hypergraphs in terms of their properties and heuristic upper bounds of ACs. We then present an affine-scaling method to compute some upper bounds of ACs for uniform hypergraphs. To testify the tightness of the obtained upper bounds, two possible approaches via the Pólya theorem and semidefinite programming respectively are also proposed to verify the lower bounds generated by the obtained upper bounds minus a small gap. Numerical experiments on synthetic datasets are reported to demonstrate the efficiency of our proposed method. Further, we apply our method in hypergraphs constructed from social networks and text analysis to detect the network connectivity and rank the keywords, respectively.     

Hall’s and Kőnig’s theorem in graphs and hypergraphs

We investigate the relation between Hall’s theorem and K?nig’s theorem in graphs and hypergraphs. In particular, we characterize the graphs satisfying a deficiency version of Hall’s theorem, thereby showing that this class strictly contains all K?nig–Egerváry graphs. Furthermore, we give a generalization of Hall’s theorem to normal hypergraphs.     

A characterization of signed hypergraphs and its applications to VLSI via minimization and logic synthesis

A recently introduced graph-theoretic notion of signed hypergraph is studied. In particular, a structural characterization of balanced signed hypergraphs is given, and two optimization problems related to the balance property — the maximum balance and the minimum covering problems — are introduced and characterized. It is shown that both problems are NP-complete in general. Applications of the theory of signed hypergraphs to two VLSI optimization problems, namely via minimization and constrained logic encoding, are described.     

超图中的着色问题

本文是近三十年来有关超图中涉及的着色问题的综述。它包含了有关超图着色中的基本结果,临界可着色性,２－可着色性,非２－可着色性以及在超图中与顶点着色、边着色和其它着色相关的极值问题。     

A (1 + ϵ)‐approximation algorithm for partitioning hypergraphs using a new algorithmic version of the Lovász Local Lemma*

In his seminal result, Beck gave the first algorithmic version of the Lovász Local Lemma by giving polynomial time algorithms for 2‐coloring and partitioning uniform hypergraphs. His work was later generalized by Alon, and Molloy and Reed. Recently, Czumaj and Scheideler gave an efficient algorithm for 2‐coloring nonuniform hypergraphs. But the partitioning algorithm obtained based on their second paper only applies to a more limited range of hypergraphs, so much so that their work doesn't imply the result of Beck for the uniform case. Here we give an algorithmic version of the general form of the Local Lemma which captures (almost) all applications of the results of Beck and Czumaj and Scheideler, with an overall simpler proof. In particular, if H is a nonuniform hypergraph in which every edge e_i intersects at most |e_i|2^αk other edges of size at most k, for some small constant α, then we can find a partitioning of H in expected linear time. This result implies the result of Beck for uniform hypergraphs along with a speedup in his running time. © 2004 Wiley Periodicals, Inc. Random Struct. Alg. 2004     

Constructing regular self‐complementary uniform hypergraphs

In this article, we examine the possible orders of t‐subset‐regular self‐complementary k‐uniform hypergraphs, which form examples of large sets of two isomorphic t‐designs. We reformulate Khosrovshahi and Tayfeh–Rezaie's necessary conditions on the order of these structures in terms of the binary representation of the rank k, and these conditions simplify to a more transparent relation between the order n and rank k in the case where k is a sum of consecutive powers of 2. Moreover, we present new constructions for 1‐subset‐regular self‐complementary uniform hypergraphs, and prove that these necessary conditions are sufficient for all k, in the case where t = 1. © 2011 Wiley Periodicals, Inc. J Combin Designs 19: 439‐454, 2011     

完全3-一致超图的圈分解

The problem of decomposing a complete 3-uniform hypergraph into Hamilton cycles was introduced by Bailey and Stevens using a generalization of Hamiltonian chain to uniform hypergraphs by Katona and Kierstead. Decomposing the complete 3-uniform hypergraphs K_n~(3) into k-cycles(3 ≤ k n) was then considered by Meszka and Rosa. This study investigates this problem using a difference pattern of combinatorics and shows that K_(n·5m)~(3) can be decomposed into 5-cycles for n ∈{5, 7, 10, 11, 16, 17, 20, 22, 26} using computer programming.     

最大边连通和super-边连通超图的充分条件

设H是连通超图。若超图H的边连通度等于其最小度,则称H是最大边连通的。若超图H的每个最小边割总是由关联于某个最小度顶点的边集所构成,则称H是super-边连通的。首先给出一致线性超图是最大边连通超图的度序列条件。其次,给出一致线性超图是super-边连通超图的度条件。这些结果分别推广了Dankelmann和Volkmann（1997）以及Hellwig和Volkmann（2005）在图上的相关结论。     

秩为r的本原超图的指数集(英文)

本文研究了超图的本原性质.运用图论方法,得到了具有秩r(≥3)的所有n阶本原有向超图的指数集,并刻划了其极超图.     

A hypergraph blow‐up lemma

We obtain a hypergraph generalisation of the graph blow‐up lemma proved by Komlós, Sarközy and Szemerédi, showing that hypergraphs with sufficient regularity and no atypical vertices behave as if they were complete for the purpose of embedding bounded degree hypergraphs. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 39, 275–376, 2011     

偶一致超图划分问题的若干结果

划分问题因其在多个领域的重要应用一直是图论的研究热点.利用张量的特征值研究超图的划分与奇划分,并结合边割的界给出最大奇割、平均最小割、等周数等超图拓扑指标的界.当k取2时,这些结果与对应的图谱理论中的经典结论一致,因此可视为这些结论在超图的推广.     

Some interpretations for algebraic invariants of edge ideals of hypergraphs via combinatorial invariants

Abstract

The present work is concerned with characterizing some algebraic invariants of edge ideals of hypergraphs. To this aim, first, we introduce some kinds of combinatorial invariants similar to matching numbers for hypergraphs. Then we compare them to each other and to previously existing ones. These invariants are used for characterizing or bounding some algebraic invariants of edge ideals of hypergraphs such as graded Betti numbers, projective dimension and Castelnouvo–Mumford regularity.

Communicated by Jason P. Bell