Connected and alternating vectors: Polyhedra and algorithms

Given a graphG = (V, E), leta ^S, S L, be the edge set incidence vectors of its nontrivial connected subgraphs.The extreme points of = {x R ^E: a^sx |V(S)| - |S|, S L} are shown to be integer 0/± 1 and characterized. They are the alternating vectorsb ^k, k K, ofG. WhenG is a tree, the extreme points ofB 0,b ^kx 1,k K} are shown to be the connected vectors ofG together with the origin. For the four LP's associated with andA, good algorithms are given and total dual integrality of andA proven.On leave from Swiss Federal Institute of Technology, Zurich.     

Kite-freeP- andQ-polynomial schemes

LetY = (X, {R _i } _oid) denote aP-polynomial association scheme. By a kite of lengthi (2 i d) inY, we mean a 4-tuplexyzu (x, y, z, u X) such that(x, y) R ₁,(x, z) R ₁,(y, z) R ₁,(u, y) R _i–1,(u, z) R _i–1,(u, x) R _i. Our main result in this paper is the following.     

Mixing and some integro-functional equations

Summary It is proved that the operatorP: L ¹ (0, ) L ¹(0, ), given byPg(z) = _z/c [g(x)/cx]dx, is completely mixing, i.e.,P ⁿ g ₁ 0 forg L ¹(0, ) with g dx = 0. This implies that, forc (0, 1), each continuous and bounded solution of the equationf(x)= ₀ ^cx f(t)dt/(cx) (x (0, 1]) is constant.     

Number of no nisomorphic subgraphs in an n-point graph

LetG(n) be the set of all nonoriented graphs with n enumerated points without loops or multiple lines, and let v_k(G) be the number of mutually nonisomorphic k-point subgraphs of G G(n). It is proved that at least |G(n)| (1–1/n) graphs G G(n) possess the following properties: a) for any k [6log₂n], where c=–c log₂c–(1–c)×log₂(1–c) and c>1/2, we havev _k(G) > C _n ^k (1–1/n²); b) for any k [cn + 5 log₂n] we havev _k(G) = C _n ^k . Hence almost all graphs G G(n) containv(G) 2ⁿ pairwise nonisomorphic subgraphs.Translated from Matematicheskie Zametki, Vol. 9, No. 3, pp. 263–273, March, 1971.     

Local Recognition Of Non-Incident Point-Hyperplane Graphs

Let be a projective space. By H() we denote the graph whose vertices are the non-incident point-hyperplane pairs of , two vertices (p,H) and (q,I) being adjacent if and only if p I and q H. In this paper we give a characterization of the graph H() (as well as of some related graphs) by its local structure. We apply this result by two characterizations of groups G with PSL _n ( )GPGL _n ( ), by properties of centralizers of some (generalized) reflections. Here is the (skew) field of coordinates of .     

Über eine Verallgemeinerung der Nicoletti-Aufgabe für Funktional-Differentialgleichungen mit voreilendem Argument

We consider a functional differential equation (1) (t)=F(t,) fort[0,+) together with a generalized Nicoletti condition (2)H()=. The functionF: [0,+)×C ⁰[0,+)B is given (whereB denotes the Banach space) and the value ofF (t, ) may depend on the values of (t) fort[0,+);H: C ⁰[0,+)B is a given linear operator and B. Under suitable assumptions we show that when the solution :[0,+)B satisfies a certain growth condition, then there exists exactly one solution of the problem (1), (2).     

Aufeinanderfolgende Elemente in multiplikativen Zahlenmengen

LetM be a multiplicative set with 1M andmnM if and only ifmM,nM for (m,n)=1. It is shown by elementary means that there exists the asymptotic density of the setM(M–1) for every multiplicative setM. The density is positive if and only ifM possesses a positive density and 2M for some . This result is slightly generalized to sums over multiplicative functionsf with |f|1.     

Critical star multigraphs

A star-multigraphG is a multigraph in which there is a vertexv ⁺ which is incident with each non-simple edge. It is critical if it is connected, Class 2 and(G\e) < (G) for eache E(G). We show that, ifG is any star multigraph, then(G) (G) + 1. We investigate the edge-chromatic class of star multigraphs with at most two vertices of maximum degree. We also obtain a number of results on critical star multigraphs. We shall make use of these results in later papers.     

Quadratically constrained quadratic programming: Some applications and a method for solution

The problem (QPQR) considered here is: minimizeQ ₁ (x) subject toQ _i (x) 0,i M ₁ {2,...,m},x P R ⁿ, whereQ _i (x), i M {1} M ₁ are quadratic forms with positive semi-definite matrices, andP a compact nonempty polyhedron of Rⁿ. Applications of (QPQR) and a new method to solve it are presented.Letu S={u R ^m;u 0, u _i= l}be fixed;then the problem:iM minimize u _iQ_i (x (u)) overP, always has an optimal solutionx (u), which is either feasible, iM i.e. u C₁ {u S;Q _i (x (u)) 0,i M ₁} or unfeasible, i.e. there exists ani M ₁ withu C {u S; Q_i(x(u)) 0}.Let us defineC _i C_i S _i withS _i {u S; u _i=0}, i M. A constructive method is used to prove that C _i is not empty and thatx (û) withiM û C _i characterizes an optimal solution to (QPQR). Quite attractive numerical results have been reached with this method.

