What must and what need not be contained in a graph of uncountable chromatic number?

We investigate the following problem: What countable graphs must a graph of uncountable chromatic number contain? We define two graphsΓ andΔ which are very similar and we show thatΓ is contained in every graph of uncountable chromatic number, whileΔ is (consistently) not.     

Some variations on a theme by Buneman

In 1971, Peter Buneman presented a paper in which he described, amongst other things, a way to construct a tree from a collection of pairwise compatible splits of a finite set. This construction is immediately generalizable to a collection of arbitrary splits, in which case it gives rise to theBuneman graph, a certain connected, median graph representing the given collection of splits in a canonical fashion. In this paper, we look at the complex obtained by filling those faces of the associated hypercube whose vertices consist only of vertices in the Buneman graph, a complex that we call theBuneman complex. In particular, we give a natural filtration of the Buneman complex, and show that this filtration collapses when the system of splitis is weakly compatible. In the case where the family of splits is not weakly compatible, we also see that the filtration naturally gives us a way to associate a graded hierarchy of phylogenetic networks to the collection of splits.     

A near subtraction result in metric spaces (the locally closed graph case)

This paper concerns a near subtraction result for multifunctions with locally closed graph in metric spaces.     

Counting points on varieties over finite fields related to a conjecture of Kontsevich

We describe a characteristic-free algorithm for reducing an algebraic variety defined by the vanishing of a set of integer polynomials. In very special cases, the algorithm can be used to decide whether the number of points on a variety, as the ground field varies over finite fields, is a polynomial function of the size of the field. The algorithm is then used to investigate a conjecture of Kontsevich regarding the number of points on a variety associated with the set of spanning trees of any graph. We also prove several theorems describing properties of a (hypothetical) minimal counterexample to the conjecture, and produce counterexamples to some related conjectures.Partially supported by NSF Grant DMS-9700787 and RIMS, Kyoto University.     

On an obstruction for perfect matchings

Steffens [3] introduced a substructure (called below a “compressed set”) which prevents a graph from having a perfect matching, and proved that a countable graph possesses a perfect matching if and only if it does not contain such a substructure. In this paper we study some properties of compressed sets. Dedicated to Paul Erdős on his seventieth birthday     

The erdös-dushnik-miller theorem for topological graphs and orders

A topological graph is a graph G=(V, E) on a topological space V such that the edge set E is a closed subset of the product space V x V. If the graph contains no infinite independent set then, by a well-known theorem of Erdös, Dushnik and Miller, for any infinite set LV, there is a subset LL of the same oardinality |L| = |L| such that the restriction G L is a complete graph. We investigate the question of whether the same conclusion holds if we weaken the hypothesis and assume only that some dense subset AV does not contain an infinite independent set. If the cofinality cf (|L|)>|A|, then there is an L as before, but if cf (|L|)<-|A|, then some additional hypothesis seems to be required. We prove that, if the graph GA is a comparability graph and A is a dense subset, then for any set LV such that cf (|L|)>, there is a subset LL of size |L|=|L| such that GL is complete. The condition cf (|L|)> is needed.Research supported by NSERC grant #A5198.     

Efficient representation of perm groups

This note presents an elementary version of Sims's algorithm for computing strong generators of a given perm group, together with a proof of correctness and some notes about appropriate lowlevel data structures. Upper and lower bounds on the running time are also obtained. (Following a suggestion of Vaughan Pratt, we adopt the convention that perm=permutation, perhaps thereby saving millions of syllables in future research.)Dedicated to the memory of Marshall HallThis research was supported in part by the National Science Foundation under grant CCR-86-10181, and by Office of Naval Research contract N00014-87-K-0502.     

Improvement on the bound of Hermite matrix polynomials

In this paper, we introduce an improved bound on the 2-norm of Hermite matrix polynomials. As a consequence, this estimate enables us to present and prove a matrix version of the Riemann-Lebesgue lemma for Fourier transforms. Finally, our theoretical results are used to develop a novel procedure for the computation of matrix exponentials with a priori bounds. A numerical example for a test matrix is provided.     

Computing the composition factors of a permutation group in polynomial time

Given generators for a group of permutations, it is shown that generators for the subgroups in a composition series can be found in polynomial time. The procedure also yields permutation representations of the composition factors. Research supported by National Science Foundation Grants DCR-8403745 and DCR-8609491     

Edge partitions of the Rado graph

We will prove that for every colouring of the edges of the Rado graph, (that is the countable homogeneous graph), with finitely many coulours, it contains an isomorphic copy whose edges are coloured with at most two of the colours. It was known [4] that there need not be a copy whose edges are coloured with only one of the colours. For the proof we use the lexicographical order on the vertices of the Rado graph, defined by Erdös, Hajnal and Pósa.Using the result we are able to describe a Ramsey basis for the class of Rado graphs whose edges are coloured with at most a finite number,r, of colours. This answers an old question of M. Pouzet.Supported by the French PRC Math-Info.Supported by NSERC of Canada Grant # 691325.     

Exact finite-difference schemes for two-dimensional linear systems with constant coefficients

