Spectral Characterizations of the Lovász Number and the Delsarte Number of a Graph

This paper gives spectral characterizations of two closely related graph functions: the Lovász number and a generalization ¹ of Delsarte's linear programming bound. There are many known characterizations of the Lovász number , and each one corresponds to a similar characterization of ¹ obtained by extremizing over a larger or smaller class of objects.The spectral characterizations of and ¹ given here involve the largest eigenvalue of a type of weighted Laplacian that Fan Chung introduced.     

Fuzzy (Θ, S)-continuity and fuzzy (Θ, S)-closed graphs

The concept of (,s)-continuity [6] is considered and studied in fuzzy setting. It is seen that althought it is independent with each of the concepts of fuzzy continuity [2], fuzzy -continuity [10], fuzzy almost continuity [1] and fuzzy semicontinuity [1]; it implies fuzzy weak continuity [1], but the converse may not be true. The image of a compact fts [2] under a fuzzy (,s)-continuous surjective function isS-closed [5]. Finally the concepts of fuzzy (,s)-closed graphs, fuzzy (,s)-T ₂ spaces and fuzzy Urysohn spaces are introduced and mainly their connections with fuzzy (,s)-continuity are studied.     

Symmetriegerechte Basisvektoren für Permutationsdarstellungen aller endlichen Punktgruppen der Dimensionen 3 und 2

Zusammenfassung Es seiG eine endliche Untergruppe der orthogonalen Gruppe (det=±1) des ^k mitk=2 oder 3 undN eine endliche Menge von Punkten des ^k , welche unterG invariant ist. Dies gibt Anlass zu einer Permutationsdarstellung vonG im Vektorraum der komplexen Funktionen aufN.In Abschn. 3 wird für eine symmetriegerechte Basis angegeben. Dabei sind die Funktionswerte jeweils exakt tabelliert.

---

Let G be a finite subgroup of the orthogonal group (det=±1) of ^k wherek=2 or 3 and letN be a finite set of points of ^k , which is invariant underG. In this way one gets a permutation representation ofG in the vector space of the complex functions onN.In Section 3, a symmetry adapted basis is given for , where the function values are tabulated exactly.

---

---

Im Buch [1] wurden lediglich die Diedergruppen behandelt (in Abschn. 3.1).     

Paradoxical subsets of hyperbolic and spherical discs

Given a disc D of radius r in H ² (resp. S ²) with <r (resp. <r), we determine the pairs (m,n) for which there is an (m,n)-paradoxical subset of D but not an (m–1, n)-paradoxical subset of D or an (m, n–1)-paradoxical subset of D.     

On the consistency of conditional maximum likelihood estimators

Let {P _, : , H} be a family of probability measures admitting a sufficient statistic for the nuisance parameter . The paper presents conditions for consistency of (asymptotic) conditional maximum likelihood estimators for . An application to the Rasch-model (a stochastic model for psychological tests) yields a condition on the sequence of nuisance parameters which is sufficient for strong consistency of conditional maximum likelihood estimators, and necessary for the existence of any weakly consistent estimator-sequence.     

Two poset polytopes

Two convex polytopes, called theorder polytope (P) andchain polytope (P), are associated with a finite posetP. There is a close interplay between the combinatorial structure ofP and the geometric structure of (P). For instance, the order polynomial (P, m) ofP and Ehrhart polynomiali((P),m) of (P) are related by (P, m+1)=i((P),m). A transfer map then allows us to transfer properties of (P) to (P). In particular, we transfer known inequalities involving linear extensions ofP to some new inequalities.Partially supported by NSF Grant No. 8104855-MCS and by a Guggenheim Fellowship.     

On strong maximal operators corresponding to different frames

The problem is posed and solved whether the conditionsf L(1+1n⁺ L)²(²) and are equivalent for functionsf L(²) (whereM _2, denotes the strong maximal operator corresponding to the frame {OX ,OY }).The results obtained represent a general solution of M. de Guzmán's problem that was previously studied by various authors.     

Randomized graph products, chromatic numbers, and the Lovász ϑ-function

For a graphG, let (G) denote the size of the largest independent set inG, and let (G) denote the Lovász -function onG. We prove that for somec>0, there exists an infinite family of graphs such that \alpha (G)n/2^{c\sqrt {\log n} }$$ " align="middle" border="0"> , wheren denotes the number of vertices in a graph. this disproves a known conjecture regarding the function.As part of our proof, we analyse the behavior of the chromatic number in graphs under a randomized version of graph products. This analysis extends earlier work of Linial and Vazirani, and of Berman and Schnitger, and may be of independent interest.Incumbent of the Joseph and Celia Reskin Career Development Chair. Yigal Alon Fellow     

A decomposition for the exponential dispersion model generated by the invariant measure on the hyperboloid

