On the Sizes of k-edge-maximal r-uniform Hypergraphs

Acta Mathematicae Applicatae Sinica, English Series - Let H = (V, E) be a hypergraph, where V is a set of vertices and E is a set of non-empty subsets of V called edges. If all edges of H have the...     

On 3-Steiner simplicial orderings

Let G be a connected graph and S a nonempty set of vertices of G. A Steiner tree for S is a connected subgraph of G containing S that has a minimum number of edges. The Steiner interval for S is the collection of all vertices in G that belong to some Steiner tree for S. Let k≥2 be an integer. A set X of vertices of G is k-Steiner convex if it contains the Steiner interval of every set of k vertices in X. A vertex x∈X is an extreme vertex of X if X?{x} is also k-Steiner convex. We call such vertices k-Steiner simplicial vertices. We characterize vertices that are 3-Steiner simplicial and give characterizations of two classes of graphs, namely the class of graphs for which every ordering produced by Lexicographic Breadth First Search is a 3-Steiner simplicial ordering and the class for which every ordering of every induced subgraph produced by Maximum Cardinality Search is a 3-Steiner simplicial ordering.     

Complexes of Discrete Distributional Differential Forms and Their Homology Theory

Complexes of discrete distributional differential forms are introduced into finite element exterior calculus. Thus, we generalize a notion of Braess and Schöberl, originally studied for a posteriori error estimation. We construct isomorphisms between the simplicial homology groups of the triangulation, the discrete harmonic forms of the finite element complex, and the harmonic forms of the distributional finite element complexes. As an application, we prove that the complexes of finite element exterior calculus have cohomology groups isomorphic to the de Rham cohomology, including the case of partial boundary conditions. Poincaré–Friedrichs-type inequalities will be studied in a subsequent contribution.     

有关循环图C(n;{1,k})的独立数的一些结果

令G=(V(G),E(G))是一个简单有限无向图.如果V(G)的子集S中任意两个顶点均不相邻,则S是图G的一个独立集.顶点独立集大小的最大值,称为图G的独立数,记作α(G).本文研究了循环图C(n;{1,k})的独立数问题,并给出了当k=2,3,4,5时的准确值.     

随机一致超图的关于H-因子的门槛函数

假设H和H（分别是具有h个顶点和n个顶点的r一致超图．我们称一个具有n/h个分支，且每个分支都同构于H的H的生成子图为H的一个H-因子．记α（H） = max{｜E′｜/｜V′｜-1 ｜}，其中的最大值取遍H的所有满足｜V’｜〉1的子超图（V’，E′）．δ（H）表示超图H的最小度．在本文中，我们证明了如果δ（H）〈α（H），那么P=p（n）=n-1／α（H）就是随机超图Hr（n，P）包含．H-因子的一个紧的门槛函数．也就是说，存在两个常数c和C使得对任意P=p（n）=cn-1／α（H），几乎所有的随机超图Hr（n，P）都不包含一个H-因子，对任意P=p（n）=cn-1／α（H），几乎所有的随机超图Hr（n，P）都包含一个H-因子．     

图有[a,b]因子的邻域条件

不含有图K1，R的图称为K1,r-free图，设G是一个具有顶点集V（G）的图，设n(≥3),a和b是整数，使得b≥a≥1，若b是奇数，设b≥n-1。我们证明了每个连通的K1,r-free图G在b|V(G)|为偶数，它的最小度至少是a n-1,|V(G）≥ （2(a b)-1)(a b-1)/b，以及|NG(x）∪NG（y)|≥a|V(G)|a b对V的任意两个不邻接的点x和y都成立时，G有一个[a,b]因子。     

Density Conditions for Panchromatic Colourings of Hypergraphs

Let be a hypergraph. A panchromatic t-colouring of is a t-colouring of its vertices such that each edge has at least one vertex of each colour; and is panchromatically t-choosable if, whenever each vertex is given a list of t colours, the vertices can be coloured from their lists in such a way that each edge receives at least t different colours. The Hall ratio of is . Among other results, it is proved here that if every edge has at least t vertices and whenever , then is panchromatically t-choosable, and this condition is sharp; the minimum such that every t-uniform hypergraph with is panchromatically t-choosable satisfies ; and except possibly when t = 3 or 5, a t-uniform hypergraph is panchromatically t-colourable if whenever , and this condition is sharp. This last result dualizes to a sharp sufficient condition for the chromatic index of a hypergraph to equal its maximum degree. Received November 10, 1998 RID="*" ID="*" This work was carried out while the first author was visiting Nottingham, funded by Visiting Fellowship Research Grant GR/L54585 from the Engineering and Physical Sciences Research Council. The work of this author was also partly supported by grants 96-01-01614 and 97-01-01075 of the Russian Foundation for Fundamental Research.     

Boolean formulae, hypergraphs and combinatorial topology

