The extreme set condition of a graph

Let G be a simple graph. The size of any largest matching in G is called the matching number of G and is denoted by ν(G). Define the deficiency of G, def(G), by the equation def(G)=|V(G)|−2ν(G). A set of points X in G is called an extreme set if def(G−X)=def(G)+|X|. Let c₀(G) denote the number of the odd components of G. A set of points X in G is called a barrier if c₀(G−X)=def(G)+|X|. In this paper, we obtain the following:

(1) Let G be a simple graph containing an independent set of size i, where i2. If X is extreme in G for every independent set X of size i in G, then there exists a perfect matching in G.

(2) Let G be a connected simple graph containing an independent set of size i, where i2. Then X is extreme in G for every independent set X of size i in G if and only if G=(U,W) is a bipartite graph with |U|=|W|i, and |Γ(Y)||U|−i+m+1 for any Y U, |Y|=m (1mi−1).

(3) Let G be a connected simple graph containing an independent set of size i, where i2. Then X is a barrier in G for every independent set X of size i in G if and only if G=(U,W) is a bipartite graph with |U|=|W|=i, and |Γ(Y)|m+1 for any Y U, |Y|=m (1mi−1).     

The equivariant Serre spectral sequence as an application of a spectral sequence of Spanier

E.H. Spanier (1992) has constructed, for a cohomology theory defined on a triangulated space and locally constant on each open simplex, a spectral sequence whose E₂-term consists of certain simplicial cohomology groups, converging to the cohomology of the space. In this paper we study a closed G-fibration ƒ: Y → X, where G is a finite group. We show that if the base-G-spaceX is equivariantly triangulated and Y is paracompact, then Spanier's spectral sequence yields an equivariant Serre spectral sequence for ƒ. The main point here is to identify the equivariant singular cohomology groups of X with appropriate simplicial cohomology groups of the orbit space X/G.     

The smallest degree sum that yields potentially kCℓ-graphic sequences

Gould et al. (Combinatorics, Graph Theory and Algorithms, Vol. 1, 1999, pp. 387–400) considered a variation of the classical Turán-type extremal problems as follows: For a given graph H, determine the smallest even integer σ(H,n) such that every n-term graphic sequence π=(d₁,d₂,…,d_n) with term sum σ(π)=d₁+d₂++d_nσ(H,n) has a realization G containing H as a subgraph. In this paper, for given integers k and ℓ, ℓ7 and 3kℓ, we completely determine the smallest even integer σ(_kC_ℓ,n) such that each n-term graphic sequence π=(d₁,d₂,…,d_n) with term sum σ(π)=d₁+d₂++d_nσ(_kC_ℓ,n) has a realization G containing a cycle of length r for each r, krℓ.     

Estimating the spectral measure of an extreme value distribution

Let (X₁, Y₁), (X₂, Y₂),…, (X_n, Y_n) be a random sample from a bivariate distribution function F which is in the domain of attraction of a bivariate extreme value distribution function G. This G is characterized by the extreme value indices and its spectral measure or angular measure. The extreme value indices determine both the marginals and the spectral measure determines the dependence structure. In this paper, we construct an empirical measure, based on the sample, which is a consistent estimator of the spectral measure. We also show for positive extreme value indices the asymptotic normality of the estimator under a suitable 2nd order strengthening of the bivariate domain of attraction condition.     

The exponent of the primitive Cayley digraphs on finite Abelian groups

Let G be finite group and let S be a subset of G. We prove a necessary and sufficient condition for the Cayley digraph X_{(G, S)} to be primitive when S contains the central elements of G. As an immediate consequence we obtain that a Cayley digraph X_{(G, S)} on an Abelian group is primitive if and only if S^−1S is a generating set for G. Moreover, it is shown that if a Cayley digraph X_{(G, S)} on an Abelian group is primitive, then its exponent either is or is not exceeding . Finally, we also characterize those Cayley digraphs on Abelian groups with exponent . In particular, we generalize a number of well-known results for the primitive circulant matrices.     

Stable 2-pairs and (X,Y)-intersection graphs

Given two fixed graphs X and Y, the (X,Y)-intersection graph of a graph G is a graph where

1. each vertex corresponds to a distinct induced subgraph in G isomorphic to Y, and

2. two vertices are adjacent iff the intersection of their corresponding subgraphs contains an induced subgraph isomorphic to X.

This notion generalizes the classical concept of line graphs since the (K₁,K₂)-intersection graph of a graph G is precisely the line graph of G.