For = ₀, ₁, ₂) andx=(x₀, x₁, x₂) in R³, define [,x] = ₀ x ₀ – ₁ x ₁ – ₂ x ₂,C = {x³:x ₀ > 0 and [x, x]>0},R(x)=([x, x]) ^1/2 forx inC andH ₁={xC: x₀>0,R(x)=1}. Define the measure onH ₁ such that if is inC and =R(), then exp (–[,x])(dx = ( exp )^–1. Therefore, is invariant under the action ofSO (1, 2), the connected component ofO(1, 2) containing the identity. We first prove that there exists a positive measure in ³ such that its Laplace transform is ( exp )^– if and only if >1. Finally, for 1 and inC, denotingP(,)(dx) = ( exp )^– exp (–[,x])(dx, we show that ifY ₀,...,Y _n aren+1 independent variables with densityP(,),j=0,...,n and ifS _k =X ₀ + ... +X _k andQ _k =R(S _k) –R(S _k–1) –R(Y _k),k=1,...,n, then then+1 statisticsD _n = [/,S _k ] –R _{k – 1} ),Q ₁,...,Q _n are independent random variables with the exponential () or gamma (1,1/) distribution.This research has been partially funded by NSERC Grant A8947.     

A characterization of hadamard designs with SL(2,q) acting transitively

Given a hyperoval in a projective plane of even orderq, we can associate a Hadamard 2-design. In the case when is the Desarguesian plane P_2,q ,q=2 ^h ,h>1 and is a regular hyperoval (conic and its nucleus) then a design (q) is obtained. (q) has a point transitive automorphism group isomorphic to PSL(2,q)( SL(2,q)). We classify the designs (q) and P_2h–1,2 (the projective space of dimension 2h–1 overF ₂) among all the designsH with the same parameters as (q) admitting an automorphism groupGSL(2,q) acting transitively the points ofH. We also describe how all such designsH may be constructed and discuss the problem of when two such designs are isomorphic.This research was supported by Science and Engineering Research Council Grant GR/G 03359.     

Equivalence Bimodule Between Non-Commutative Tori

The non-commutative torus C ^*(ⁿ,) is realized as the C*-algebra of sections of a locally trivial C*-algebra bundle over S with fibres isomorphic to C ^*n/S, ₁) for a totally skew multiplier ₁ on ⁿ/S. D. Poguntke [9] proved that A is stably isomorphic to C(S) C(^*( Zⁿ/S, ₁) C(S) A M_kl( C) for a simple non-commutative torus A and an integer kl. It is well-known that a stable isomorphism of two separable C*-algebras is equivalent to the existence of equivalence bimodule between them. We construct an A-C(S) A-equivalence bimodule.     

Two limit theorems on ARIMA models

Let the time series {X(t), t=1, 2, ...} satisfy (B)(1–B) ^d X(t)=(B)e(t), whereB is a backward shift operator, defined byBX(t)=X(t–1), and (z)=1+₁ z+...+ _p z ^p , (z)=1+₁ z+...+ _q z ^q , and all the roots of (z) lie outside the unit circle; {e(t)} is a sequence of iid random variables with mean zero andE|e(t)|^4+r < (r>0). In this paper, the limit properties of , where the integerd1, have been considered.     

The convergence rates of empirical Bayes estimation in a multiple linear regression model

Empirical Bayes (EB) estimation of the parameter vector =(,²) in a multiple linear regression modelY=X+ is considered, where is the vector of regression coefficient, N(0,² I) and ² is unknown. In this paper, we have constructed the EB estimators of by using the kernel estimation of multivariate density function and its partial derivatives. Under suitable conditions it is shown that the convergence rates of the EB estimators areO(n ^{-(k-1)(k-2)/k(2k+p+1)}), where the natural numberk3, 1/3<<1, andp is the dimension of vector .The project is supported by the National Natural Science Foundation of China.     

On a generalization of Morisita's model for estimating the habitat preference

The Morisita's model for estimating the habitat preference by the ant lionsGenuroides japonicus is generalized by introducing, in addition to the environmental densitiesa andb, a repulsivity parameter . The probability function of the numberL _n of individuals choosing fine sand to settle when a total ofn ant lions are introduced is examined. A heuristic and the minimum chi-square methods for estimating the parametersa, b and are discussed.     

Existence of a universal attractor for a fully hyperbolic phase-field system

Here we study a nonlinear hyperbolic integrodifferential system which was proposed by H.G. Rotstein et al. to describe certain peculiar phase transition phenomena. This system governs the evolution of the (relative) temperature and the order parameter (or phase-field) . We first consider an initial and boundary value problem associated with the system and we frame it in a history space setting. This is done by introducing two additional variables accounting for the histories of and . Then we show that the reformulated problem generates a dissipative dynamical system in a suitable infinite-dimensional phase space. Finally, we prove the existence of a universal attractor.     

A Hochschild Homology Euler Characteristic for Circle Actions

We define an S¹-Euler characteristic, _S ¹(X), of a circle action on a compact manifold or finite complex X. It lies in the first Hochschild homology group HH ₁(G) where G is the fundamental group of X. This _S ¹(X) is analogous in many ways to the ordinary Euler characteristic. One application is an intuitively satisfying formula for the Euler class (integer coefficients) of the normal bundle to a smooth circle action without fixed points on a manifold. In the special case of a three-dimensional Seifert fibered space, this formula is particularly effective.     

Thermal creep of polyethylene in the presence of thermal cycling

The temperature-time dependence of Poisson's ratio and the volume relaxation of LDP is investigated in the case of uniaxial tension. It is established that at elevated temperatures and loads the material becomes denser and Poisson's ratio exceeds 0.5. It is shown that the (t) curves and the temperature dependence of the instantaneous Poisson's ratio are nonmonotonic, while the nature of the (t) relaxation changes qualitatively as a certain temperature region is entered and the stress is increased.Mekhanika Polimerov, Vol. 4, No. 3, pp. 421–427, 1968     

On the Infinitesimal Rigidity of Homogeneous Varieties

Let XP be a variety (respectively an open subset of an analytic submanifold) and let xX be a point where all integer valued differential invariants are locally constant. We show that if the projective second fundamental form of X at x is isomorphic to the second fundamental form of a point of a Segre P× P, n,m2, a Grassmaniann G(2,n+2), n4, or the Cayley plane OP², then X is the corresponding homogeneous variety (resp. an open subset of the corresponding homogeneous variety). The case of the Segre P²×P² had been conjectured by Griffiths and Harris in [GH]. If the projective second fundamental form of X at x is isomorphic to the second fundamental form of a point of a Veronese v₂(P) and the Fubini cubic form of X at x is zero, then X=v₂ (P) (resp. an open subset of v₂(P)). All these results are valid in the real or complex analytic categories and locally in the C category if one assumes the hypotheses hold in a neighborhood of any point x. As a byproduct, we show that the systems of quadrics I₂(P P) S²C, I₂(P¹× P) S²C and I₂(S₅) S²C¹⁶ are stable in the sense that if A S^* is an analytic family such that for t0,AA, then A₀A. We also make some observations related to the Fulton–:Hansen connectedness theorem.     

On the strongly spherical Sasakian metric of a spherical tangent bundle

Let Mⁿ denote an n-dimensional Riemannian manifold. Its metric is called -strongly spherical if at every point Q Mⁿ there exists a -dimensional subspace _Q T_QMⁿ such that the curvature operator of the metric of Mⁿ satisfies R(X, Y) Z = k(< Y, Z > X < X, Z > Y), where k = const > 0, Y _Q , X, Z #x2208; T_QMⁿ. The number is called the index of sphericity and k the exponent of sphericity. The following theorems are proved in the paper.THEOREM 1. Let the Sasakian metric of T₁Mⁿ be -strongly spherical with exponent of sphericity k. The following assertions hold: a) = 1 if and only if M² has constant Gaussian curvature K 1 and k = K²/4; b) = 3 if and only if M² has constant curvature K = 1 and k = 1/4; c) = 0, otherwise.THEOREM 2. Let the Sasakian metric of T₁Mⁿ (n Mⁿ) be -strongly spherical with exponent of sphericity k. If k > 1/3 and k 1, then = 0. Let us denote by (Mⁿ, K) a space of constant curvatureK. THEOREM 3. Let the Sasakian metric of T₁(Mⁿ, K) (n 3) be -strongly spherical with exponent of sphericity k. The following assertions hold: a) = 1 if and only if K = 1/4; b) = 0, otherwise. In dimension n = 3 Theorem 2 is true for k {1/4, 1}.Translated from Ukrainskii Geometricheskii Sbornik, No. 35, pp. 150–159, 1992.     

Approximating the independence number via theϑ-function

We describe an approximation algorithm for the independence number of a graph. If a graph onn vertices has an independence numbern/k + m for some fixed integerk 3 and somem > 0, the algorithm finds, in random polynomial time, an independent set of size , improving the best known previous algorithm of Boppana and Halldorsson that finds an independent set of size (m ^1/(k–1)) in such a graph. The algorithm is based on semi-definite programming, some properties of the Lovász-function of a graph and the recent algorithm of Karger, Motwani and Sudan for approximating the chromatic number of a graph. If the-function of ann vertex graph is at leastMn ^1–2/k for some absolute constantM, we describe another, related, efficient algorithm that finds an independent set of sizek. Several examples show the limitations of the approach and the analysis together with some related arguments supply new results on the problem of estimating the largest possible ratio between the-function and the independence number of a graph onn vertices. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Research supported in part by a USA—Israel BSF grant and by the Fund for Basic Research administered by the Israel Academy of Sciences and by the Minkowski Minerva Center for Geometry at Tel Aviv University.This work was partly done while the author was at XEROX PARC and partly at DIMACS.