One-Shot CFTP; Application to a Class of Truncated Gaussian Densities

In this paper, we introduce a new method for perfect simulation of multivariate densities. We use One-Shot CFTP (G. Roberts and J. Rosenthal, “One-shot coupling for certain stochastic recursive sequences,” Stochastic Processes and their Applications vol. 99 pp. 195–208, 2002) together with a monotone coupler for the Gibbs sampler, and implement the algorithm within the Read-Once CFTP protocol (D. B. Wilson, “How to couple form the past using a read-once source of randomness,” Random Structures and Algorithms vol. 16(1) pp. 85–113, 2000b). We illustrate our method by simulating efficiently from high-dimensional truncated normal distributions using the Gibbs sampler. AMS 2000 Subject Classification Primary 65C40; Secondary 65C60     

<Emphasis Type="Italic">L</Emphasis>(<Emphasis Type="Italic">h</Emphasis>, 1, 1)-labeling of outerplanar graphs

An L(h, 1, 1)-labeling of a graph is an assignment of labels from the set of integers {0, . . . , λ} to the nodes of the graph such that adjacent nodes are assigned integers of at least distance h ≥ 1 apart and all nodes of distance three or less must be assigned different labels. The aim of the L(h, 1, 1)-labeling problem is to minimize λ, denoted by λ _{h, 1, 1} and called span of the L(h, 1, 1)-labeling. As outerplanar graphs have bounded treewidth, the L(1, 1, 1)-labeling problem on outerplanar graphs can be exactly solved in O(n ³), but the multiplicative factor depends on the maximum degree Δ and is too big to be of practical use. In this paper we give a linear time approximation algorithm for computing the more general L(h, 1, 1)-labeling for outerplanar graphs that is within additive constants of the optimum values. This research is partially supported by the European Research Project Algorithmic Principles for Building Efficient Overlay Computers (AEOLUS) and was done during the visit of Richard B. Tan at the Department of Computer Science, University of Rome “Sapienza”, supported by a visiting fellowship from the University of Rome “Sapienza”.     

Combinatorial Groupoids,Cubical Complexes,and the Lovász Conjecture

This paper lays the foundation for a theory of combinatorial groupoids that allows us to use concepts like “holonomy”, “parallel transport”, “bundles”, “combinatorial curvature”, etc. in the context of simplicial (polyhedral) complexes, posets, graphs, polytopes and other combinatorial objects. We introduce a new, holonomy-type invariant for cubical complexes, leading to a combinatorial “Theorema Egregium” for cubical complexes that are non-embeddable into cubical lattices. Parallel transport of Hom-complexes and maps is used as a tool to extend Babson–Kozlov–Lovász graph coloring results to more general statements about nondegenerate maps (colorings) of simplicial complexes and graphs. The author was supported by grants 144014 and 144026 of the Serbian Ministry of Science and Technology.     

Asymptotically optimal choice of the smoothing parameter in a nonparametric kernel estimator for a probability density

This paper presents a method of estimation of an “optimal” smoothing parameter (window width) in kernel estimators for a probability density. The obtained estimator is calculated directly from observations. By “optimal” smoothing parameters we mean those parameters which minimize the mean integral square error (MISE) or the integral square error (ISE) of approximation of an unknown density by the kernel estimator. It is shown that the asymptotic “optimality” properties of the proposed estimator correspond (with respect to the order) to those of the well-known cross-validation procedure [1, 2]. Translated fromStatisticheskie Metody Otsenivaniya i Proverki Gipotez, pp. 67–80, Perm, 1990.     

Precoloring Extension of Co-Meyniel Graphs

The pre-coloring extension problem consists, given a graph G and a set of nodes to which some colors are already assigned, in finding a coloring of G with the minimum number of colors which respects the pre-coloring assignment. This can be reduced to the usual coloring problem on a certain contracted graph. We prove that pre-coloring extension is polynomial for complements of Meyniel graphs. We answer a question of Hujter and Tuza by showing that “PrExt perfect” graphs are exactly the co-Meyniel graphs, which also generalizes results of Hujter and Tuza and of Hertz. Moreover we show that, given a co-Meyniel graph, the corresponding contracted graph belongs to a restricted class of perfect graphs (“co-Artemis” graphs, which are “co-perfectly contractile” graphs), whose perfectness is easier to establish than the strong perfect graph theorem. However, the polynomiality of our algorithm still depends on the ellipsoid method for coloring perfect graphs. C.N.R.S. Final version received: January, 2007     

Sequent calculi for branching time temporal logics of knowledge and beliefwith awareness: Completeness and decidability

In this paper, we consider branching time temporal logic CT L with epistemic modalities for knowledge (belief) and with awareness operators. These logics involve the discrete-time linear temporal logic operators “next” and “until” with the branching temporal logic operator “on all paths”. In addition, the temporal logic of knowledge (belief) contains an indexed set of unary modal operators “agent i knows” (“agent i believes”). In a language of these logics, there are awareness operators. For these logics, we present sequent calculi with a restricted cut rule. Thus, we get proof systems where proof-search becomes decidable. The soundness and completeness for these calculi are proved. Published in Lietuvos Matematikos Rinkinys, Vol. 47, No. 3, pp. 328–340, July–September, 2007.     

