关于D-完全一致混合超图上色数的一个结论的推广

混合超图的上、下色数的研究是超图研究中一个重要的话题.由于超图本身结构上的复杂性,近年来对超图色性的研究也近局限于对一些特殊图类的研究,其中完全一致混合超图是最为热门的图类之一.给出了D完全(C不完全)一致混合超图的概念,并运用组合数学中有关分划的思想和方法对该图类的色性进行了进一步的研究,对相关文献中给出的结论进行了推广,得到了一个较为一般化的结论.并在该定理的证明中得到并证明了一个关于混合超图C稳定集的重要论断,对超图色性研究有着重要的意义.     

Quasi-random hypergraphs

We introduce an equivalence class of varied properties for hypergraphs. Any hypergraph possessing any one of these properties must of necessity possess them all. Since almost all random hypergraphs share these properties, we term these properties quasi-random. With these results, it becomes quite easy to show that many natural explicit constructions result in hypergraphs which imitate random hypergraphs in a variety of ways.     

Codismantlability and projective dimension of the Stanley–Reisner ring of special hypergraphs

In this paper, we generalize the concept of codismantlable graphs to hypergraphs and show that some special vertex decomposable hypergraphs are codismantlable. Then we generalize the concept of bouquet in graphs to hypergraphs to extend some combinatorial invariants of graphs about disjointness of a set of bouquets. We use these invariants to characterize the projective dimension of Stanley–Reisner ring of special hypergraphs in some sense.     

Some hypergraphs and packing problems associated with matrices of 0's and 1's

We define various classes of hypergraphs associated with m × n matrices of 0's and 1's and determine for which classes the maximum cardinality of a set of pairwise disjoint edges equals the minimum cardinality of a set of nodes that cover all edges independently of the matrix.     

On the Laplacian Spectrum and Walk-regular Hypergraphs

We use the generalization of the Laplacian matrix to hypergraphs to obtain several spectral-like results on hypergraphs. For instance, we obtain upper bounds on the eccentricity and the excess of any vertex of hypergraphs. We extend to the case of hypergraphs the concepts of walk regularity and spectral regularity, showing that all walk-regular hypergraphs are spectrally-regular. Finally, we obtain an upper bound on the mean distance of walk-regular hypergraphs that involves all the Laplacian spectrum.     

On the Laplacian Spectrum and Walk-regular Hypergraphs

We use the generalization of the Laplacian matrix to hypergraphs to obtain several spectral-like results on hypergraphs. For instance, we obtain upper bounds on the eccentricity and the excess of any vertex of hypergraphs. We extend to the case of hypergraphs the concepts of walk regularity and spectral regularity, showing that all walk-regular hypergraphs are spectrally-regular. Finally, we obtain an upper bound on the mean distance of walk-regular hypergraphs that involves all the Laplacian spectrum.     

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.     

超图的Alcuin数与其横贯数的关系

1000多年前, 英国著名学者Alcuin曾提出过一个古老的渡河问题, 即狼、羊和卷心菜的渡河问题. 最近, Prisner和Csorba等考虑了一般``冲突图"上的渡河问题. 将这一问题推广到超图$H=(V,\mathcal{E})$\,上, 考虑一类情况更一般的运输计划问题. 现在监管者 欲运输超图中的所有点\,(代表``items")\,渡河, 这里$V$的点子 形成超边 当且仅当这些点代表的``items"在无人监管的情况下不能留在一起. 超图$H$的Alcuin数是指超图$H$具有可行运输方案\,(即把$V$的点代表的``items" 全部运到河对岸)\,时船的最小容量. 给出了 $r$-一致完全二部超图和它的伴随超图, 以及$r$-一致超图的Alcuin数, 同时证明了判断$r$-一致超图是否为小船图是NP 困难的.     

Generating Scenarios of Division as Sharing and Grouping: A Study of Japanese Elementary and University Students

Elementary school students learn two types of division scenarios: partitive and quotitive. Previous researchers have assumed that the partitive scenario is easier because it reflects the everyday notion of sharing, whereas the quotitive scenario, which represents grouping, is more difficult and is understood gradually in the course of mathematics learning. However, this assumption has not been adequately investigated in empirical studies. The present study examines the assumption in a cross-sectional study. Participants were 336 elementary school students (98 in Grade 3, 82 in Grade 4, 88 in Grade 5, and 68 in Grade 6) and 70 university students who performed two tasks. In the preference task, they generated a division scenario of any type consistent with a given numerical equation. In the problem-posing task, they generated a division scenario consistent with both a numerical equation and a picture representing a partitive or quotitive scenario. On the preference task, students at all grade levels preferred the partitive to the quotitive scenario, and this preference increased with students’ grade level. On the problem-posing task, younger students (Grades 3, 4, and 5) had equivalent success in the partitive and quotitive scenarios, but older students (Grade 6 and university) found the partitive scenario to be easier than the quotitive. Implications for mathematics education are discussed.     

The existence spectrum of Meta(K 4 (3) >K 4 (3) − e)

Let H and J1 be both t-uniform hypergraphs. Let J2 be a sub-hypergraph of J1. In this paper, the metamorphosis of a hypergraph decomposition is introduced, denoted by (H, J1 J2)-design, which is a generalization of the concept of metamorphosis of a graph decomposition. Let Meta(J1J2) denote the set of all integers v such that there exists a (Kv((3)), J1J2)-design. We completely determine the set Meta(K4((3))K4((3))-e).     

Join-Irreducible Boolean Functions