Let ( , respectively) denote the family of line graphs of bipartite graphs (bipartite multigraphs, respectively), and refer to a pair (X,Y) as a 2-pair if Y contains exactly two induced subgraphs isomorphic to X. Then and , respectively, are the smallest families amongst the families of (X,Y)-intersection graphs defined by so called hereditary 2-pairs and hereditary non-compact 2-pairs. Furthermore, they can be characterized through forbidden induced subgraphs. With this motivation, we investigate the properties of a 2-pair (X,Y) for which the family of (X,Y)-intersection graphs coincides with (or ). For this purpose, we introduce a notion of stability of a 2-pair and obtain the desired characterization for such stable 2-pairs. An interesting aspect of the characterization is that it is based on a graph determined by the structure of (X,Y).     

The consistency of a non-linear least squares estimator from diffusion processes

Consider the following Itô stochastic differential equation dX(t) = ƒ(θ⁰, X(t)) dt + dW(t), where (W(t), t 0), is a standard Wiener process in R^N. On the basis of discrete data 0 = t₀ < t₁ < …<t_n = T; X(t₁),...,X(t_n) we would like to estimate the parameter θ⁰. We shall define the least squares estimator and show that under some regularity conditions, is strongly consistent.     

Some algebraic constructions in rational homotopy theory

In this note we describe constructions in the category of differential graded commutative algebras over the rational numbers Q which are analogs of the space F(X, Y) of continuous maps of X to Y, the component F(X, Y,ƒ) containing ƒ ε F(X, Y), fibrations, induced fibrations, the space Γ(π) of sections of a fibration π: E → X, and the component Γ(π,σ) containing σ ε Γ (π). As a focus, we address the problem of expressing π^*(F(X, Y, ƒ)) = Hom(π_*(F(X,Y, ƒ)),Q) in terms of differential graded algebra models for X and Y.     

Degrevlex Gröbner bases of generic complete intersections

In this paper, we study the Hilbert–Samuel function of a generic standard graded K-algebra

K[X₁,…,X_n]/(g₁,…,g_m)

when refined by an (ℓ)-adic filtration, ℓ being a linear form. From this we obtain a structure theorem which describes the stairs of a generic complete intersection for the degree-reverse-lexicographic order. We show what this means for generic standard (or Gröbner) bases for this order; in particular, we consider an “orderly filling up” conjecture, and we propose a strategy for the standard basis algorithm which could be useful in generic-like cases.     

Strong equality of domination parameters in trees

We study the concept of strong equality of domination parameters. Let P₁ and P₂ be properties of vertex subsets of a graph, and assume that every subset of V(G) with property P₂ also has property P₁. Let ψ₁(G) and ψ₂(G), respectively, denote the minimum cardinalities of sets with properties P₁ and P₂, respectively. Then ψ₁(G)ψ₂(G). If ψ₁(G)=ψ₂(G) and every ψ₁(G)-set is also a ψ₂(G)-set, then we say ψ₁(G) strongly equals ψ₂(G), written ψ₁(G)≡ψ₂(G). We provide a constructive characterization of the trees T such that γ(T)≡i(T), where γ(T) and i(T) are the domination and independent domination numbers, respectively. A constructive characterization of the trees T for which γ(T)=γ_t(T), where γ_t(T) denotes the total domination number of T, is also presented.     

ℓ-homology of right-angled Coxeter groups based on barycentric subdivisions

Associated to any finite flag complex L there is a right-angled Coxeter group W_L and a contractible cubical complex Σ_L on which W_L acts properly and cocompactly, and such that the link of each vertex is L. It follows that if L is a triangulation of , then Σ_L is a contractible n-manifold. We establish vanishing (in a certain range) of the reduced ℓ²-homology of Σ_L in the case where L is the barycentric subdivision of a cellulation of a manifold. In particular, we prove the Singer Conjecture (on the vanishing of the reduced ℓ²-homology except in the middle dimension) in the case of Σ_L where L is the barycentric subdivision of a cellulation of , n=6,8.     

On a problem concerning ordered colourings

Let G be a connected graph with v(G) 2 vertices and independence number (G). G is critical if for any edge e of G:

1. (i) (G − e) > (G), if e is not a cut edge of G, and

2. (ii) v(G_i) − (G_i) < v(G) − (G), I = 1, 2, if e is a cut edge and G₁, G₂ are the two components of G − e.

Recently, Katchalski et al. (1995) conjectured that: if G is a connected critical graph, then with equality possible if and only if G is a tree. In this paper we establish this conjecture.     

ContributionsChromatic Ramsey numbers