An exact finite-difference scheme for a system of two linear differential equations with constant coefficients, (d/dt)x(t)=Ax(t)$(\mathrm{d}/\mathrm{d}t)\mathbf{x}(t)=A\mathbf{x}(t)$, is proposed. The scheme is different from what was proposed by Mickens [Nonstandard Finite Difference Models of Differential Equations, World Scientific, New Jersey, 1994, p. 147], in which the derivatives of the two equations are formed differently. Our exact scheme is in the form of (1/φ(h))(_xk+1-_xk)=A[θ_xk+1+(1-θ)_xk]$(1/\phi (h))({\mathbf{x}}_{k+1}-{\mathbf{x}}_k)=A[\theta {\mathbf{x}}_{k+1}+(1-\theta ){\mathbf{x}}_k]$; both derivatives are in the same form of (_xk+1-_xk)/φ(h)$(x_{k+1}-x_k)/\phi (h)$.     

Maximal tight sets and the edmonds—Gallai decomposition for matchings

The Edmonds—Gallai decomposition theorem for matchings of finite or locally finite graphs is generalized to matchings of the kernel of an arbitrary graph.     

二分图中度条件和k-因子的存在性

本文主要研究了二分图中任意一对距离为２的顶点的度数与ｋ－因子关系,给出了二分图有ｋ因子的若干充分条件,并说明这些条件是最好的可能,从而证明了Ｎｉｓｈｉｍｕｒａ提出的问题对二分图成立。     

一类偶阶图的边优美性

本文讨论了一类偶阶图的边优美性。同时得到了完全图是边优美图的充要条件。     

Computing ODE symmetries as abnormal variational symmetries

We give a new computational method to obtain symmetries of ordinary differential equations. The proposed approach appears as an extension of a recent algorithm to compute variational symmetries of optimal control problems [P.D.F. Gouveia, D.F.M. Torres, Automatic computation of conservation laws in the calculus of variations and optimal control, Comput. Methods Appl. Math. 5 (4) (2005) 387-409], and is based on the resolution of a first order linear PDE that arises as a necessary and sufficient condition of invariance for abnormal optimal control problems. A computer algebra procedure is developed, which permits one to obtain ODE symmetries by the proposed method. Examples are given, and results compared with those obtained by previous available methods.     

On the probability of the occurrence of a copy of a fixed graph in a random distance graph

The threshold probability of the occurrence of a copy of a balanced graph in a random distance graph is obtained. The technique used by P. Erd?s and A. Rényi for determining the threshold probability for the classical random graph could not be applied in the model under consideration. In this connection, a new method for deriving estimates of the number of copies of a balanced graph in a complete distance graph is developed.     

On the number of vertices and edges of the Buneman graph

In 1971, Peter Buneman proposed a way to construct a tree from a collection of pairwise compatible splits. This construction immediately generalizes to arbitrary collections of splits, and yields a connected median graph, called the Buneman graph. In this paper, we prove that the vertices and the edges of this graph can be described in a very simple way: given a collection of splitsS, the vertices of the Buneman graph correspond precisely to the subsetsS′ ofS such that the splits inS′ are pairwise incompatible and the edges correspond to pairs (S′, S) withS′ as above andS∈S′. Using this characterization, it is much more straightforward to construct the vertices of the Buneman graph than using prior constructions. We also recover as an immediate consequence of this enumeration that the Buneman graph is a tree, that is, that the number of vertices exceeds the number of edges (by one), if and only if any two distinct splits inS are compatible.     

关于一类(g,f)-3-覆盖图的判据

本文首先给出了(g,f)-3-覆盖图的定义,即一个图G称为(g,f)-3-覆盖图,如果G的任何三条边都属于它的一个(g,f)-因子；其次,黄光鑫曾先后给出了当g＜f时一个二部图分别是(g,f)-2-覆盖图和(g,f)-3-覆盖图的充分必要条件,在此基础上,本文进一步得到了,当g≤f时一个二部图G=(X,Y)是(g,f)-3-覆盖图的一个充分必要条件；最后,研究了f(X)=f(Y)的情形,得到了当f(X)=f(Y)时一个二部图G=(X,Y)是f-3-覆盖图的一个充分必要条件．     

Symbolic software for soliton theory

Four symbolic programs, in Macsyma or Mathematica language, are presented. The first program tests forthe existence of solitons for nonlinear PDEs. It explicitly constructs solitons using Hirota's bilinear method. In the second program, the Painlevé integrability test for ODEs and PDEs is implemented. The third program provides an algorithm to compute conserved densities for nonlinear evolution equations. The fourth software package aids in the computation of Lie symmetries of systems of differential and difference-differential equations. Several examples illustrate the capabilities of the software.Research supported in part by NSF under Grant CCR-9300978.     

A quaternion QR algorithm

Summary This paper extends the Francis QR algorithm to quaternion and antiquaternion matrices. It calculates a quaternion version of the Schur decomposition using quaternion unitary similarity transformations. Following a finite step reduction to a Hessenberg-like condensed form, a sequence of implicit QR steps reduces the matrix to triangular form. Eigenvalues may be read off the diagonal. Eigenvectors may be obtained from simple back substitutions. For serial computation, the algorithm uses only half the work and storage of the unstructured Francis QR iteration. By preserving quaternion structure, the algorithm calculates the eigenvalues of a nearby quaternion matrix despite rounding errors.