This paper is a contribution to the study of a quasi-order on the set Ω of Boolean functions, the simple minor quasi-order. We look at the join-irreducible members of the resulting poset [(W)\tilde]\tilde{\Omega}. Using a two-way correspondence between Boolean functions and hypergraphs, join-irreducibility translates into a combinatorial property of hypergraphs. We observe that among Steiner systems, those which yield join-irreducible members of [(W)\tilde]\tilde{\Omega} are the − 2-monomorphic Steiner systems. We also describe the graphs which correspond to join-irreducible members of [(W)\tilde]\tilde{\Omega}.     

秩为r的本原超图的指数集(英文)

本文研究了超图的本原性质.运用图论方法,得到了具有秩r(≥3)的所有n阶本原有向超图的指数集,并刻划了其极超图.     

Multidimensional clustering and hypergraphs

We discuss a multidimensional generalization of the clustering method. In our approach, the clustering is realized by partially ordered hypergraphs belonging to some family. The suggested procedure is applicable in the case where the original metric depends on a set of parameters. The clustering hypergraph studied here can be regarded as an object describing all possible clustering trees corresponding to different values of the original metric.     

Cones of alternating and cut submodular set functions

We describe facets of the cones of alternating set functions and cut submodular set functions generated by directed and undirected graphs and by uniform even hypergraphs. This answers a question asked by L. Lovász at the Bonn Mathematical Programming Conference in 1982. We show that there is a network flow algorithm for minimizing a hypergraph cut set function.     

Cost colourings of hypergraphs

Some aspects of the cost colouring of hypergraphs are considered in the paper. A generalisation of the well-known Brook's theorem for a cost colouring of hypergraphs is proved. Moreover, a relation between the minimal cost of a colouring of a hypergraph with a set of costs which produce an arithmetic sequence and a number of edges of this hypergraph is investigated.     

本原简单超图的指数集

设H是一个超图, 用H\+*和L(H)分别表示H的对偶超图和线图. 定义H的邻接图是由L(H\+*)和H的所有环组成的图, 记作G\-H. 若G\-H是本原的, 则称H是本原的, 并称γ(G\-H)为H的指数. 该文得到了所有n阶本原简单超图以及所有秩不小于3的n阶本原简单超图的指数集, 并分别刻划了其极超图.     

Independent sets in bounded-degree hypergraphs

In this paper we analyze several approaches to the Maximum Independent Set (MIS) problem in hypergraphs with degree bounded by a parameter Δ. Since independent sets in hypergraphs can be strong and weak, we denote by MIS (MSIS) the problem of finding a maximum weak (strong) independent set in hypergraphs, respectively. We propose a general technique that reduces the worst case analysis of certain algorithms on hypergraphs to their analysis on ordinary graphs. This technique allows us to show that the greedy algorithm for MIS that corresponds to the classical greedy set cover algorithm has a performance ratio of (Δ+1)/2. It also allows us to apply results on local search algorithms on graphs to obtain a (Δ+1)/2 approximation for the weighted MIS and (Δ+3)/5−? approximation for the unweighted case. We improve the bound in the weighted case to ⌈(Δ+1)/3⌉ using a simple partitioning algorithm. We also consider another natural greedy algorithm for MIS that adds vertices of minimum degree and achieves only a ratio of Δ−1, significantly worse than on ordinary graphs. For MSIS, we give two variations of the basic greedy algorithm and describe a family of hypergraphs where both algorithms approach the bound of Δ.     

Elementary Preservice Teachers’ Transitional Conceptions of Partitive Division with Proper-Fraction Divisors

An understanding of partitive division is foundational for numerous other mathematics topics, including unit rate, slope, and probability. However, research has shown that learners tend to have a limited understanding of partitive division when the divisor is a proper fraction. To extend research on conceptions of partitive division in this study, we used Moschkovich’s (1999) transitional conceptions perspective to examine how conceptions of partitive division evolve. This article reports on preservice teachers’ (PSTs) conceptions of partitive division with proper-fraction divisors before and after they explored partitive division in a mathematics content course for elementary teachers (N = 17). Our analysis of pre- and post-interviews revealed an initial transitional conception and two levels of refinement of their conceptions. Furthermore, we identified two perturbations that PSTs experienced during refinement of their conceptions. By identifying ordered levels of refinement and associated perturbations, this exploratory study extends the transitional conceptions perspective. Furthermore, this study adds new insights into the conceptual complexities that the partitive model for division of fractions presents to PSTs (and to learners in general) and suggests new hypotheses about ways that conceptions of partitive division undergo refinement.     

Value of games with two-layered hypergraphs

This paper studies cooperative games with restricted cooperation among players. We define situations in which a priori unions and hypergraphs coexist simultaneously and mutually depend on each other. We call such structures two-layered hypergraphs. Using a two-step approach, we define a value of the games with two-layered hypergraphs. The value is characterized by Owen’s coalitional value of hypergraph-restricted games and in terms of weighted Myerson value. Further, our value is axiomatically characterized by component efficiency and a coalition size normalized balanced contributions property.     

Betti Numbers of Hypergraphs

In this article, we study some algebraic properties of hypergraphs, in particular their Betti numbers. We define some different types of complete hypergraphs, which to the best of our knowledge are not previously considered in the literature. Also, in a natural way, we define a product on hypergraphs, which in a sense is dual to the join operation on simplicial complexes. For such product, we give a general formula for the Betti numbers, which specializes neatly in case of linear resolutions.