On the Heterochromatic Number of Hypergraphs Associated to Geometric Graphs and to Matroids

The heterochromatic number h _c (H) of a non-empty hypergraph H is the smallest integer k such that for every colouring of the vertices of H with exactly k colours, there is a hyperedge of H all of whose vertices have different colours. We denote by ν(H) the number of vertices of H and by τ(H) the size of the smallest set containing at least two vertices of each hyperedge of H. For a complete geometric graph G with n ≥ 3 vertices let H = H(G) be the hypergraph whose vertices are the edges of G and whose hyperedges are the edge sets of plane spanning trees of G. We prove that if G has at most one interior vertex, then h _c (H) = ν(H) ? τ(H) + 2. We also show that h _c (H) = ν(H) ? τ(H) + 2 whenever H is a hypergraph with vertex set and hyperedge set given by the ground set and the bases of a matroid, respectively.     

Efficiently Recognizing the P 4-Structure of Trees and of Bipartite Graphs Without Short Cycles

A 4-uniform hypergraph represents the P ₄-structure of a graph G if its hyperedges are the vertex sets of the P ₄'s in G. By using the weighted 2-section graph of the hypergraph we propose a simple efficient algorithm to decide whether a given 4-uniform hypergraph represents the P ₄-structure of a bipartite graph without 4-cycle and 6-cycle. For trees, our algorithm is different from that given by G. Ding and has a better running time namely O(n ²) where n is the number of vertices. Revised: February 18, 1998     

The existence of regular self-complementary 3-uniform hypergraphs

A k-uniform hypergraph with vertex set V and edge set E is called t-subset-regular if every t-element subset of V lies in the same number of elements of E. In this paper we show that a 1-subset-regular self-complementary 3-uniform hypergraph with n vertices exists if and only if n≥5 and n is congruent to 1 or 2 modulo 4.     

Recognizing Intersection Graphs of Linear Uniform Hypergraphs

A hypergraph is linear if any two distinct hyperedges have at most one common vertex. The existence of a polynomial algorithm is shown for deciding whether a graph of minimum degree δ ≥ 19 is the intersection graph of a linear 3-uniform hypergraph. This result improves a corollary of the finite forbidden subgraph characterization proved for δ ≥ 69 by Naik et al. in [8]. Essentially the same methods yield a polynomial recognition algorithm for the intersection graph of a linear r-uniform hypergraph, r ≥ 3, provided the minimum edge-degree of the graphs is at least 2r ² ? 3r + 1. This improves on the cubic bound that follows from the corresponding finite characterization result in [8].     

图与超图中的彩色匹配综述

超图H=(V,E)是一个二元组(V,E),其中超边集E中的元素是点集V的非空子集.因此图是一种特殊的超图,超图也可以看作是一般图的推广.特别地,如果超边集E中的元素均是点集V的k元子集,则称该超图为k-一致的.通常情况下,为叙述简便,我们也会将超边简称为边.图(超图)中的匹配是指图(超图)中互不相交的边的集合.对于图(超图)中的彩色匹配,有两种定义方式:一为染色图(超图)中互不相交且颜色不同的边的集合;二为顶点集均为[n]的多个染色图(超图)所构成的集族中互不相交且颜色均不同的边的集合,且每条边均来自集族中不同的图(超图).现主要介绍了图与超图中关于彩色匹配的相关结果.     

Not-all-equal 3-SAT and 2-colorings of 4-regular 4-uniform hypergraphs

In this paper, we continue our study of 2-colorings in hypergraphs (see, Henning and Yeo, 2013). A hypergraph is 2-colorable if there is a 2-coloring of the vertices with no monochromatic hyperedge. It is known (see Thomassen, 1992) that every 4-uniform 4-regular hypergraph is 2-colorable. Our main result in this paper is a strengthening of this result. For this purpose, we define a vertex in a hypergraph $H$ to be a free vertex in $H$ if we can 2-color $V\left(H\right)?\left\{v\right\}$ such that every hyperedge in $H$ contains vertices of both colors (where $v$ has no color). We prove that every 4-uniform 4-regular hypergraph has a free vertex. This proves a conjecture in Henning and Yeo (2015). Our proofs use a new result on not-all-equal 3-SAT which is also proved in this paper and is of interest in its own right.     

