无标号真严格(d)-连通无圈超图的计数

本文得到了无标号真严格(d)-连通无圈超图的计数公式,并得到了无标号真严格(d)-连通同胚k不可约无圈超图的计数公式.     

无圈超图的计数

研究了标号超图的计数, 得到2个公式: 一个是关于严格(D)-连通无圈齐超图的显式计数公式, 另一个是关于线性无圈超图数目的递推公式.     

无圈超图规模的进一步研究

本文在王建方给出的严格(d)-连通κ-匀齐无圈超图的规模的基础上,进一步研究n阶(d)-连通κ-匀齐无圈超图的规模和非严格(d)-连通κ-匀齐无圈超图的规模,并分别得到它们规模的上下界.     

匀称无圈超图的计数

研究了标号匀称无圈超图的计数, 得到了一般的$n$阶标号r-匀称(d)-森林和n阶标号r-匀称(d)-真森林的递推公式,并分别得到了包含和不包含独立点的$n$阶标号森林的计数显式.     

严格非匀称线性超树的计数公式

本文应用容斥原理，得到了有n个顶点、m条边的严格非匀称标号线性无圈超图的计数公式。     

图带宽和与其对偶超图带宽和的关系

设H=（E1,E2,…,Em）是集合X上的一个超图,一个1-1映射f:X→{1,2,…,|X|}称为H的一个标号,对H的任一标号f,BS（H,f）=∑(E∈H)max{|f(u)-f(v)|;u,v∈E}称为超图H的关于标号f的带宽和BS(H)=min{BS(H,f)|f是超图H的标号|}称为H的带宽和．论文研究图带宽和与其对偶超图的带宽和这两个参数间的关系．     

关于匀称超树数的猜想

1982年,毛经中对(k 1) p阶和q边的匀称超树的个数T_(k 1)(p,q)提出如下猜想:其余 易见,当k(?)1时,T(p, q) (q-1)~(?) p~p(?),故(*)成立将是标号树计数的Cayley公式在超图理论中的推广。 本书证明了上述猜想并得到一般超图的计数式。 定义 如果超图H (X,ε)是连通的且不含圈,则称H为一超树,若(?)E_i∈ε,|E_i|=M,则称H是匀称M秩超树。     

超图的路和圈

超图是离散数学中最一般最复杂的结构 .无圈超图已被证明在数据库设计中非常有用 .从关系数据的结构出发 ,建立了关于超图的路、连通性和圈的新的公理系统 .该系统与特殊情形———图是符合的 .引入了虚圈和实圈的概念 ,这是一对相关联的概念 .虚圈在特殊情形———图中不存在 ,退化掉了 .定义了超图圈的相关性和独立性 ,给出了超图中最大独立实圈数目的计数公式 ,对特殊情形———图 ,这个公式就是Euler公式 .     

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

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

超图中的C-圈

在本文我们给出了一个新的定义C-圈.设f(n,k,r)是不含C-圈的n阶r-一致超图的最大可能边数,我们主要是确定f(n,k,r)或给出它的一个下界.另外,我们给出了超图不含C-圈的一个充分必要条件.     

秩为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     

Economical Covers with Geometric Applications

A cover of a hypergraph is a collection of edges whose unioncontains all vertices. Let H = (V, E) be a k-uniform, D-regularhypergraph on n vertices, in which no two vertices are containedin more than o(D/e^2k log D) edges as D tends to infinity. Ourresults include the fact that if k = o(log D), then there isa cover of (1 + o(1))n/k edges, extending the known result thatthis holds for fixed k. On the other hand, if k 4 log D thenthere are k-uniform, D-regular hypergraphs on n vertices inwhich no two vertices are contained in more than one edge, andyet the smallest cover has at least (nk) log (k log D)) edges.Several extensions and variants are also obtained, as well asthe following geometric application. The minimum number of linesrequired to separate n random points in the unit square is,almost surely, (n^2/3 / (log n)^1/3). 2000 Mathematical SubjectClassification: 05C65, 05D15, 60D05.     

超图中的着色问题

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

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     

Color-bounded hypergraphs, II: Interval hypergraphs and hypertrees

A color-bounded hypergraph is a hypergraph (set system) with vertex set X and edge set E={E₁,…,E_m}, together with integers s_i and t_i (1≤s_i≤t_i≤|E_i|) for i=1,…,m. A vertex coloring φ is feasible if the number of colors occurring in edge E_i satisfies s_i≤|φ(E_i)|≤t_i, for every i≤m.In this paper we point out that hypertrees-hypergraphs admitting a representation over a (graph) tree where each hyperedge E_i induces a subtree of the underlying tree-play a central role concerning the set of possible numbers of colors that can occur in feasible colorings. We also consider interval hypergraphs and circular hypergraphs, where the underlying graph is a path or a cycle, respectively. Sufficient conditions are given for a ‘gap-free’ chromatic spectrum; i.e., when each number of colors is feasible between minimum and maximum. The algorithmic complexity of colorability is studied, too.Compared with the ‘mixed hypergraphs’-where ‘D-edge’ means (s_i,t_i)=(2,|E_i|), while ‘C-edge’ assumes (s_i,t_i)=(1,|E_i|−1)-the differences are rather significant.     

Color-bounded hypergraphs, IV: Stable colorings of hypertrees

We consider vertex colorings of hypergraphs in which lower and upper bounds are prescribed for the largest cardinality of a monochromatic subset and/or of a polychromatic subset in each edge. One of the results states that for any integers s≥2 and a≥2 there exists an integer f(s,a) with the following property. If an interval hypergraph admits some coloring such that in each edge E_i at least a prescribed number s_i≤s of colors occur and also each E_i contains a monochromatic subset with a prescribed number a_i≤a of vertices, then a coloring with these properties exists with at most f(s,a) colors. Further results deal with estimates on the minimum and maximum possible numbers of colors and the time complexity of determining those numbers or testing colorability, for various combinations of the four color bounds prescribed. Many interesting problems remain open.