Triple Systems are Eulerian

An Euler tour of a hypergraph (also called a rank‐2 universal cycle or 1‐overlap cycle in the context of designs) is a closed walk that traverses every edge exactly once. In this paper, using a graph‐theoretic approach, we prove that every triple system with at least two triples is eulerian, that is, it admits an Euler tour. Horan and Hurlbert have previously shown that for every admissible order >3, there exists a Steiner triple system with an Euler tour, while Dewar and Stevens have proved that every cyclic Steiner triple system of order >3 and every cyclic twofold triple system admits an Euler tour.     

Covering and Euler cycles on non-oriented graphs

A covering cycle is a closed path that traverses each edge of a graph at least once. Two cycles are equivalent if one is a cyclic permutation of the other. We compute the number of equivalence classes of non-periodic covering cycles of given length in a non-oriented connected graph. A special case is the number of Euler cycles (covering cycles that cover each edge of the graph exactly once) in the non-oriented graph. We obtain an identity relating the numbers of covering cycles of any length in a graph to a product of determinants.     

Hypergraph Extension Of The Alon-Tarsi List Coloring Theorem

A circulation in a digraph is a spanning subgraph with indegree equal to outdegree at each vertex. Alon and Tarsi proved that a graph is d-choosable when it has an orientation that has no vertex of outdegree at least d and has the property that the numbers of circulations with even-sized and odd-sized edge sets differ. We generalize this to k-uniform hypergraphs for prime k. We use a hypergraph polynomial and a notion of hypergraph orientation defined by choosing a source vertex from each edge.* Project sponsored by the National Security Agency under Grant Number MDA904-03-1-0037. The United States Government is authorized to reproduce and distribute reprints notwithstanding any copyright notation herein.     

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.     

P4‐decompositions of regular graphs

In this article, we show that every simple r‐regular graph G admits a balanced P₄‐decomposition if r ≡ 0(mod 3) and G has no cut‐edge when r is odd. We also show that a connected 4‐regular graph G admits a P₄‐decomposition if and only if |E(G)| ≡ 0(mod 3) by characterizing graphs of maximum degree 4 that admit a triangle‐free Eulerian tour. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 135–143, 1999     

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.     

A construction of a perfect set of Euler tours of K2k + I

In this article we define a perfect set of Euler tours of K_2k + I, I a 1-factor of K_2k, to be a set of Euler tours of K_2k + I that partition the 2-paths of K_2k, with the added condition that if ab ∈ I, then each Euler tour contains either the digon a b a or b a b. We prove for all k > 1 that K_2k + I has a perfect set of Euler tours, and, as a corollary, that L(K_2k) has a Hamilton decomposition. © 1998 John Wiley & Sons, Inc. J Combin Designs 6: 183–211, 1998     

Critical hypergraphs for the weak chromatic number

Instead of removing a vertex or an edge from a hypergraph H, one may add to some edges of H new vertices (not necessarily belonging to V_H). The weak chromatic number of H tends to drop by this operation. This suggests the definition of an order relation ≥ on the set $\text{S}$ of all Sperner hypergraphs on a universal set V of vertices. The corresponding criticality study leads to unifying and interesting results: reconstruction of critical hypergraphs and two general characterizations of k-chromatic critical hypergraphs (k ≥ 3), from which a special characterization of 3-chromatic critical hypergraphs can be derived.     

On intersection multigraphs of hypergraphs

The sum of the cardinalities of all the edges of a hypergraph is computed in two different ways. This result is used to treat the generalisation of the notion of cyclomatic number for hypergraphs. Among others the following result is obtained: The cyclomatic number of the hypergraph H vanishes if and only if some maximum forest of the weighted intersection graph of H has the property that for every vertex of H the subgraph of the forest induced by those edges containing that vertex is connected.     

Generalisations of Hypomorphisms and Reconstruction of Hypergraphs

We define certain generalisations of hypergraph hypomorphisms, which we call k-morphisms, \((k,n-k)\)-hypomorphisms, partial \((k,n-k)\)-hypomorphisms. They are special bijections between collections of k-subsets of vertex sets of hypergraphs. We show that these mappings lead to alternative representations of the automorphism groups of r-uniform hypergraphs and vertex stabilisers of graphs. We also use them to show that almost every r-uniform hypergraph is reconstructible and \((k,n-k)\)-reconstructible. As a consequence we also obtain the result that almost every r-uniform hypergraph is asymmetric.     

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

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

Infinite Eulerian tessellations