Space structures: Theory and applications. 3

This paper is the third part of the book Space Structures: Theory and Applications. This part consists of an introduction and two chapters: “P²-Topological Spaces” and “Structured Sets.” __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 352, 2008, pp. 7–93.     

On weight distributions of perfect colorings and completely regular codes

A vertex coloring of a graph is called “perfect” if for any two colors a and b, the number of the color-b neighbors of a color-a vertex x does not depend on the choice of x, that is, depends only on a and b (the corresponding partition of the vertex set is known as “equitable”). A set of vertices is called “completely regular” if the coloring according to the distance from this set is perfect. By the “weight distribution” of some coloring with respect to some set we mean the information about the number of vertices of every color at every distance from the set. We study the weight distribution of a perfect coloring (equitable partition) of a graph with respect to a completely regular set (in particular, with respect to a vertex if the graph is distance-regular). We show how to compute this distribution by the knowledge of the color composition over the set. For some partial cases of completely regular sets, we derive explicit formulas of weight distributions. Since any (other) completely regular set itself generates a perfect coloring, this gives universal formulas for calculating the weight distribution of any completely regular set from its parameters. In the case of Hamming graphs, we prove a very simple formula for the weight enumerator of an arbitrary perfect coloring.     

Linear liftings of skew symmetric tensor fields of type (1, 2) to Weil bundles

The paper contains a classification of linear liftings of skew symmetric tensor fields of type (1, 2) on n-dimensional manifolds to tensor fields of type (1, 2) on Weil bundles under the condition that n ⩾ 3. It complements author’s paper “Linear liftings of symmetric tensor fields of type (1, 2) to Weil bundles” (Ann. Polon. Math. 92, 2007, pp. 13–27), where similar liftings of symmetric tensor fields were studied. We apply this result to generalize that of author’s paper “Affine liftings of torsion-free connections to Weil bundles” (Colloq. Math. 114, 2009, pp. 1–8) and get a classification of affine liftings of all linear connections to Weil bundles.     

Chaotic time dependence in a disordered spin system

Stochastic Ising and voter models on ℤ ^d are natural examples of Markov processes with compact state spaces. When the initial state is chosen uniformly at random, can it happen that the distribution at time t has multiple (subsequence) limits as t→∞? Yes for the d = 1 Voter Model with Random Rates (VMRR) – which is the same as a d = 1 rate-disordered stochastic Ising model at zero temperature – if the disorder distribution is heavy-tailed. No (at least in a weak sense) for the VMRR when the tail is light or d≥ 2. These results are based on an analysis of the “localization” properties of Random Walks with Random Rates. Received: 10 August 1998     

Complete Upper Angle Around a Point on the Minkowski Plane

The dependence of the complete upper angle in the sense of A. D. Aleksandrov about a point on the Minkowski plane on the form of the “unit circle” (the centrally symmetric convex curve Φ determining the Minkowski metric ρ_Φ) is studied.The complete upper angle is computed in three cases: if Φ is a square, a “cut circle,” or a “rounded rhombus.” Bibliography: 6 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 299, 2003, pp. 42–53.     

Undecidability of a simple fragment of a positive theory with a single constant for a free semigroup of rank two

In the paper we study the algorithmic nature of some “simple” fragments of positive theories with “few” constants for free noncyclic semigroups. Translated fromMatematicheskie Zametki, Vol. 67, No. 2, pp. 191–200, February, 2000.     

Polyhedral surfaces in wedge products

We introduce the wedge product of two polytopes. The wedge product is described in terms of inequality systems, in terms of vertex coordinates as well as purely combinatorially, from the corresponding data of its constituents. The wedge product construction can be described as an iterated “subdirect product” as introduced by McMullen (Discrete Math 14:347–358, 1976); it is dual to the “wreath product” construction of Joswig and Lutz (J Combinatorial Theor A 110:193–216, 2005). One particular instance of the wedge product construction turns out to be especially interesting: The wedge products of polygons with simplices contain certain combinatorially regular polyhedral surfaces as subcomplexes. These generalize known classes of surfaces “of unusually large genus” that first appeared in works by Coxeter (Proc London Math Soc 43:33–62, 1937), Ringel (Abh Math Seminar Univ Hamburg 20:10–19, 1956), and McMullen et al. (Israel J Math 46:127–144, 1983). Via “projections of deformed wedge products” we obtain realizations of some of the surfaces in the boundary complexes of 4-polytopes, and thus in \mathbb R³{{\mathbb R}^3} . As additional benefits our construction also yields polyhedral subdivisions for the interior and the exterior, as well as a great number of local deformations (“moduli”) for the surfaces in \mathbb R³{{\mathbb R}^3} . In order to prove that there are many moduli, we introduce the concept of “affine support sets” in simple polytopes. Finally, we explain how duality theory for 4-dimensional polytopes can be exploited in order to also realize combinatorially dual surfaces in \mathbb R³{{\mathbb R}^3} via dual 4-polytopes.     