---

Zusammenfassung Die vorliegende Arbeit befaßt sich mit Anwendungen und einer neuen Lösungsmethode der folgenden Aufgabe (QPQR): man minimiere eine konvexe quadratische ZielfunktionQ _i (x) unter Berücksichtigung konvexer quadratischer RestriktionenQ _i (x) 0, iM ₁ {2,...,m}, und/oder linearer Restriktionen.·Für ein festesu S {u R ^m;u 0, u _i=1},M {1} M₁ besitzt das Problem:iM minimiere die konvexe quadratische Zielfunktion u _i Q_i (x (u)) über dem durch die lineareniM Restriktionen von (QPQR) erzeugten, kompakten und nicht leeren PolyederP R ⁿ, immer eine Optimallösungx (u), die entweder zulässig ist: u C₁ {u S;Q ₁ (x (u)) 0,i M ₁} oder unzulässig ist, d.h. es existiert eini M ₁ mitu C_i {u S;Q _i (x(u))0}.Es seien folgende MengenC _i C_i S _i definiert, mitS _i {u S;u _i=0}, i M. Es wird konstruktiv bewiesen, daß C _i 0 undx (û) mitû C _i eine Optimallösung voniM iM (QPQR) ist; damit ergibt sich eine Methode zur Lösung von (QPQR), die sich als sehr effizient erwiesen hat. Ein einfaches Beispiel ist angegeben, mit dem alle Schritte des Algorithmus und dessen Arbeitsweise graphisch dargestellt werden können.

---

---

An earlier version of this paper was written during the author's stay at the Institute for Operations Research, Swiss Federal Institute of Technology, Zürich.     

Reconstructing dimensions of intersections of convex sets

Denoting by dimA the dimension of the affine hull of the setA, we prove that if {K _i:i T} and {K _i ^j :i T} are two finite families of convex sets inR ⁿ and if dim {K _i :i S} = dim {K _i ^j :i S}for eachS T such that|S| n + 1 then dim {K _i :i T} = dim {K _i : {i T}}.     

On signpost systems and connected graphs

By a signpost system we mean an ordered pair (W, P), where W is a finite nonempty set, P W × W × W and the following statements hold: if (u, v, w) P, then (v, u, u) P and (v, u, w) P, for all u, v, w W; if u v; then there exists r W such that (u, r, v) P, for all u, v W. We say that a signpost system (W, P) is smooth if the folowing statement holds for all u, v, x, y, z W: if (u, v, x), (u, v, z), (x, y, z) P, then (u, v, y) P. We say thay a signpost system (W, P) is simple if the following statement holds for all u, v, x, y W: if (u, v, x), (x, y, v) P, then (u, v, y), (x, y, u) P.By the underlying graph of a signpost system (W, P) we mean the graph G with V(G) = W and such that the following statement holds for all distinct u, v W: u and v are adjacent in G if and only if (u, v, v) P. The main result of this paper is as follows: If G is a graph, then the following three statements are equivalent: G is connected; G is the underlying graph of a simple smooth signpost system; G is the underlying graph of a smooth signpost system.Research was supported by Grant Agency of the Czech Republic, grant No. 401/01/0218.     

Zur Vollständigkeit der Induktiven Gruppoide der Partiellen Automorphismen von Algebren

