Strengthened semidefinite programming bounds for codes

We give a hierarchy of semidefinite upper bounds for the maximum size A(n,d) of a binary code of word length n and minimum distance at least d. At any fixed stage in the hierarchy, the bound can be computed (to an arbitrary precision) in time polynomial in n; this is based on a result of de Klerk et al. (Math Program, 2006) about the regular ∗-representation for matrix ∗-algebras. The Delsarte bound for A(n,d) is the first bound in the hierarchy, and the new bound of Schrijver (IEEE Trans. Inform. Theory 51:2859–2866, 2005) is located between the first and second bounds in the hierarchy. While computing the second bound involves a semidefinite program with O(n ⁷) variables and thus seems out of reach for interesting values of n, Schrijver’s bound can be computed via a semidefinite program of size O(n ³), a result which uses the explicit block-diagonalization of the Terwilliger algebra. We propose two strengthenings of Schrijver’s bound with the same computational complexity. Supported by the Netherlands Organisation for Scientific Research grant NWO 639.032.203.     

REGULAR RELATIONS AND MONOTONE NORMAL ORDERED SPACES

In this paper the classical theorem of Zareckii about regular relations is generalized and an intrinsic characterization of regularity is obtained. Based on the generalized Zareckii theorem and the intrinsic characterization of regularity, the authors give a characterization of monotone normality of ordered spaces. A new proof of the Urysohn-Nachbin lemma is presented which is quite different from the classical one.     

Diameter graphs of polygons and the proof of a conjecture of Graham

We show that for an n-gon with unit diameter to have maximum area, its diameter graph must contain a cycle, and we derive an isodiametric theorem for such n-gons in terms of the length of the cycle. We then apply this theorem to prove Graham's 1975 conjecture that the diameter graph of a maximal 2m-gon (m?3) must be a cycle of length 2m−1 with one additional edge attached to it.     

Clustering of spectra and fractals of regular graphs

We exhibit a characteristic structure of the class of all regular graphs of degree d that stems from the spectra of their adjacency matrices. The structure has a fractal threadlike appearance. Points with coordinates given by the mean and variance of the exponentials of graph eigenvalues cluster around a line segment that we call a filar. Zooming-in reveals that this cluster splits into smaller segments (filars) labeled by the number of triangles in graphs. Further zooming-in shows that the smaller filars split into subfilars labeled by the number of quadrangles in graphs, etc. We call this fractal structure, discovered in a numerical experiment, a multifilar structure. We also provide a mathematical explanation of this phenomenon based on the Ihara-Selberg trace formula, and compute the coordinates and slopes of all filars in terms of Bessel functions of the first kind.     

On circle diffeomorphisms with discontinuous derivatives and quasi-invariance subgroups of Malliavin-Shavgulidze measures

This note is devoted to construction of the domain of the regular representation of Diff₊(S¹). We consider a subgroup of diffeomorphism group such that the Malliavin-Shavgulidze measure is quasi-invariant with respect to the left action of the subgroup. The measure appears to be quasi-invariant with respect to the left action of diffeomorphisms with discontinuous second derivative. We derive an expression for quasi-invariance density and obtain an additional PSL(2,R) symmetry breaking term.     

Tail asymptotics for the fundamental period in the MAP/G/1 queue

This paper studies the tail behavior of the fundamental period in the MAP/G/1 queue. We prove that if the service time distribution has a regularly varying tail, then the fundamental period distribution in the MAP/G/1 queue has also regularly varying tail, and vice versa, by finding an explicit expression for the asymptotics of the tail of the fundamental period in terms of the tail of the service time distribution. Our main result with the matrix analytic proof is a natural extension of the result in (de Meyer and Teugels, J. Appl. Probab. 17: 802–813, 1980) on the M/G/1 queue where techniques rely heavily on analytic expressions of relevant functions. I.-S. Wee’s research was supported by the Korea Research Foundation Grant KRF 2003-070-00008.     

The automorphism group of Payne derived generalized quadrangles

We solve a long-standing open problem by proving that the automorphism group of any thick Payne derived generalized quadrangle with ambient quadrangle S a thick generalized quadrangle of order s, s?5 and odd, with a center of symmetry, is induced by the automorphism group of S.     

Estimating tail probabilities of heavy tailed distributions with asymptotically zero relative error

Efficient estimation of tail probabilities involving heavy tailed random variables is amongst the most challenging problems in Monte-Carlo simulation. In the last few years, applied probabilists have achieved considerable success in developing efficient algorithms for some such simple but fundamental tail probabilities. Usually, unbiased importance sampling estimators of such tail probabilities are developed and it is proved that these estimators are asymptotically efficient or even possess the desirable bounded relative error property. In this paper, as an illustration, we consider a simple tail probability involving geometric sums of heavy tailed random variables. This is useful in estimating the probability of large delays in M/G/1 queues. In this setting we develop an unbiased estimator whose relative error decreases to zero asymptotically. The key idea is to decompose the probability of interest into a known dominant component and an unknown small component. Simulation then focuses on estimating the latter ‘residual’ probability. Here we show that the existing conditioning methods or importance sampling methods are not effective in estimating the residual probability while an appropriate combination of the two estimates it with bounded relative error. As a further illustration of the proposed ideas, we apply them to develop an estimator for the probability of large delays in stochastic activity networks that has an asymptotically zero relative error.      

New light on Hensel''s lemma

The historical development of Hensel's lemma is briefly discussed (Section 1). Using Newton polygons, a simple proof of a general Hensel's lemma for separable polynomials over Henselian fields is given (Section 3). For polynomials over algebraically closed, valued fields, best possible results on continuity of roots (Section 4) and continuity of factors (Section 6) are demonstrated. Using this and a general Krasner's lemma (Section 7), we give a short proof of a general Hensel's lemma and show that it is, in a certain sense, best possible (Section 8). All valuations here are non-Archimedean and of arbitrary rank. The article is practically self-contained.     

A Characterization of the Optimal p-sum Labellingsof Unit Interval Graphs

1.IntroductionGraphsconsideredinthispaperarefiniteandsimple.FOragraphG,V(G)andE(G)denoteitssetofvenicesandedges,respectively.AbijectionwillbecalledalabellingofG.Letpbeapositiverealnumber.ForagivenlabellingTofagraphG,definethegndiscrepencya.(G,ac)ofTasTheobjectiveoftheminimum-p--sumproblemistofindalabelling7ofagraphGsuchthatac(G,T)isassmallaspossible.ThelabellingTminimizinga.(G,7)iscalledanoptimalHsumlabellingofG.Theminimumvalueiscalledtheminimum-psumofG.ItisshowninI31thattheminimum-…