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.     

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.     

Performance-Driven Layer Assignment by Integer Linear Programming and Path-Constrained Hypergraph Partitioning

Performance-driven physical layout design is becoming increasingly important for both high speed integrated circuits and printed circuit boards. This paper studies the problem of assigning wire segments into two layers so as to minimize the number of vias, while taking into account performance constraints such as layer preference and circuit timing. We show that using the Elmore delay model, three timing problems in synchronous digital circuits—the long path problem, the short path problem and the time skew problem—can be formulated as a set of linear inequalities. We use the model of signed hypergraph to represent two-layer routings and formulate the performance-driven optimum layer assignment problem as the path-constrained maximum balance problem in a signed hypergraph. Two solution methods are developed and implemented. First, an integer linear programming formulation is derived for finding exact solutions. Second, a local-search heuristic for hypergraph partitioning is extended to cope with path-inequality constraints. Experimental results on a set of layer-assignment benchmarks demonstrated that the path-constrained local-search heuristic achieves optimum or near-optimum solutions with several orders of magnitude faster than the integer linear programming approach.     

Optimization on sparse random hypergraphs and spin glasses

We establish that in the large degree limit, the value of certain optimization problems on sparse random hypergraphs is determined by an appropriate Gaussian optimization problem. This approach was initiated in Dembo et al. (2016) for extremal cuts of graphs. The usefulness of this technique is further illustrated by deriving the optimal value for Max q‐cut on graphs, Max XORSAT on Erdős–Rényi hypergraphs, and the min‐bisection the min‐bisection for the Stochastic Block Model.     

Linear optimization over permutation groups

For a permutation group given by a set of generators, the problem of finding “special” group members is NP-hard in many cases, e.g., this is true for the problem of finding a permutation with a minimum number of fixed points or a permutation with a minimal Hamming distance from a given permutation. Many of these problems can be modeled as linear optimization problems over permutation groups. We develop a polyhedral approach to this general problem and derive an exact and practically fast algorithm based on the branch & cut-technique.     

Maximum Cliques of Hypergraphs and Polynomial Optimization

A remarkable connection between the clique number and the Lagrangian of a graph was established by Motzkin and Straus. Later, Rota Buló and Pelillo extended the theorem of Motzkin-Straus to r-uniform hypergraphs by studying the relation of local (global) minimizers of a homogeneous polynomial function of degree r and the maximal (maximum) cliques of an r-uniform hypergraph. In this paper, we study polynomial optimization problems for non-uniform hypergraphs with four different types of edges and apply it to get an upper bound of Turán densities of complete non-uniform hypergraphs.     

A NEW FILLED FUNCTION METHOD FOR INTEGER PROGRAMMING

The Filled Function Method is a class of effective algorithms for continuous globaloptimization.In this paper,a new filled function method is introduced and used to solveinteger programming.Firstly,some basic definitions of discrete optimization are given.Then an algorithm and the implementation of this algorithm on several test problems areshowed.The computational results show the algorithm is effective.     

New short proofs to some stability theorems

We present new short proofs to both the exact and the stability result of two extremal problems. The first result is about the extension of Turán’s theorem to hypergraphs, and the second result is about cancellative hypergraphs. Our proofs are concise and straightforward, but give a sharper version of stability theorems to both problems.     

超图研究中的两个问题

使用超图中已取得的结果研究在超图上数据库的整体一致性并初步探讨随机超图.     

超图的最优标号与特征值

研究超图的标号性质,首先利用拉普拉斯张量的第二小和最大特征值给出4一致超图的带宽和与割宽的上下界;其次构造与超图对应的简单图,通过其拉普拉斯矩阵的特征值给出超图带宽的下界.     

Laplacians on quantum hypergraphs

