关于不含k-C-圈的n阶r-一致超图的若干结果

主要讨论了不含k-C-圈的n阶r-一致超图,对不同的k,分别得出了它的极大边数的一个下界,并且得出在有些情况下它的下界是最大的.另外,我们得到了Krn含k-C-圈的一个充分必要条件.     

超图中的C-圈

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

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

研究了一般的标号严格(d)-连通无圈超图的计数,得到了n阶标号严格(d)-连通无圈超图的计数公式.     

无圈超图的计数

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

超图在圈中的嵌入问题

H为定义在圈G上的一个超图,将H的每条超边映射为圈G中不同的路,并且这条路包含此超边中的所有的顶点,此问题称为超边在圈G中的嵌入问题(MCHEC问题).超图在圈中的嵌入问题即为寻找H在G中的最优嵌入使得G中任一边被H所有超边的嵌入经过的最大次数最小.应用组合最优化以及概率方法可得到MCHEC问题的PTAS算法.     

超图的路和圈

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

一致超图谱半径界的改进结果

利用张量理论研究一致超图的谱半径.首先,利用对角相似张量与原张量同谱的性质,结合张量特征值的圆盘定理,给出谱半径的上界,这一上界严格小于最大度;其次,通过超图的度向量给出谱半径的下界.改进了超图谱半径上下界的原有结果.     

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

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

关于有限群的不可约特征标个数的一个结果

本文研究了一般的非交换有限群G的阶与不可约特征标个数的比值与群G结构之间的关系.通过群G阶的最小素因子和G的换位子群的阶的最小素因子,得出了这个比值的下界,并确定了达到下界的一个充分必要条件.     

图的强符号圈控制数

本文研究了图的强符号圈控制数γ′_(ssc)(G).利用最大独立集最大匹配等方法,刻画了满足γ′_(ssc)(G)=|E|-2的所有连通图,给出了γ′_(ssc)(G)的一个下界,求出了两类特殊图的强符号圈控制数.     

Dual blocking sets in projective and affine planes

A dual blocking set is a set of points which meets every blocking set but contains no line. We establish a lower bound for the cardinality of such a set, and characterize sets meeting the bound, in projective and affine planes.     

On Milnor's classes “L” and “D”

A twenty-one player counterexample is presented which disposes of two questions raised by J. W. Milnor in 1952 concerning the existence of certain pre-solutions, based on plausible lower and upper bounds to what a coalition should expect to receive in a cooperative game in characteristic function form. In the counterexample, the lower-bound set, known as “L”, is empty, and the upper-bound set, known as “D”, contains no efficient outcomes.     

Transformation of Quasiconvex Functions to Eliminate Local Minima

Quasiconvex functions present some difficulties in global optimization, because their graph contains “flat parts”; thus, a local minimum is not necessarily the global minimum. In this paper, we show that any lower semicontinuous quasiconvex function may be written as a composition of two functions, one of which is nondecreasing, and the other is quasiconvex with the property that every local minimum is global minimum. Thus, finding the global minimum of any lower semicontinuous quasiconvex function is equivalent to finding the minimum of a quasiconvex function, which has no local minima other than its global minimum. The construction of the decomposition is based on the notion of “adjusted sublevel set.” In particular, we study the structure of the class of sublevel sets, and the continuity properties of the sublevel set operator and its corresponding normal operator.     

A sylvester theorem for conic sections

If S is a finite set of points in the plane and no conic contains all points of S, then S determines a conic which contains exactly five points ofS.     

Exchange rings,units and idempotents

An associative ring R with identity is semiperfect if and only if every element of R is a sum of a unit and an idempotent, and R contains no infinite set of orthogonal idempotents. A ring which contains no infinite set of orthogonal idempotents is an exchange ring if and only if every element is a sum of a unit and an idempo-tent     

On directed graphs with an independent covering set

We prove that if a directed graph,D, contains no odd directed cycle and, for all but finitely many vertices, EITHER the in-degrees are finite OR the out-degrees are at most one, thenD contains an independent covering set (i.e. there is a kernel). We also give an example of a countable directed graph which has no directed cycle, each vertex has out-degree at most two, and which has no independent covering set.Research supported by N.S.E.R.C. grants #69-0982 and #69-0259.     

Subgraphs of a hypercube containing no small even cycles

We investigate several Ramsey-Turán type problems for subgraphs of a hypercube. We obtain upper and lower bounds for the maximum number of edges in a subgraph of a hypercube containing no four-cycles or more generally, no 2k-cycles C_2k. These extermal results imply, for example, the following Ramsey theorems for hypercubes: A hypercube can always be edge-partitioned into four subgraphs, each of which contains no six-cycle. However, for any integer t, if the n-cube is edge-partitioned into t sub-graphs, then one of the subgraphs must contain an edight-cycle, provided only than n is sufficiently large (depending only on t).     

Sparsely intersecting perfect matchings in cubic graphs

In 1971, Fulkerson made a conjecture that every bridgeless cubic graph contains a family of six perfect matchings such that each edge belongs to exactly two of them; equivalently, such that no three of the matchings have an edge in common. In 1994, Fan and Raspaud proposed a weaker conjecture which requires only three perfect matchings with no edge in common. In this paper we discuss these and other related conjectures and make a step towards Fulkerson’s conjecture by proving the following result: Every bridgeless cubic graph which has a 2-factor with at most two odd circuits contains three perfect matchings with no edge in common.