On total matching numbers and total covering numbers of complementary graphs

Best upper and lower bounds, as functions of n, are obtained for the quantities $\text{β}{}_2\text{(G)+β}{}_2\text{(}\text{G}\text{?}\text{)}$ and $\text{α}{}_2\text{(G)+α}{}_2\text{(}\text{G}\text{?}\text{)}$, where β₂(G) denotes the total matching number and α₂(G) the total covering number of any graph G with n vertices and with complementry graph ?.The best upper bound is obtained also for α₂(G)+β₂(G), when G is a connected graph.     

Some Ramsey numbers for directed graphs

Given k directed graphs G₁,…,G_k the Ramsey number R(G₁,…, G_k) is the smallest integer n such that for any partition (U₁,…,U_k) of the arcs of the complete symmetric directed graph K_n, there exists an integer i such that the partial graph generated by U₁ contains G₁ as a subgraph. In the article we give a necessary and sufficient condition for the existence of Ramsey numbers, and, when they exist an upper bound function. We also give exact values for some classes of graphs. Our main result is: $\text{R(}\text{P}{}_{\mathrm{n}}\text{,….}\text{P}{}_{\mathrm{nk-1}}\text{, G) = n}{}_1\text{…n}{}_{\mathrm{k-1}}\text{(p-1) + 1}$, where G is a hamltonian directed graph with p vertices and $\text{P}{}_{\mathrm{n}}{}_{\mathrm{i}}$ denotes the directed path of length n_t     

A characterization of planar cubic graphs

If S is a collection of circuits in a graph G, the circuits in S are said to be consistently orientable if G can be oriented so that they are all directed circuits. If S is a set of three or more consistently orientable circuits such that no edge of G belongs to more than two circuits of S, then S is called a ring if there exists a cyclic ordering C₀, C₁,…, C_{n ? 1}, C₀ of the n circuits in S such that $\text{EC}{}_{\mathrm{i}}\text{? EC}{}_{\mathrm{j}}\text{≠ ?}$ if and only if j = i or j ≡ i ? 1 (mod n) or j ≡ i + 1 (mod n). We characterise planar cubic graphs in terms of the non-existence of a ring with certain specified properties.     

The cochromatic index of a graph

We discuss partitions of the edge set of a graph into subsets which are uniform in their internal relationships; i.e., the edges are independent, they are incident with a common vertex (a star), or three edges meet in a triangle. We define the cochromatic index z′(G) of G to be the minimum number of subsets into which the edge set of G can be partitioned so that the edges in any subset are either mutually adjacent or independent.Several bounds for z′(G) are discussed. For example, it is shown that δ(G) - 1 ? z′(G)? Δ(G) + 1, with the lower bound being attained only for a complete graph. Here δ(G) and Δ(G) denote the minimum and maximum degrees of G, respectively. The cochromatic index is also found for complete n-partite graphs.Given a graph G define a sequence of graphs G₀, G₁,…, G_k, with G₀=G and