For any algebraA let(A) be the set of partial automorphisms (isomorphisms between subalgebras). With the natural multiplication it is an inductive groupoid in the sense of Ehresmann.(A) is complete iff every subset of(A) which is compatible with the semi-ordering has an upper bound. The fact, whether(A) is complete or not, depends on the defining operations ofA. For every direct familyF = (, (A ) ,()_, , of algebras such that all ,, with are one-to-one functions, the direct limit is complete iff all(A) are complete. We give some theorems on the decomposition of inductive groupoids, and employ them in proving the completeness of(A) to variousA.In particular, we obtain that, in case whenG is a finite group,(G) is complete iffG is either cyclic or direct product of a noncyclic group of order 4 and a cyclic group of odd order. For finite acyclic ringsR and finite fieldsK the inductive groupoids(R) and(K) are complete.Further we deal with the question, to what extent algebras are determined by their inductive groupoids. (An algebraA of a classS is defined by(A) iff, for any algebraB of the classS, isomorphism between(A) and(B) implies isomorphism betweenA andB.) Particular attention is paid to finite groups. In general, algebras of classesS are not defined within the classS by their inductive groupoids.

     

Irreducible representations of Lie algebras of reductive groups and the Kac-Weisfeiler conjecture

Letg be the Lie algebra of a connected reductive groupG over an algebraically closed field of characteristicp>0. Suppose thatG ⁽¹⁾ is simply connected andp is good for the root system ofG. Ifp=2, suppose in addition thatg admits a nondegenerateG-invariant trace form. LetV be an irreducible and faithfulg-module withp-character g ^*. It is proved in the paper that dimV is divisible byp ^1/2dim() where () stands for the orbit of under the coadjoint action ofG.Oblatum 14-III-1994 & 17-XI-1994     

Posterior Sensitivity to the Sampling Distribution and the Prior: More than One Observation

Sensitivity of a posterior quantity (f, P) to the choice of the sampling distribution f and prior P is considered. Sensitivity is measured by the range of (f, P) when f and P vary in nonparametric classes ^f and ^P respectively. Direct and iterative methods are described which obtain the range of (f, P) over f ^f when prior P is fixed, and also the overall range over f ^f and P ^P . When multiple i.i.d. observations X ₁,...,X _k are observed from f, the posterior quantity (f, P) is not a ratio-linear function of f. A method of steepest descent is proposed to obtain the range of (f, P). Several examples illustrate applications of these methods.     

Nonparametric Inference for a Class of Stochastic Partial Differential Equations II

Consider the stochastic partial differential equationdu (t,x) = (t)u (t, x)dt + dW _Q(t,x), 0 t T where = ₂/x ₂, and is a class of positive valued functions. We obtain an estimator for the linear multiplier (t) and establish the consistency, rate of convergence and asymptotic normality of this estimator as 0.     

Analytic Approximations for a Singularly Perturbed Convection—Diffusion Problem with Discontinuous Data in a Half-Infinite Strip

We consider a singularly perturbed convection—diffusion equation, –u+v u=0, defined on a half-infinite strip, (x,y)(0,)×(0,1) with a discontinuous Dirichlet boundary condition: u(x,0)=1, u(x,1)=u(0,y)=0. Asymptotic expansions of the solution are obtained from an integral representation in two limits: (a) as the singular parameter 0⁺ (with fixed distance r to the discontinuity point of the boundary condition) and (b) as that distance r0⁺ (with fixed ). It is shown that the first term of the expansion at =0 contains an error function or a combination of error functions. This term characterizes the effect of discontinuities on the -behavior of the solution and its derivatives in the boundary or internal layers. On the other hand, near the point of discontinuity of the boundary condition, the solution u(x,y) is approximated by a linear function of the polar angle at the point of discontinuity (0,0).     

The Adjoints of Dilation Operators on H-Cones

If S is an H-cone and P:SS is a localizable dilation operator on S (i.e., P is additive increasing, contractive, continuous in order from below and s(Ps+t–Pt+Pf)S, s,tS,f(S–S)₊), then it is proved that its adjoint P ^*:S ^*S ^* (i.e., P ^*=P) is also a localizable dilation operator. This is an improvement of a result obtained by G. Mokobodzki in the frame of excessive functions.     

Einschließungsaussagen für gewöhnliche Differentialoperatoren

Summary For differential operatorsM of second order (as defined in (1.1)) we describe a method to prove Range-Domain implications—Mu–u and an algorithm to construct these functions , , , . This method has been especially developed for application to non-inverse-positive differential operators. For example, for non-negativea ₂ and for given functions = we require =C ₀[0, 1] C ₂([0, 1]–T) whereT is some finite set), (M) (t)(t), (t[0, 1]–T) and certain additional conditions for eachtT. Such Range-Domain implications can be used to obtain a numerical error estimation for the solution of a boundary value problemMu=r; further, we use them to guarantee the existence of a solution of nonlinear boundary value problems between the bounds- and .     

On a Property of Subexponential Distributions

Let F be a distribution function (d.f.) on [0, ) with finite first moment m >0. We define the integrated tail distribution function F ₁ of F by F ₁(t)=m^-1 ₀ ^t (1- F(u))du, t0. In this paper, we obtain sufficient conditions under which implications FSF ₁S and F ₁S FS hold, where S is the class of subexponential distributions.     

Sugli insiemi di permutazioni strettamente k-transitivi (k ≥ 3)

Summary Let G be a sharply 3-transitive permutation set on a finite set E of even cardinality and let 1 be in G. The following theorems are proved. G is one of the known examples if and only if there exists a non-identity normal subgroup N of G and an element of E such that NG G.G is a group if and only if G for every G and for every G and for every G .By using the classification of finite single groups a result concerning sharply k-transitive permutation sets k>3 is also proved.

---

---

Dedicato a Guido Zappa in occasione del suo 70° compleanno

---

Lavoro eseguito nell'ambito dei progetti finanziati dal Ministero della Pubblica Istruzione.