Regular Score Tests of Independence in Multivariate Extreme Values

The score tests of independence in multivariate extreme values derived by Tawn (Tawn, J.A., “Bivariate extreme value theory: models and estimation,” Biometrika 75, 397–415, 1988) and Ledford and Tawn (Ledford, A.W. and Tawn, J.A., “Statistics for near independence in multivariate extreme values,” Biometrika 83, 169–187, 1996) have non-regular properties that arise due to violations of the usual regularity conditions of maximum likelihood. Two distinct types of regularity violation are encountered in each of their likelihood frameworks: independence within the underlying model corresponding to a boundary point of the parameter space and the score function having an infinite second moment. For applications, the second form of regularity violation has the more important consequences, as it results in score statistics with non-standard normalisation and poor rates of convergence. The corresponding tests are difficult to use in practical situations because their asymptotic properties are unrepresentative of their behaviour for the sample sizes typical of applications, and extensive simulations may be needed in order to evaluate adequately their null distribution. Overcoming this difficulty is the primary focus of this paper. We propose a modification to the likelihood based approaches used by Tawn (Tawn, J.A., “Bivariate extreme value theory: models and estimation,” Biometrika 75, 397–415, 1988) and Ledford and Tawn (Ledford, A.W. and Tawn, J.A., “Statistics for near independence in multivariate extreme values,” Biometrika 83, 169–187, 1996) that provides asymptotically normal score tests of independence with regular normalisation and rapid convergence. The resulting tests are straightforward to implement and are beneficial in practical situations with realistic amounts of data. AMS 2000 Subject Classification Primary—60G70 Secondary—62H15     

The “parking” problem for segments of different length

A modified “parking” problem is considered. Segments of different length fill a large interval (in our case, there are two kinds of segments). The asymptotics of the mean number of segmentsplaced are obtained. Bibliography: 2 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 228, 1996, pp. 16–23.     

On Small World Semiplanes with Generalised Schubert Cells

The well known “real-life examples” of small world graphs, including the graph of binary relation: “two persons on the earth know each other” contains cliques, so they have cycles of order 3 and 4. Some problems of Computer Science require explicit construction of regular algebraic graphs with small diameter but without small cycles. The well known examples here are generalised polygons, which are small world algebraic graphs i.e. graphs with the diameter d≤clog  _k−1(v), where v is order, k is the degree and c is the independent constant, semiplanes (regular bipartite graphs without cycles of order 4); graphs that can be homomorphically mapped onto the ordinary polygons. The problem of the existence of regular graphs satisfying these conditions with the degree ≥k and the diameter ≥d for each pair k≥3 and d≥3 is addressed in the paper. This problem is positively solved via the explicit construction. Generalised Schubert cells are defined in the spirit of Gelfand-Macpherson theorem for the Grassmanian. Constructed graph, induced on the generalised largest Schubert cells, is isomorphic to the well-known Wenger’s graph. We prove that the family of edge-transitive q-regular Wenger graphs of order 2q ⁿ , where integer n≥2 and q is prime power, q≥n, q>2 is a family of small world semiplanes. We observe the applications of some classes of small world graphs without small cycles to Cryptography and Coding Theory.     

Exact solutions of one-dimensional two-phase free boundary problems for parabolic equations

We construct automodel solutions for the one-dimensional two-phase Stefan, Florin, and Verigin free boundary problems for parabolic equations in the case where the initial and boundary data are not adjusted. It is shown that in the Stefan problem with “supercooling,” the liquid temperature may be less than the temperature of the phase transition, i.e., the liquid may be “supercooled” while the solid may be “superheated.” Bibliography: 8 titles. Dedicated to the memory of Olga Aleksandrovna Ladyzhenskaya __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 318, 2004, pp. 42–59.     

On the doubled tetrus

The “tetrus” is a member of a family of hyperbolic 3-manifolds with totally geodesic boundary, described by Paoluzzi–Zimmerman, which also contains W.P. Thurston’s “tripus.” Each member of this family has a branched cover to B ³ over a certain tangle T. This map on the tripus has degree three, and on the tetrus degree four. We describe a cover of the double of the tetrus, itself a double across a closed surface, which fibers over the circle.     

Self-duality equation: Monodromy matrices and algebraic curves

It is shown that the general local solution of the self-duality equation with SU(1,1) and SU(2) gauge groups is associated with some algebraic curve with moving branch points if the related “monodromy matrix” is rational. The “multisoliton” solutions including monopoles and instantons, correspond to degenerate curves when the branch cuts collapse to double points. Bibliography:18 titles. Dedicated to L. D. Faddeev on the occasion of his 60th birthday Published inZapiski Nauchnykh Seminarov POMI, Vol. 215, 1994, pp. 197–216. Translated by D. A. Korotkin.