With a view toward studying the homotopy type of spaces of Boolean formulae, we introduce a simplicial complex, called the theta complex, associated to any hypergraph, which is the Alexander dual of the more well-known independence complex. In particular, the set of satisfiable formulae in k-conjunctive normal form with ?n variables has the homotopy type of Θ(Cube(n,n−k)), where Cube(n,n−k) is a hypergraph associated to the (n−k)-skeleton of an n-cube. We make partial progress in calculating the homotopy type of theta for these cubical hypergraphs, and we also give calculations and examples for other hypergraphs as well. Indeed studying the theta complex of hypergraphs is an interesting problem in its own right.     

Cores of Simplicial Complexes

We introduce a method to reduce the study of the topology of a simplicial complex to that of a simpler one. Applying this method to complexes arising from graphs, we give topological meaning to classical graph invariants. As a consequence, we answer some questions raised in (Ehrenborg and Hetyei in Eur. J. Comb. 27(6):906–923, 2006) on the independence complex and the dominance complex of a forest and obtain improved algorithms to compute their homotopy types.     

Remarks on Vertex-Distinguishing IE-Total Coloring of Complete Bipartite Graphs K4,n and Kn,n

Let G be a simple graph.An IE-total coloring f of G refers to a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color.Let C(u) be the set of colors of vertex u and edges incident to u under f.For an IE-total coloring f of G using k colors,if C(u)=C(v) for any two different vertices u and v of V(G),then f is called a k-vertex-distinguishing IE-total-coloring of G,or a k-VDIET coloring of G for short.The minimum number of colors required for a VDIET coloring of G is denoted by χ ie vt (G),and it is called the VDIET chromatic number of G.We will give VDIET chromatic numbers for complete bipartite graph K4,n (n≥4),K n,n (5≤ n ≤ 21) in this article.     

A simplicial homology algorithm for Lipschitz optimisation

The simplicial homology global optimisation (SHGO) algorithm is a general purpose global optimisation algorithm based on applications of simplicial integral homology and combinatorial topology. SHGO approximates the homology groups of a complex built on a hypersurface homeomorphic to a complex on the objective function. This provides both approximations of locally convex subdomains in the search space through Sperner’s lemma and a useful visual tool for characterising and efficiently solving higher dimensional black and grey box optimisation problems. This complex is built up using sampling points within the feasible search space as vertices. The algorithm is specialised in finding all the local minima of an objective function with expensive function evaluations efficiently which is especially suitable to applications such as energy landscape exploration. SHGO was initially developed as an improvement on the topographical global optimisation (TGO) method. It is proven that the SHGO algorithm will always outperform TGO on function evaluations if the objective function is Lipschitz smooth. In this paper SHGO is applied to non-convex problems with linear and box constraints with bounds placed on the variables. Numerical experiments on linearly constrained test problems show that SHGO gives competitive results compared to TGO and the recently developed Lc-DISIMPL algorithm as well as the PSwarm, LGO and DIRECT-L1 algorithms. Furthermore SHGO is compared with the TGO, basinhopping (BH) and differential evolution (DE) global optimisation algorithms over a large selection of black-box problems with bounds placed on the variables from the SciPy benchmarking test suite. A Python implementation of the SHGO and TGO algorithms published under a MIT license can be found from https://bitbucket.org/upiamcompthermo/shgo/.     

Homotopy type of circle graph complexes motivated by extreme Khovanov homology

It was proven by González-Meneses, Manchón and Silvero that the extreme Khovanov homology of a link diagram is isomorphic to the reduced (co)homology of the independence simplicial complex obtained from a bipartite circle graph constructed from the diagram. In this paper, we conjecture that this simplicial complex is always homotopy equivalent to a wedge of spheres. In particular, its homotopy type, if not contractible, would be a link invariant (up to suspension), and it would imply that the extreme Khovanov homology of any link diagram does not contain torsion. We prove the conjecture in many special cases and find it convincing to generalize it to every circle graph (intersection graph of chords in a circle). In particular, we prove it for the families of cactus, outerplanar, permutation and non-nested graphs. Conversely, we also give a method for constructing a permutation graph whose independence simplicial complex is homotopy equivalent to any given finite wedge of spheres. We also present some combinatorial results on the homotopy type of finite simplicial complexes and a theorem shedding light on previous results by Csorba, Nagel and Reiner, Jonsson and Barmak. We study the implications of our results to knot theory; more precisely, we compute the real-extreme Khovanov homology of torus links T(3, q) and obtain examples of H-thick knots whose extreme Khovanov homology groups are separated either by one or two gaps as long as desired.     

The diagonal hypergraph of a matrix (bipartite graph)

Let A be an n x n matrix of 0's and 1's (a bipartite graph). The diagonal hypergraph of A is the hypergraph whose vertices correspond to the 1's (edges) of A and whose edges correspond to the positive diagonals (1-factors) of A. The numerical invariants of this hypergraph are investigated.     