Suppose G is a graph. The chromatic Ramsey number r_c(G) of G is the least integer m such that there exists a graph F of chromatic number m for which the following is true: for any 2-colouring of the edges of F there is a monochromatic subgraph isomorphic to G. Let M_n = min[r_c(G): χ(G) = n]. It was conjectured by Burr et al. (1976) that M_n = (n − 1)² + 1. This conjecture has been confirmed previously for n 4. In this paper, we shall prove that the conjecture is true for n = 5. We shall also improve the upper bounds for M₆ and M₇.     

Eulerian subgraphs containing given edges

For an integer l0, define to be the family of graphs such that if and only if for any edge subset XE(G) with |X|l, G has a spanning eulerian subgraph H with XE(H). The graphs in are known as supereulerian graphs. Let f(l) be the minimum value of k such that every k-edge-connected graph is in . Jaeger and Catlin independently proved f(0)=4. We shall determine f(l) for all values of l0. Another problem concerning the existence of eulerian subgraphs containing given edges is also discussed, and former results in [J. Graph Theory 1 (1977) 79–84] and [J. Graph Theory 3 (1979) 91–93] are extended.     

A two-sided estimate in the Hsu-Robbins-Erdös law of large numbers

Let X₁, X₂, … be independent identically distributed random variables. Then, Hsu and Robbins (1947) together with Erdös (1949, 1950) have proved that

,

if and only if E[X²₁] < ∞ and E[X₁] = 0. We prove that there are absolute constants C₁, C₂ (0, ∞) such that if X₁, X₂, … are independent identically distributed mean zero random variables, then

c₁λ⁻² E[X₁²·1_{|X1|λ}]S(λ)C₂λ⁻² E[X₁²·1_{|X1|λ}]

,

for every λ > 0.     

On Some Families of Smooth Affine Spherical Varieties of Full Rank

Let G be a complex connected reductive group. Losev has shown that a smooth affine spherical G-variety X is uniquely determined by its weight monoid, which is the set of irreducible representations of G that occur in the coordinate ring of X. In this paper we use a combinatorial characterization of the weight monoids of smooth affine spherical varieties to classify:(a) all such varieties for G = SL(2) × C~×and(b) all such varieties for G simple which have a G-saturated weight monoid of full rank. We also use the characterization and Knop's classification theorem for multiplicity free Hamiltonian manifolds to give a new proof of Woodward's result that every reflective Delzant polytope is the moment polytope of such a manifold.     

Polygamma functions of negative order

Liouville's fractional integration is used to define polygamma functions ψ⁽ⁿ⁾(Z) for negative integer n. It is shown that such ψ⁽ⁿ⁾(Z) can be represented in a closed form by means of the first derivatives of the Hurwitz Zeta function. Relations to the Barnes G-function and generalized Glaisher's constants are also discussed.     

On L(d,1)-labelings of graphs

Given a graph G and a positive integer d, an L(d,1)-labeling of G is a function f that assigns to each vertex of G a non-negative integer such that if two vertices u and v are adjacent, then |f(u)−f(v)|d; if u and v are not adjacent but there is a two-edge path between them, then |f(u)−f(v)|1. The L(d,1)-number of G, λ_d(G), is defined as the minimum m such that there is an L(d,1)-labeling f of G with f(V){0,1,2,…,m}. Motivated by the channel assignment problem introduced by Hale (Proc. IEEE 68 (1980) 1497–1514), the L(2,1)-labeling and the L(1,1)-labeling (as d=2 and 1, respectively) have been studied extensively in the past decade. This article extends the study to all positive integers d. We prove that λ_d(G)Δ²+(d−1)Δ for any graph G with maximum degree Δ. Different lower and upper bounds of λ_d(G) for some families of graphs including trees and chordal graphs are presented. In particular, we show that the lower and the upper bounds for trees are both attainable, and the upper bound for chordal graphs can be improved for several subclasses of chordal graphs.     

All trees are 1-embeddable and all except stars are 2-embeddable

A graph G with n vertices is said to be embeddable (in its complement) if there is an automorphism φ of K_n such that E(G) ∩ E(φ(G))=. It is known that all trees T with n (≥2) vertices and T K_1,n−1 are embeddable. We say that G is 1-embeddable if, for every edge e, there is an automorphism φ of K_n such that E(G) ∩ E(φ(G))={e};and that it is 2-embeddable if,for every pair e₁, e₂ of edges, there is an automorphism φ of K_n such that E(G) ∩ E(φ(G))={e₁, e₂}. We prove here that all trees with n (3) vertices are 1-embeddable; and that all trees T with n (4) vertices and T K_1,n−1 are 2-embeddable. In a certain sense, this result is sharp.