Acyclic Hypergraph Projections

Hypergraphs can be partitioned into two classes: tree (acyclic) hypergraphs and cyclic hypergraphs. This paper analyzes a new class of cyclic hypergraphs called Xrings. HypergraphHis an Xring if the hyperedges ofHcan be circularly ordered so that for every vertex, all hyperedges containing the vertex are consecutive; in addition, the vertices of no hyperedge may be a subset of the vertices of another hyperedge, and no vertex may appear in exactly one hyperedge. LetH₁andH₂be two hypergraphs. A tree projection ofH₁with respect toH₂is an acyclic hypergraphH₃such that the vertices of each hyperedge inH₁appear among the vertices of some hyperedge ofH₃and the vertices of each hyperedge inH₃appear among the vertices of some hyperedge ofH₂. A polynomial time algorithm is presented for deciding, given XringH₁and arbitrary hypergraphH₂, whether there exists a tree projection ofH₂with respect toH₁. It is shown that hypergraphHis an Xring iff a modified adjacency graph ofHis a circular-arc graph. A linear time Xring recognition algorithm, for GYO reduced hypergraphs as inputs, is presented.     

3-一致超图的反馈数研究

超图H=(V,E)顶点集为V,边集为E.S■V是H的顶点子集,如果H/S不含有圈,则称S是H的点反馈数,记τc(H)是H的最小点反馈数.本文证明了:(i)如果H是线性3-一致超图,边数为m,则τc(H)≤m/3;(ii)如果H是3-一致超图,边数为m,则τc(H)≤m/2并且等式成立当且仅当H任何一个连通分支是孤立顶点或者长度为2的圈.A■V是H的边子集,如果H\A不含有圈,则称A是H的边反馈数,记τc′(H)是H的最小边反馈数.本文证明了如果H是含有p个连通分支的3-一致超图,则τc’(H)≤2m-n+p.     

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.     

Sur le nombre transversal des hypergraphes uniformes

The transversal number of a given hypergraph is the cardinality of the smallest set of vertices meeting all the edges. What is the maximal possible value of the transversal number of a r-uniform hypergraph on n vertices with maximal degree p? The problem is solved here for p = 2, by using Berge's theorem on matchings.     

Almost all triple systems with independent neighborhoods are semi-bipartite

The neighborhood of a pair of vertices u, v in a triple system is the set of vertices w such that uvw is an edge. A triple system H is semi-bipartite if its vertex set contains a vertex subset X such that every edge of H intersects X in exactly two points. It is easy to see that if H is semi-bipartite, then the neighborhood of every pair of vertices in H is an independent set. We show a partial converse of this statement by proving that almost all triple systems with vertex sets [n] and independent neighborhoods are semi-bipartite. Our result can be viewed as an extension of the Erd?s-Kleitman-Rothschild theorem to triple systems.The proof uses the Frankl-Rödl hypergraph regularity lemma, and stability theorems. Similar results have recently been proved for hypergraphs with various other local constraints.     

Clustering by hypergraphs and dimensionality of cluster systems

In the present paper we discuss a new clustering procedure in the case where instead of a single metric we have a family of metrics. In this case we can obtain a partially ordered graph of clusters which is not necessarily a tree. We discuss a structure of a hypergraph above this graph. We propose two definitions of dimension for hyperedges of this hypergraph and show that for the multidimensional p-adic case both dimensions are reduced to the number of p-adic parameters.We discuss the application of the hypergraph clustering procedure to the construction of phylogenetic graphs in biology. In this case the dimension of a hyperedge will describe the number of sources of genetic diversity.     

On packing and coloring hyperedges in a cycle