We introduce quantum hypergraphs, in analogy with the theory of quantum graphs developed over the last 15 years by many authors. We emphasize some problems that arise when one tries to define a Laplacian on a hypergraph. (© 2014 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Paths and cycles of hypergraphs

Hypergraphs are the most general structures in discrete mathematics. Acyclic hypergraphs have been proved very useful in relational databases. New systems of axioms for paths, connectivity and cycles of hypergraphs are constructed. The systems suit the structure properties of relational databases. The concepts of pseudo cycles and essential cycles of hypergraphs are introduced. They are relative to each other. Whether a family of cycles of a hypergraph is dependent or independent is defined. An enumeration formula for the maximum number of independent essential cycles of a hypergraph is given.     

Homology Cycles and Dependent Cycles of Hypergraphs

In this paper, some new concepts for hypergraphs are introduced. Based on the previous results, we do further research on cycle structures of hypergraphs and construct a more strictly complete cycle structure system of hypergraphs.     

Partitioning Signed Two-Mode Networks

Structural balance theory forms the foundation for a generalized blockmodel method useful for delineating the structure of signed social one-mode networks for social actors (for example, people or nations). Heider's unit formation relation was dropped. We re-examine structural balance by formulating Heider's unit formation relations as signed two-mode data. Just as generalized blockmodeling has been extended to analyze two-mode unsigned data, we extend it to analyze signed two-mode network data and provide a formalization of the extension. The blockmodel structure for signed two-mode networks has positive and negative blocks, defined in terms of different partitions of rows and columns. These signed blocks can be located anywhere in the block model. We provide a motivating example and then use the new blockmodel type to delineate the voting patterns of the Supreme Court justices for all of their nonunanimous decisions for the 2006–07 term. Interpretations are presented together with a statement of further problems meriting attention for partitioning signed two-mode data.     

A quantum-behaved simulated annealing algorithm-based moth-flame optimization method

This study develops an improved moth-flame optimization algorithm, which is a recently proposed optimizer based on moth behavior in nature. It has achieved favorable results in medical science, educational evaluation, and other fields. However, the convergence rate of the original moth-flame optimization algorithm is too fast in the running process, and it is prone to fall into local optimum, which leads to the failure to produce the high-quality optimal result. Accordingly, this paper proposes a reinforced technique for the moth-flame optimization algorithm. Firstly, the simulated annealing strategy is introduced into the moth-flame optimization algorithm to boost the advantage of the algorithm in the local exploitation process. Then, the idea of the quantum rotation gate is integrated to enhance the global exploration ability of the algorithm and ameliorate the diversity of the moth. These two steps maintain the relationship between exploitation and exploration as well as strengthen the performance of the algorithm in both phases. After that, the method is compared with ten well-regarded and ten alternative algorithms on benchmark functions to verify the effectiveness of the approach. Also, the Wilcoxon signed rank and Friedman assessment were performed to verify the significance of the proposed method against other counterparts. The simulation results reveal that the two introduced strategies significantly improve the exploration and exploitation capacity of moth-flame optimization algorithm. Finally, the algorithm is utilized to feature selection and two engineering problems, including pressure vessel design and multiple disk clutch brake problems. In these practical applications, the novel algorithm also achieves particularly notable results, which also illustrates that the algorithm is qualified is an effective auxiliary appliance in solving complex optimization problems.     

Critical hypergraphs and intersecting set-pair systems

A method is given for solving extremal problems of the following type: determine the maximal number of vertices in a class of hypergraphs. Results are applied for τ-critical and ν-critical hypergraphs.     

On the Number of Independent Sets in Simple Hypergraphs

Extremal problems on the number of j-independent sets in uniform simple hypergraphs are studied. Nearly optimal results on the maximum number of independent sets for the class of simple regular hypergraphs and on the minimum number of independent sets for the class of simple hypergraphs with given average degree of vertices are obtained.     

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.     

A Sequential Convexification Method (SCM) for Continuous Global Optimization

A new method for continuous global minimization problems, acronymed SCM, is introduced. This method gives a simple transformation to convert the objective function to an auxiliary function with gradually fewer local minimizers. All Local minimizers except a prefixed one of the auxiliary function are in the region where the function value of the objective function is lower than its current minimal value. Based on this method, an algorithm is designed which uses a local optimization method to minimize the auxiliary function to find a local minimizer at which the value of the objective function is lower than its current minimal value. The algorithm converges asymptotically with probability one to a global minimizer of the objective function. Numerical experiments on a set of standard test problems with several problems' dimensions up to 50 show that the algorithm is very efficient compared with other global optimization methods.     

关于图的团符号控制数

引入了图的团符号控制的概念,给出了n阶图G的团符号控制数γks(G)的若干下限,确定了几类特殊图的团符号控制数,并提出了若干未解决的问题和猜想.