, with k being the first value of i for which G_i is regular. Let φ_i(G) = |V(G) – V(G_i| + Δ (G_i) and setφ(G) = min_0?i?kφ_i(G). We show that φ(G) ? 1 ?z′(G)?φ(G) + 1. We then s that a graph G is of class A, B or C, if z′(G) = φ(G) ? 1, φ(G), orφ(G) + 1, respectively. Examples of graphs of each class are presented; in particular, it is shown that any bipartite graph belongs to class B.Finally, we show that if a, b and c are positive integers with a?b?c + 1 and a?c, then unless a = c = b - 1 = 1, there exists a graph G having δ(G) = a, Δ(G) =c, and z′(G) = b.     

Vertex degrees of planar graphs

Let G be a planar graph having n vertices with vertex degrees d₁, d₂,…,d_n. It is shown that $\text{Σ}{}_{\mathrm{i=1}}{}^{\mathrm{n}}\text{d}{}_{\mathrm{i}}{}^2\text{≤ 2n}{}^2\text{+ O(n)}$. The main term in this upper bound is best possible.     

Acyclic orientations of a graph and chromatic and independence numbers

The determinations of chromatic and independence numbers of a graph are represented as problems in optimization over the set of acyclic orientations of the graph. Specifically $\text{χ =}\text{min}{}_{\mathrm{\omega \in \Omega }}\text{k}{}_{\mathrm{\omega }}$ and $\text{β}{}_0\text{=}\text{max}{}_{\mathrm{\omega \in \Omega }}\text{k}{}_{\mathrm{\omega }}$ where χ is the chromatic number, β₀ is the independence number, Ω is the set of acyclic orientations, l_ω is the length of a maximum chain, and k_ω is the cardinality of a minimum chain decomposition. It is shown that Dilworth's theorem is a special case of the second equality.     

Permutation-operator inequalities on certain symmetry classes of tensors

If A∈T(m, N), the real-valued N-linear functions on E_m, and σ∈S_N, the symmetric group on {…,N}, then we define the permutation operator P_σ: T(m, N) → T(m, N) such that P_σ(A)(x₁,x₂,…,x_N = A(x_σ(1),x_σ(2),…, x_σ(N)). Suppose Σ^q_i=1n_i = N, where the n_i are positive integers. In this paper we present a condition on σ that is sufficient to guarantee that 〈P_σ(A₁?A₂???A_q),A₁?A₂?? ? A_q〉 ? 0 for A_i∈S(m, n_i), where S(m, n_i) denotes the subspace of T(m, n_i) consisting of all the fully symmetric members of T(m, n_i). Also we present a broad generalization of the Neuberger identity which is sometimes useful in answering questions of the type described below. Suppose G and H are subgroups of S_N. We let T_G(m, N) denote all A∈T(m, N) such that P_σ(A) = A for all σ∈G. We define the symmetrizer $\text{S}$_G: T(m, N)→T_G(m,N) such that $\text{S}{}_{\mathrm{G}}\text{(A) = 1/|G|Σ}{}_{\mathrm{\sigma \in G}}\text{P}{}_{\mathrm{\sigma }}\text{(A)}$. Suppose H is a subgroup of G and A∈T_H(m, N). Clearly $\text{6}\text{S}{}_{\mathrm{<mtext>G</mtext>}}\text{6(A) 6? 6A6.}$ We are interested in the reverse type of comparison. In particular, if D is a suitably chosen subset of T_H(m,N), then can we explicitly present a constant C>0 such that $\text{6}\text{S}{}_{\mathrm{G}}\text{(A)6?C6A6}$ for all A∈D?     

Bounds on path connectivity

The path-connectivity of a graph G is the maximal k for which between any k pairs of vertices there are k edge-disjoint paths (one between each pair). An upper bound for the path-connectivity of n^q(q<1) separable graphs [6] is shown to exist.If the edge-connectivity of a graph is K_E then between any two pairs of vertices and for every $\text{t?}\text{K}{}_{\mathrm{E}}$ there exists a t?t′?t+1 such that there are t′ paths between the first pair and $\text{K}{}_{\mathrm{E}}\text{?t′}$ between the second pair. All paths are edge-disjoint.     

Test solutions of porous media problems

Laminar isothermal fluid flow of two immiscible compressible fluid phases in a porous medium is formulated in terms of four unknown functions ?₁, ?₂, S₁ and S₂ in a pair of partial differential equations, $\text{(}\text{?}\text{?t}\text{)[φ(x, t)S}{}_{\mathrm{i}}\text{?}{}_{\mathrm{i}}\text{] = (}\text{?}\text{?x}\text{){κ(x, t) σ}{}_{\mathrm{i}}\text{(S}{}_{\mathrm{i}}\text{)(}\text{?}\text{?x}\text{)[Φ}{}_{\mathrm{i}}\text{(?}{}_{\mathrm{i}}\text{)]}}$, and a pair of auxiliary relations, S₁ = Γ₁(?₁, ?₂) and S₂ = 1 ? S₁. This system is studied in terms of solutions which are constant along curves, viz., horizontal lines, vertical lines, and parabolas relevant to the parabolic nature of each of the partial differential equations in the system. Such solutions are described, although subject to solution of ordinary differential equations, for use in testing either numerical methods or proposed theorems for the original larger problem.     

Arithmetic in generalized Artin-Schreier extensions of k(x)

If k is a perfect field of characteristic p ≠ 0 and k(x) is the rational function field over k, it is possible to construct cyclic extensions K_n over k(x) such that [K : k(x)] = pⁿ using the concept of Witt vectors. This is accomplished in the following way; if [β₁, β₂,…, β_n] is a Witt vector over k(x) = K₀, then the Witt equation $\text{y}{}^{\mathrm{p}}\text{?}\text{y}\text{= β}$ generates a tower of extensions through $\text{K}{}_{\mathrm{i}}\text{= K}{}_{\mathrm{i?1}}\text{(}\text{y}{}_{\mathrm{i}}\text{)}$ where $\text{y}\text{= [}\text{y}{}_1\text{,}\text{y}{}_2\text{,…,}\text{y}{}_{\mathrm{n}}\text{]}$. In this paper, it is shown that there exists an alternate method of generating this tower which lends itself better for further constructions in K_n. This alternate generation has the form K_i = K_i?1(y_i); y_i^p ? y_i = B_i, where, as a divisor in K_i?1, B_i has the form . In this form q is prime to Πp_j^λ_j and each λ_j is positive and prime to p. As an application of this, the alternate generation is used to construct a lower-triangular form of the Hasse-Witt matrix of such a field K_n over an algebraically closed field of constants.     

Spectra of Cayley graphs

By a result of L. Lovász, the determination of the spectrum of any graph with transitive automorphism group easily reduces to that of some Cayley graph.We derive an expression for the spectrum of the Cayley graph X(G,H) in terms of irreducible characters of the group G:

for any natural number t, where ξ_i is an irreducible character (over $\text{C}$), of degree n_i , and λ_i,1 ,…, λ_i,ni are eigenvalues of X(G, H), each one n_i times. (σn_i² = n = | G | is the total'number of eigenvalues.) Using this formula for t = 1,…, n_i one can obtain a polynomial of degree n_i whose roots are λ_i,1,…,λ_i,ni. The results are formulated for directed graphs with colored edges. We apply the results to dihedral groups and prove the existence of k nonisomorphic Cayley graphs of D_p with the same spectrum provided p > 64k, prime.     

Existence of stable equilibrium point for dynamical systems of Volterra type

This paper presents sufficient conditions for the existence of a nonnegative and stable equilibrium point of a dynamical system of Volterra type, (1) $\text{(}\text{d}\text{dt}\text{) x}{}_{\mathrm{i}}\text{(t) = ?x}{}_{\mathrm{i}}\text{(t)[f}{}_{\mathrm{i}}\text{(x}{}_1\text{(t),…, x}{}_{\mathrm{n}}\text{(t)) ? q}{}_{\mathrm{i}}\text{], i = 1,…, n}$, for every q = (q₁,…, q_n)^T?Rⁿ. Results of a nonlinear complementarity problem are applied to obtain the conditions. System (1) has a nonnegative and stable equilibrium point if (i) f(x) = (f₁(x),…,f_n(x))^T is a continuous and differentiable M-function and it satisfies a certain surjectivity property, or (ii), f(x) is continuous and strongly monotone on R₊₀ⁿ.     

On the simulation of shot noise and some other random variables

It is shown that the random voltage V_t resulting from pulses with independent random amplitude Y_i Poisson arrivals, and exponential decay, can be asymptotically represented, in the stationary case, by the following random variable; namely a sum of products of random variables:

$\text{W=}\text{∑}\text{i=1}\text{∞}\text{U}{}_{\mathrm{i}}\text{Y}{}_{\mathrm{i}}\text{,}$

where

$\text{U}{}_{\mathrm{i}}\text{=}\text{∏}\text{j=1}\text{i}\text{X}{}_{\mathrm{j}}{}^{\mathrm{\beta /\lambda }}\text{.}$

Here X_j are independent uniform random variables, β>0 is the decay parameter, λ>0 is the rate of the Poisson process.     

Measuring flatness in linear spaces

Let L be a finite-dimensional normed linear space and let M be a compact subset of L lying on one side of a hyperplane through 0. A measure of flatness for M is the number $\text{D(M) =}\text{inf}\text{{}\text{sup}\text{f(x)}\text{f(y)}\text{: x, y ? M}}$, where the infimum is over all f in $\text{L}{}^1$ which are positive on M. Thus D(M) = 1 if M is flat, but otherwise D(M) > 1. On the other hand, let E(M) be a second measure on M defined as follows: If M is linearly independent, E(M) = 1. If M is linearly dependent, then (1) let Z be a minimal, linearly dependent subset of M; (2) partition Z into mutually exclusive subsets U = {u₁, …, u_p} and V = {v₁, …, v_q} such that there exist positive coefficients a_i and b_i for which Σ_{i = 1}^pa_iu_i = Σ_{i = 1}^qb_iv_i; (3) let $\text{r =}\text{max}\text{{}\text{Σ}{}_{\mathrm{i\; =\; 1}}{}^{\mathrm{p}}\text{a}{}_{\mathrm{i}}\text{Σ}{}_{\mathrm{i\; =\; 1}}{}^{\mathrm{q}}\text{b}{}_{\mathrm{i}}\text{,}\text{Σ}{}_{\mathrm{i\; =\; 1}}{}^{\mathrm{p}}\text{b}{}_{\mathrm{i}}\text{Σ}{}_{\mathrm{i\; =\; 1}}{}^{\mathrm{q}}\text{a}{}_{\mathrm{i}}\text{}}$; (4) let E(M) be the supremum of all ratios r which can be formed by steps (1), (2) and (3). The main result of this paper is that these two measures are the same: D(M) = E(M). This result is then used to obtain results concerning the Banach distance-coefficient between an arbitrary finite-dimensional normed linear space and Hilbert space.     

On minimally subspace-comparable F-spaces

An F-space (complete metric linear space) is minimal if it admits no strictly weaker linear Hausdorff topology, and quotient (q-) minimal if all of its Hausdorff quotients are minimal. Two F-spaces are (q-minimally) minimally s-comparable if they have no isomorphic (q-) nonminimal closed linear subspaces. It is proved that if X, Y are (q-minimally (resp., minimally) s-comparable F-subspaces of an arbitrary topological linear space E (resp., with X ∩ Y = {0}), then X + Y is an F-subspace of E. Also, if X₁,…, X_n are F-subspaces of E, then X₁ + ··· + X_n is an F-subspace of E, provided that $\text{X}{}_{\mathrm{i}}\text{F}\text{and}\text{X}{}_{\mathrm{j}}\text{G}$ are minimally s-comparable whenever F and G are closed minimal subspaces of X_i and X_j, i ≠ j. These are analogs of some results due to Gurariǐ and Rosenthal concerning totally incomparable Banach spaces.     

On moment conditions for normed sums of independent variables and martingale differences

Let X₁, X₂,… be a sequence of i.i.d. random variables and S_n their partial sums. Necessary and sufficient conditions are given for $\text{{n}{}^{\mathrm{<mtext>?1</mtext><mtext>q</mtext>}}\text{S}{}_{\mathrm{n}}\text{}}{}^{\mathrm{\propto }}{}_1$ to have uniformly bounded pth moments, 0<p<q?2.Some of the results are generalized to martingle differences.     

On a problem of C. C. Chen and D. E. Daykin

Let α(k, p, h) be the maximum number of vertices a complete edge-colored graph may have with no color appearing more than k times at any vertex and not containing a complete subgraph on p vertices with no color appearing more than h times at any vertex. We prove that $\text{α(k, p, h) ≤ h + 1 + (k ? 1){(p ? h ? 1) × (h}{}^{\mathrm{p}}\text{+ 1)}}{}^{\mathrm{<mtext>1</mtext><mtext>h</mtext>}}$ and obtain a stronger upper bound for α(k, 3, 1). Further, we prove that a complete edge-colored graph with n vertices contains a complete subgraph on p vertices in which no two edges have the same color if

$\text{(}\text{n}\text{3}\text{)>(}\text{p}\text{3}\text{)}\text{Σ}\text{i=1}\text{t}\text{(}\text{e}{}_{\mathrm{i}}\text{2}\text{)}$

where e_i is the number of edges of color i, 1 ≤ i ≤ t.     

Unbounded operators: Perturbations and commutativity problems

Let H be a complex Hilbert space, and let G_i, i = 1, 2, be closed and orthogonal subspaces of the product space H × H. The subspace G = G₁ ⊕ G₂ is called a (graph) perturbation. We give conditions for invariance of regular operators (R.O.) under graph perturbations: When is the perturbation of a R.O. again a R.O.? If N is a Hilbert space we consider R.O. (i.e., densely defined and closed operators T) in H=$\text{L}$(N) such that G(T)=G(S)⊕V$\text{H}$(M, where G denotes the graph, S is a decomposable operator in H, V a decomposable partial isometry such that the initial space of V(t) is equal to M a.e. t, and finally $\text{H}$(M) is the Hardy space of analytic $\text{L}$₂ vector functions with values in M ? N × N. Such operators T commute with the bilateral shift U; but, unless M = 0, T does not commute with $\text{U}{}^1$. Conversely, this is a canonical model for all R.O. with said commutativity properties. Moreover, the model is unique when T is given, and M = G(w) where w is a partial isometry in N. The detailed structure of the model is analyzed in the special case where dim N = dim M = 1. We relate the problem to a condition of Szeg? by showing that T is a $\text{R.O. iff}\text{∝}{}_0{}^{\mathrm{2\pi }}\text{log}\text{¦ V}{}_2\text{(t)¦ dt = ?∞,}\text{where}\text{V = (V}{}_1\text{, V}{}_2\text{)}$ is the partial isometry in the special case of dimension one. Szeg?'s conditions enters in a different way in the analysis of the case M = N × N, as well as in the spectral analysis of T. Our results provide an answer to a commutativity problem posed by Fuglede. If T is an arbitrary densely defined operator, and A?B(H) is normal, we prove two theorems stating conditions for the implication $\text{A}{}_{\mathrm{\cup }}\text{T ? A}{}_{\mathrm{\cup }}{}^1\text{T}$. These conditions cannot generally be relaxed.     

On maximum principles for a class of nonlinear second-order elliptic equations

In a recent paper [3] the authors derived maximum principles which involved $\text{u(x)}\text{and}\text{q = ¦}\text{grad}\text{u¦}$, where u(x) is a classical solution of an alliptic differential equation of the form ($\text{g(q}{}^2\text{)u}{}_{\mathrm{,i}}\text{)}{}_{\mathrm{,i}}\text{+ ?(u) ?(q}{}^2\text{) = 0}$. In this paper these results are extended to the more general case in which $\text{g = g(u, q}{}^2\text{)}\text{and}\text{?(u) ?(q}{}^2\text{)}$ is replaced by h(u, q²).     

Best pseudo-isolated Gerschgorin disks for Eigenvalues

Let A be an arbitrary n×n matrix, partitioned so that if A=[A_ij], then all submatrices A_ii are square. If x is a positive vector, it is well-known that $\text{G(}\text{x}\text{) =∪}{}^{\mathrm{N}}{}_{\mathrm{i=1}}\text{G}{}_{\mathrm{i}}\text{(}\text{x}\text{)}$, where

$\text{G}{}_{\mathrm{i}}\text{(}\text{x}\text{) =}\text{z}\text{6(zI ? A}{}_{\mathrm{ii}}\text{)}{}^{\mathrm{?1}}\text{6}{}^{\mathrm{?1}}\text{?}\text{1}\text{x}{}_{\mathrm{i}}\text{∑}\text{j = 1}\text{j ≠ i}\text{N}\text{`6A}{}_{\mathrm{ij}}\text{6x}{}_{\mathrm{j}}$

, contains all the eigenvalues of A. The purpose of this paper is to give a new definition of the concept of an isolated subregion of G(x). An algorithm is given for obtaining the best such isolated subregion in a certain sense, and examples are given to show that tighter bounds for some eigenvalues of A may be obtained than with previous algorithms. For ease of computation, each subregion G_i(x) is replaced by the union of circular disks centered at the eigenvalues of A_ii.