An Eulerian path in a graph G is a path π such that (1) π traverses each edge of G exactly once in each direction, and (2) π does not traverse any edge once in one direction and then immediately after in the other direction. A tessellation T of the plane is Eulerian if its l-skeleton G admits an Eulerian path. It is shown that the three regular tessellations of the Euclidean plane are Eulerian. More generally, if T is a tessellation of the plane such that each face has 2t least p sides and each vertex has degree (number of incident edges) at least q, where $\text{1/p+1/q≤}\text{1}\text{2}$, then, except possibly for the case p = 3 and q = 6, T is Eulerian. Let $\text{T}{}^1$ be the truncation of T. If every vertex of T has degree 3, then $\text{T}{}^1$ is not Eulerian. If every vertex has degree 4, or degree at least 6, then T is Eulerian.     

两类广义Petersen 图的Euler亏格

广义 Petersen 图 P(n, m) 是这样的一个图:它的顶点集是{u_i, v_i | i=0,1, ^… , n-1}, 边集是 {u_iu_i+1, v_iv_i+m, u_iv_i | i=0,1, ^…, n-1}, 这里 m, n 是正整数、加法是在模n 下且 m<|n/2| . 这篇文章证明了P(2m+1, m)(m≥ 2) 的 Euler 亏格是1, 并且 P(2m+2, m)(m≥ 5) 的 Euler 亏格是2.     

Generalized multiplicities of edge ideals

We explore connections between the generalized multiplicities of square-free monomial ideals and the combinatorial structure of the underlying hypergraphs using methods of commutative algebra and polyhedral geometry. For instance, we show that the j-multiplicity is multiplicative over the connected components of a hypergraph, and we explicitly relate the j-multiplicity of the edge ideal of a properly connected uniform hypergraph to the Hilbert–Samuel multiplicity of its special fiber ring. In addition, we provide general bounds for the generalized multiplicities of the edge ideals and compute these invariants for classes of uniform hypergraphs.     

Almost all triangle-free triple systems are tripartite

A triangle in a triple system is a collection of three edges isomorphic to {123,124,345}. A triple system is triangle-free if it contains no three edges forming a triangle. It is tripartite if it has a vertex partition into three parts such that every edge has exactly one point in each part. It is easy to see that every tripartite triple system is triangle-free. We prove that almost all triangle-free triple systems with vertex set [n] are tripartite. Our proof uses the hypergraph regularity lemma of Frankl and R?dl [13], and a stability theorem for triangle-free triple systems due to Keevash and the second author [15].     

Localizable invariants of combinatorial manifolds and Euler characteristic

It is shown that if a real-valued PL-invariant of closed combinatorial manifolds admits a local formula that depends only on the f-vector of the link of each vertex, then the invariant must be a constant times the Euler characteristic.     

Hamiltonian cycles in bipartite quadrangulations on the torus

In this article, we shall prove that every bipartite quadrangulation G on the torus admits a simple closed curve visiting each face and each vertex of G exactly once but crossing no edge. As an application, we conclude that the radial graph of any bipartite quadrangulation on the torus has a hamiltonian cycle. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 69:143‐151, 2012     

Lines in hypergraphs

One of the De Bruijn-Erd?s theorems deals with finite hypergraphs where every two vertices belong to precisely one hyperedge. It asserts that, except in the perverse case where a single hyperedge equals the whole vertex set, the number of hyperedges is at least the number of vertices and the two numbers are equal if and only if the hypergraph belongs to one of simply described families, near-pencils and finite projective planes. Chen and Chvátal proposed to define the line uv in a 3-uniform hypergraph as the set of vertices that consists of u, v, and all w such that {u;v;w} is a hyperedge. With this definition, the De Bruijn-Erd?s theorem is easily seen to be equivalent to the following statement: If no four vertices in a 3-uniform hypergraph carry two or three hyperedges, then, except in the perverse case where one of the lines equals the whole vertex set, the number of lines is at least the number of vertices and the two numbers are equal if and only if the hypergraph belongs to one of two simply described families. Our main result generalizes this statement by allowing any four vertices to carry three hyperedges (but keeping two forbidden): the conclusion remains the same except that a third simply described family, complements of Steiner triple systems, appears in the extremal case.     

Interval hypergraphs and D-interval hypergraphs

A hypergraph $\text{H = (V,}\text{E}\text{)}$ is called an interval hypergraph if there exists a one-to-one function ? mapping the elements of V to points on the real line such that for each edge E, there is an interval I, containing the images of all elements of E, but not the images of any elements not in E₁. The difference hypergraph D(H) determined by H is formed by adding to $\text{E}$ all nonempty sets of the form E₁ ? E₁, where E₁ and E₁ are edges of HH is said to be a D-interval hypergraph if D(H) is an interval hypergraph. A forbidden subhypergraph characterization of D-interval hypergraphs is given. By relating D-interval hypergraphs to dimension theory for posets, we determine all 3-irreducible posets of length one.