Given a hypergraph and k different colors, we study the problem of packing and coloring a subset of the hyperedges of the hypergraph as paths in a cycle such that the total profit of the hyperedges selected is maximized, where each physical link e_j on the cycle is used at most c_j times, each hyperedge h_i has its profit p_i and any two paths, each spanning all nodes of its corresponding hyperedge, must be assigned different colors if they share a common physical link. This new problem arises in optical communication networks, and it is called the Maximizing Profits when Packing and Coloring Hyperedges in a Cycle problem (MPPCHC).In this paper, we prove that the MPPCHC problem is NP-hard and then present an algorithm with approximation ratio 2 for this problem. For the special case where each hyperedge has the same profit 1 and each link e_j has same capacity k, we propose an algorithm with approximation ratio .     

Hypergraphs and abstract polygons

The notion of a graph has recently been generalized to include structures called hypergraphs which have two or more vertices per edge. A hypergraph is called 2-settled if each pair of distinct vertices is contained in at most one edge. A connected 2-settled hypergraph which has at least two edges through each vertex might be called an abstract polygon. Lemma: Every abstract polygon contains a cycle. Shephard and Coxeter have examined certain abstract polygons called regular complex polygons, each of which is denoted by a symbol p {q} r where there are p vertices on each edge and r edges through each vertex. Theorem: The girth of the non-starry regular complex polygon p {q} r is q. Thus, the number q is finally given a simple combinatoric interpretation.     

3一致完全超图的彩色哈密顿圈

假设c是一个小于1/1152的常数,证明：对于每个充分大的偶数n,如果一个具有n个顶点的3一致完全超图的边着色满足每种颜色出现的次数不超过[cn],那么必含有一个每条边颜色都不一样的彩色哈密顿圈。     

Weakly union-free twofold triple systems

In this paper, we settle a problem of Frankl and Füredi, which is a special case of a problem of Erdös, determining the maximum number of hyperedges in a 3-uniform hypergraph in which no two pairs of distinct hyperedges have the same union. The extremal case corresponds to the existence of weakly union-free twofold triple systems, which is settled here with six definite and four possible exceptions. An application to group testing is also given.     

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的上界.     

Supersaturated graphs and hypergraphs

We shall consider graphs (hypergraphs) without loops and multiple edges. Let ? be a family of so called prohibited graphs and ex (n, ?) denote the maximum number of edges (hyperedges) a graph (hypergraph) onn vertices can have without containing subgraphs from ?. A graph (hyper-graph) will be called supersaturated if it has more edges than ex (n, ?). IfG hasn vertices and ex (n, ?)+k edges (hyperedges), then it always contains prohibited subgraphs. The basic question investigated here is: At least how many copies ofL ε ? must occur in a graphG ⁿ onn vertices with ex (n, ?)+k edges (hyperedges)?     

4-Books of three pages

Let H be a 4-uniform hypergraph on an n-element vertex set V containing no 4-book of 3 pages, i.e., a hypergraph of 4 quadruples with vertices {1,2,…,7} and edges {1234,1235,1236,4567}. Then for n>n₀

     

Random Hypergraph Processes with Degree Restrictions

A d-process for s-uniform hypergraphs starts with an empty hypergraph on n vertices, and adds one s-tuple at each time step, chosen uniformly at random from those s-tuples which are not already present as a hyperedge and which consist entirely of vertices with degree less than d. We prove that for d2 and s3, with probability which tends to 1 as n tends to infinity, the final hypergraph is saturated; that is, it has n–i vertices of degree d and i vertices of degree d–1, where This generalises the result for s=2 obtained by the second and third authors. In addition, when s3, we prove asymptotic equivalence of this process and the more relaxed process, in which the chosen s-tuple may already be a hyperedge (and which therefore may form multiple hyperedges).Some of this work was performed while the first and second authors were visiting the Isaac Newton Institute for Mathematical Sciences, Cambridge, UKResearch supported by an Australian Research Council Postdoctoral Fellowship.Research supported by the KBN grant 2 P03A 15 23Research supported by the Australian Research Council.Final version received: October 22, 2003