Zero divisor graphs of semigroups

The zero divisor graph of a commutative semigroup with zero is a graph whose vertices are the nonzero zero divisors of the semigroup, with two distinct vertices joined by an edge in case their product in the semigroup is zero. We continue the study of this construction and its extension to a simplicial complex.     

5-一致超图的全横贯

设H=(V,E)是以V为顶点集, E为(超)边集的超图. 如果H的每条边均含有k个顶点, 则称H是k-一致超图. 超图H的点子集T称为它的一个横贯, 如果T 与H 的每条边均相交. 超图H的全横贯是指它的一个横贯T, 并且T还满足如下性质: T中每个顶点均至少有一个邻点在T中. H 的全横贯数定义为H 的最小全横贯所含顶点的数目, 记作\tau_{t}(H). 对于整数k\geq 2, 令b_{k}=\sup_{H\in{\mathscr{H}}_{k}}\frac{\tau_{t}(H)}{n_{H}+m_{H}}, 其中n_H=|V|, m_H=|E|, {\mathscr{H}}_{k} 表示无孤立点和孤立边以及多重边的k-一致超图类. 最近, Bujt\'as和Henning等证明了如下结果: b_{2}=\frac{2}{5}, b_{3}=\frac{1}{3}, b_{4}=\frac{2}{7}; 当k\geq 5 时, 有b_{k}\leq \frac{2}{7}以及b_{6}\leq \frac{1}{4}; 当k\geq 7 时, b_{k}\leq \frac{2}{9}. 证明了对5-一致超图, b_{5}\leq \frac{4}{15}, 从而改进了当k=5 时b_k的上界.     

A semidefinite programming approach to the hypergraph minimum bisection problem

The hypergraph minimum bisection (HMB) problem is the problem of partitioning the vertices of a hypergraph into two sets of equal size so that the total weight of hyperedges crossing the sets is minimized. HMB is an NP-hard problem that arises in numerous applications – for example, in digital circuit design. Although many heuristics have been proposed for HMB, there has been no known mathematical program that is equivalent to HMB. As a means of shedding light on HMB, we study the equivalent, complement problem of HMB (called CHMB), which attempts to maximize the total weight of non-crossing hyperedges. We formulate CHMB as a quadratically constrained quadratic program, considering its semidefinite programming relaxation and providing computational results on digital circuit partitioning benchmark problems. We also provide results towards an approximation guarantee for CHMB.     

K3-free图的线图的哈密顿性

设G是一个简单图，Gi G，G1在G中的度定义为d（Gt）=∑v∈v（c）d（v），其中d（v）为v在G中的度数。本文的主要结果是：设G是n≥2阶几乎无桥的简单连通K3-free图，且G≌k1,n-1、Q1和Q2，若对G中任何同构于四个顶点路的导出子图I有d（I）≥n＋2，则G有一个D-闭迹，从而G的线图L（G）是哈密顿图。     

Special Eccentric Vertices for the Class of Chordal Graphs and Related Classes

A vertex is simplicial if the vertices of its neighborhood are pairwise adjacent. It is known that, for every vertex v of a chordal graph, there exists a simplicial vertex among the vertices at maximum distance from v. Here we prove similar properties in other classes of graphs related to that of chordal graphs. Those properties will not be in terms of simplicial vertices, but in terms of other types of vertices that are used to characterize those classes.     

The Angle Defect for Odd-Dimensional Simplicial Manifolds

In a 1967 paper, Banchoff stated that a certain type of polyhedral curvature, that applies to all finite polyhedra, was zero at all vertices of an odd-dimensional polyhedral manifold; one then obtains an elementary proof that odd-dimensional manifolds have zero Euler characteristic. In a previous paper, the author defined a different approach to curvature for arbitrary simplicial complexes, based upon a direct generalization of the angle defect. The generalized angle defect is not zero at the simplices of every odd-dimensional manifold. In this paper we use a sequence based upon the Bernoulli numbers to define a variant of the angle defect for finite simplicial complexes that still satisfies a Gauss-Bonnet-type theorem, but is also zero at any simplex of an odd-dimensional simplicial complex K (of dimension at least 3), such that χ(link(ηⁱ, K)) = 2 for all i-simplices ηⁱ of K, where i is an even integer such that 0 ≤ i ≤ n – 1. As a corollary, an elementary proof is given that any such simplicial complex has Euler characteristic zero.     

A combinatorial Lefschetz fixed point formula

We define a class of simplicial maps — those which are “expanding directions preserving” — from a barycentric subdivision to the original simplicial complex. These maps naturally induce a self map on the links of their fixed points. The local index at a fixed point of such a map turns out to be the Lefschetz number of the induced map on the link of the fixed point in relative homology. We also show that a weakly hyperbolic [4] simplicial map sdⁿK →K is expanding directions preserving.