Degree Sequences and the Existence of <Emphasis Type="Italic">k</Emphasis>-Factors

We consider sufficient conditions for a degree sequence π to be forcibly k-factor graphical. We note that previous work on degrees and factors has focused primarily on finding conditions for a degree sequence to be potentially k-factor graphical. We first give a theorem for π to be forcibly 1-factor graphical and, more generally, forcibly graphical with deficiency at most β ≥ 0. These theorems are equal in strength to Chvátal’s well-known hamiltonian theorem, i.e., the best monotone degree condition for hamiltonicity. We then give an equally strong theorem for π to be forcibly 2-factor graphical. Unfortunately, the number of nonredundant conditions that must be checked increases significantly in moving from k = 1 to k = 2, and we conjecture that the number of nonredundant conditions in a best monotone theorem for a k-factor will increase superpolynomially in k. This suggests the desirability of finding a theorem for π to be forcibly k-factor graphical whose algorithmic complexity grows more slowly. In the final section, we present such a theorem for any k ≥ 2, based on Tutte’s well-known factor theorem. While this theorem is not best monotone, we show that it is nevertheless tight in a precise way, and give examples illustrating this tightness.     

Neighbourhood-Perfect Line Graphs

We show that the line graph of any balanced hypergraph is neighbourhood-perfect. This result is a hypergraphic extension of a recent theorem in [GKLM] saying that the line graphs of bipartite graphs are neighbourhood-perfect. The note contains also a graphical extension of the same theorem: the characterization of all graphs with neighbourhood-perfect line graph. The proof relies on a characterization of neighbourhood-perfect graphs among line graphs in terms of forbidden induced subgraphs.     

有理分式的增广图示及其在工程控制论中的应用

本文研究有理分式的增广图示,分子分母分别为n及m次多项式的有理分式,它的根轨迹方程的次数,当n+m是偶数时,是y2的(n+m)/2-1次;当n+m是奇数时,是(n+m-1)/2次.因此,n+m≤10的图示数据能用公式计算有理分式的增广图示能应用于研究反馈系统及特征方程的任一实系数作参数的图线特性.用本文理论易证倒分式定理:K₁=f(n)(s)/(F)(m)(s),与K₂=F(m)(s)/f(n)(s)二者在复数平面上的根轨迹完全相同又由图示知识发现,不论n和m多大,只要有理分式的零点和极点在实轴上相间排列,它就没有复数根轨迹,这样的系统不会发生振荡,本文对这种分式可能存在的稳定区作较全面地分析.     

Monomorphisms of finitely generated free groups have finitely generated equalizers

Summary The authors' approach to Gersten's graphical model of an automorphism is generalized to prove the theorem of the title, resolving a conjecture of Stallings.     

Graphical algebras — a new approach to congruence lattices

In 1970, H. Werner considered the question of which sublattices of partition lattices are congruence lattices for an algebra on the underlying set of the partition lattices. He showed that a complete sublattice of a partition lattice is a congruence lattice if and only if it is closed under a new operation called graphical composition. We study the properties of this new operation, viewed as an operation on an abstract lattice. We obtain some necessary properties, and we also obtain some sufficient conditions for an operation on an abstract lattice L to be this operation on a congruence lattice isomorphic to L. We use this result to give a new proof of Grätzer and Schmidt’s result that any algebraic lattice occurs as a congruence lattice.     

Coincidence of the sets of minimal and irreducible join graphs over primary structure of algebraic Bayesian networks

An algebraic Bayesian network (ABN) is a probabilistic-logic graphical model of bases of knowledge patterns with uncertainty. A primary structure of an ABN is a set of knowledge patterns, that are ideals of conjunctions of positive literals except the empty conjunction endowed with scalar or interval probability estimates. A secondary ABN structure is represented by a graph constructed over the primary structure, which is called a join graph. From the point of view of learning of a global ABN structure, of interest are join graphs with the minimum number of edges and irreducible join graphs. A theorem on the coincidence of the sets of minimal and irreducible join graphs over the same primary structure is proved. A greedy algorithm constructing an arbitrary minimal join graph from a given primary structure is described. A theorem expressing the number of edges in a minimal join graph as the sum of the ranks of the incidence matrices of strong restrictions of a maximal join graph minus the number of significant weights is stated and proved. A generalized graph of maximal knowledge patterns (GGMKP) is a graph with the same vertex set as the join graph which is not subject to any constraints concerning the possibility of joining two vertices by an edge. It is proved that the pair consisting of the edge set of a maximal GGMKP and the set of all subsets of this graph such that the subtraction of any such subset from the maximal GGMKP yields an edge of the join graph on the same vertex set is a matroid.     

Approximation of curves by fairness splines with tangent conditions

We present in this paper an approximation method of curves from sets of Lagrangian data and vectorial tangent subspaces. We define a discrete smoothing fairness spline with tangent conditions by minimizing certain quadratic functional on finite element spaces. Convergence theorem is established and some numerical and graphical examples are analyzed in order to show the validity and the effectiveness of this paper.     

A new look at solving inequalities

Several ways for solving inequalities have been suggested in the literature, among them graphical, verbal and algebraic solutions. A new look at solving inequalities via use of the intermediate value theorem is presented here, and this method may prove to be straightforward for many students.     

A Berge-keeping operation for graphs

We prove that a certain simple operation does not create odd holes or odd antiholes in a graph unless there are already some. In order to apply it, we need a vertex whose neighborhood has a coloring where the union of any two color classes is a connected graph; the operation is the shrinking of each of the color classes. Odd holes and antiholes do have such a vertex, and this property of minimal imperfect graphs implies the strong perfect graph theorem through the results of the paper. Conceivably, this property may be a target in the search for a proof of the strong perfect graph theorem different from the monumental achievement of Chudnovsky, Robertson, Seymour, and Thomas.     

The generation of clones with majority operations

A theorem by Baker and Pixley implies that any clone on a finite set is finitely generated if it contains a near-unanimity operation. This raises the question of what arity the generating operations must have. In this paper, we solve the last open bits of this problem for the majority case by showing that 5 and 8 are the smallest integers k such that every clone with a majority operation on a 3 and 4-element set, respectively, is generated by its k-ary part.     

On the structure of dimonoids

J. -L. Loday introduced the notion of a dimonoid and constructed the free dimonoid. Cayley’s theorem for dimonoids states that every dimonoid is isomorphic to some transformation dimonoid. In this paper we propose another approach to constructing dimonoids which is based on using a semigroup operation. Several dimonoid-theoretical constructions are suggested, and it is shown that any dimonoid is isomorphically embedded into some dimonoid constructed from a semigroup. A similar result is obtained for dirings.     

PBW deformations of quadratic monomial algebras

A result of Braverman and Gaitsgory from 1996 gives necessary and sufficient conditions for a filtered algebra to be a Poincaré-Birkhoff-Witt (PBW) deformation of a Koszul algebra. The main theorem in this paper establishes conditions equivalent to the Braverman-Gaitsgory Theorem to efficiently determine PBW deformations of quadratic monomial algebras. In particular, a graphical interpretation is presented for this result, and we discuss circumstances under which some of the conditions of this theorem need not be checked. Several examples are also provided. Finally, with these tools, we show that each quadratic monomial algebra admits a nontrivial PBW deformation.     

A short proof of two shuffling theorems for tilings and a weighted generalization

Recently, Lai and Rohatgi discovered a shuffling theorem for lozenge tilings of doubly-dented hexagons, which generalized the earlier work of Ciucu. Later, Lai proved an analogous theorem for centrally symmetric tilings, which generalized some other previous work of Ciucu. In this paper, we give a unified proof of these two shuffling theorems, which also covers the weighted case. Unlike the original proofs, our arguments do not use the graphical condensation method but instead rely on a well-known tiling enumeration formula due to Cohn, Larsen, and Propp. Fulmek independently found a similar proof of Lai and Rohatgi's original shuffling theorem. Our proof also gives a simple explanation for Ciucu's recent conjecture relating the total number and the number of centrally symmetric lozenge tilings.     

Hypergraphical t-designs

We introduce a theory of hypergraphical t-designs. We show the existence of these designs and prove a finiteness theorem on these designs for infinitely many parameter sets. We also give effective bounds on the number of points in these cases. These results generalize some results on graphical t-designs of Alltop, Chee and Betten-Klin-Laue-Wassermann.     

The Australian National Bushfire model project

The National Bushfire Research Unit has developed a personal computer based model to act as a shell for a decision support system for bushfire management. To date the fire spread module has been developed, and there is a continuing programme to incorporate expert systems. The model is designed for real-time operation. Inputs to the model combine a geographic information system (GIS) with real-time data acquisition and data assimilation through modem connections to telephone lines. Outputs are graphical and allow the fire-front position, which is generated using Huygens' principle, to be examined at any desired scale.     

Approximation by Kantorovich-Szász Type Operators Based on Brenke Type Polynomials

In this article, we give a generalization of the Kantorovich-Szász type operators defined by means of the Brenke type polynomials introduced in the literature and obtain convergence properties of these operators by using Korovkin’s theorem. Some graphical examples using the Maple program for this approximation are given. We also establish the order of convergence by using modulus of smoothness and Peetre’s K-functional and give a Voronoskaja type theorem. In addition, we deal with the convergence of these operators in a weighted space.     

A graphical method for valuing switching options

This paper introduces a graphical method for valuing options on real asset investments that allow the investor to switch between different operating modes at a single point-in-time. The technique uses mixtures of truncated exponential functions to approximate both the probability density function for project value and the expressions for option value of each alternative. The distribution for project value is transformed into an expected cash flow function for the option under each mode of operation. After determining an optimal exercise strategy, these functions are used to determine the option value. The graphical method allows the option exercise strategy to be communicated effectively through a graphical representation of the expected cash flow functions. A comparison of this approach to the existing binomial lattice method is presented. The efficiency of the graphical method is comparable to the binomial lattice and in some cases accurate solutions can be obtained with less CPU time.     

Diagnosing Bootstrap Success

We show that convergence of intuitive bootstrap distributions to the correct limit distribution is equivalent to a local asymptotic equivariance property of estimators and to an asymptotic independence property in the bootstrap world. The first equivalence implies that bootstrap convergence fails at superefficiency points in the parameter space. However, superefficiency is only a sufficient condition for bootstrap failure. The second equivalence suggests graphical diagnostics for detecting whether or not the intuitive bootstrap is trustworthy in a given data analysis. Both criteria for bootstrap convergence are related to Hájek's (1970, Zeit. Wahrscheinlichkeitsth., 14, 323-330) formulation of the convolution theorem and to Basu's (1955, Sankhy, 15, 377-380) theorem on the independence of an ancillary statistic and a complete sufficient statistic.     

FC-空间上的相交定理,不等式系解的存在定理

给出了没有任何凸结构的FC-空间上相交定理,并利用此结论得到了变分不等式解的存在定理.最后作为应用,给出了互为等价的集族的相交定理和不等式系的公共解的存在定理,所得结论推广和改进了文献中的相应结果.     

Adjoint Linear Systems on Normal Log Surfaces

We prove a Reider type theorem for separating any cluster by an adjoint system to a pseudoeffective divisor on a normal surface. As a corollary we get a Reider type theorem for adjoint linear systems (to a nef Q-divisor) on normal log surfaces. This theorem is new even for smooth surfaces.