A Discrete Laplace–Beltrami Operator for Simplicial Surfaces

We define a discrete Laplace–Beltrami operator for simplicial surfaces (Definition 16). It depends only on the intrinsic geometry of the surface and its edge weights are positive. Our Laplace operator is similar to the well known finite-elements Laplacian (the so called “cotan formula”) except that it is based on the intrinsic Delaunay triangulation of the simplicial surface. This leads to new definitions of discrete harmonic functions, discrete mean curvature, and discrete minimal surfaces. The definition of the discrete Laplace–Beltrami operator depends on the existence and uniqueness of Delaunay tessellations in piecewise flat surfaces. While the existence is known, we prove the uniqueness. Using Rippa’s Theorem we show that, as claimed, Musin’s harmonic index provides an optimality criterion for Delaunay triangulations, and this can be used to prove that the edge flipping algorithm terminates also in the setting of piecewise flat surfaces. Research for this article was supported by the DFG Research Unit 565 “Polyhedral Surfaces” and the DFG Research Center Matheon “Mathematics for key technologies” in Berlin.     

Weighted Hermite-Fejér interpolation on the real line: L ∞ case

We give a weighted Hermite-Fejér-type interpolatory method on the real line, which is a positive operator on “good” matrices. We give an example on “good” interpolatory matrix by weighted Fekete points. To prove the convergence theorem we need the generalization of “Rodrigues’ property”. The present publication was written in the framework of the Hungarian-Spanish Scientific and Technological Governmental Cooperation, no. E-38/04, with the support of the Research and Technological Development Fund of Hungary and the Ministry of Education of Spain, and supported by Hungarian National Foundation for Scientific Research, Grant No. T049301.     

A minimization version of a directed subgraph homeomorphism problem

We consider a special case of the directed subgraph homeomorphism or topological minor problem, where the host graph has a specific regular structure. Given an acyclic directed pattern graph, we are looking for a host graph of minimal height which still allows for an embedding. This problem has applications in compiler design for certain coarse-grain reconfigurable architectures. In this application domain, the task is to simultaneously schedule, bind and route a so-called data-flow graph, where vertices represent operations and arcs stand for data dependencies between the operations, given an orthogonal grid structure of reconfigurable processing elements (PEs) that have restricted communication abilities. We show that the problem of simultaneously scheduling, binding and routing is NP-complete by describing a logic engine reduction from NAE-3-SAT. This result holds even when the input graph is a directed tree with maximum indegree two. We also give a |V|^3/2-approximation algorithm. J. A. Brenner’s research supported by the DFG Research Center Matheon “Mathematics for key technologies”. J. C. van der Veen’s research supported by DFG Focus Program 1148, “Reconfigurable Architectures”, Grants FE 407/8-1 and FE 407/8-2.     

Local Linear Convergence for Alternating and Averaged Nonconvex Projections

The idea of a finite collection of closed sets having “linearly regular intersection” at a point is crucial in variational analysis. This central theoretical condition also has striking algorithmic consequences: in the case of two sets, one of which satisfies a further regularity condition (convexity or smoothness, for example), we prove that von Neumann’s method of “alternating projections” converges locally to a point in the intersection, at a linear rate associated with a modulus of regularity. As a consequence, in the case of several arbitrary closed sets having linearly regular intersection at some point, the method of “averaged projections” converges locally at a linear rate to a point in the intersection. Inexact versions of both algorithms also converge linearly. Research of A.S. Lewis supported in part by National Science Foundation Grant DMS-0504032. Research of D.R. Luke supported in part by National Science Foundation Grant DMS-0712796.     

Monadic theory of order and topology, 1

We deal with the monadic theory of linearly ordered sets and topological spaces, disprove two of Shelah’s conjectures and prove some more results. In particular, if the Continuum Hypothesis holds, then there exist monadic formulae expressing the predicates “X is countable” and “X is meager” in the real line and in Cantor’s Discontinuum.     

Convergence of a class of degenerate Ginzburg-Landau functionals and regularity for a subelliptic harmonic map equation

In this paper, we consider a class of Ginzburg-Landau functionalsE _ε associated with a couple of non-commuting vector fields which yield a “degenerate” energy. We study the asymptotic behavior of the minimizers, showing that it does not depend on the topological degree of the boundary datum; and we prove uniqueness and regularity of the minimizer of the limit problem, in spite of the lack of lifting theorems in the natural function spaces for the limit functional.

---

Résumé  Dans cet article, nous considérons une classe de fonctionnellesE _ε du type Ginzburg-Landau associée a un couple de champs de vecteurs définissant une énergie dégénérée. Nous étudions le comportement asymptotique des minimiseurs. Nous démontrons que ce comportement ne dépend pas du degré topologique de la donnée a la frontiere et nous prouvons l’unicité et la régularité du minimiseur du probléme limite, malgré l’absence d’un théorème de lifting dans les espaces de Sobolev naturels pour la même fonctionnelle.

---

---

The authors were supported by University of Bologna, funds for selected research topics, and by GNAMPA of the INDAM, Italy, project “Analysis in metric spaces and subelliptic equations.”     

Local Chromatic Number, KY Fan's Theorem, And Circular Colorings

The local chromatic number of a graph was introduced in [14]. It is in between the chromatic and fractional chromatic numbers. This motivates the study of the local chromatic number of graphs for which these quantities are far apart. Such graphs include Kneser graphs, their vertex color-critical subgraphs, the Schrijver (or stable Kneser) graphs; Mycielski graphs, and their generalizations; and Borsuk graphs. We give more or less tight bounds for the local chromatic number of many of these graphs. We use an old topological result of Ky Fan [17] which generalizes the Borsuk–Ulam theorem. It implies the existence of a multicolored copy of the complete bipartite graph K_{⌈t/2⌉,⌊t/2⌋} in every proper coloring of many graphs whose chromatic number t is determined via a topological argument. (This was in particular noted for Kneser graphs by Ky Fan [18].) This yields a lower bound of ⌈t/2⌉ + 1 for the local chromatic number of these graphs. We show this bound to be tight or almost tight in many cases. As another consequence of the above we prove that the graphs considered here have equal circular and ordinary chromatic numbers if the latter is even. This partially proves a conjecture of Johnson, Holroyd, and Stahl and was independently attained by F. Meunier [42]. We also show that odd chromatic Schrijver graphs behave differently, their circular chromatic number can be arbitrarily close to the other extreme. * Research partially supported by the Hungarian Foundation for Scientific Research Grant (OTKA) Nos. T037846, T046376, AT048826, and NK62321. † Research partially supported by the NSERC grant 611470 and the Hungarian Foundation for Scientific Research Grant (OTKA) Nos. T037846, T046234, AT048826, and NK62321.     

Upper Semicontinuity of the Solution set to Parametric Vector Quasivariational Inequalities

We prove the upper semicontinuity (in term of the closedness) of the solution set with respect to parameters of vector quasivariational inequalities involving multifunctions in topological vector spaces under the semicontinuity of the data, avoiding monotonicity assumptions. In particular, a new quasivariational inequality problem is proposed. Applications to quasi-complementarity problems are considered This work was partially supported by the program “Optimisation et Mathématiques Appliquées” of C.I.U.F-C.U.D./C.U.I. of Belgium and by the National Basic Research Program in Natural Sciences of NCSR of Vietnam     

Carleson Measures via BMO

We obtain new characterizations of Carleson measures via uniform boundedness of BMO norms of certain mass functions associated with the given measure in a natural way. This research was performed during M. Stessin’s visit to Korea University. He thanks the Mathematics Department of Korea University and the “Brain Pool” program for their hospitality and support. The first two authors were supported by the Korea Research Foundation Grant funded by the Korean Government (KRF-2008-314-C00012).     

Theta lifting from elliptic cusp forms to automorphic forms on <Emphasis Type="Italic">Sp</Emphasis>(1, <Emphasis Type="Italic">q</Emphasis>)

Tsuneo Arakawa formulated a theta lifting from elliptic cusp forms to automorphic forms on Sp(1,q) in his unpublished note, which was inspired by “Kudla lifting”, i.e. a theta lifting from elliptic modular forms to holomorphic automorphic forms on SU(1,q). We prove that the images of Arakawa’s theta lifting belong to the space of bounded automorphic forms generating quaternionic discrete series, which are non-holomorphic forms. In the appendix we provide the construction of Eisenstein series and Poincaré series generating such discrete series. The author was partially supported by JSPS Research Fellowships for Young Scientist for April 2002 to March 2005. The results of this paper were obtained in this period.     

Extremal Problems For Transversals In Graphs With Bounded Degree

We introduce and discuss generalizations of the problem of independent transversals. Given a graph property , we investigate whether any graph of maximum degree at most d with a vertex partition into classes of size at least p admits a transversal having property . In this paper we study this problem for the following properties : “acyclic”, “H-free”, and “having connected components of order at most r”. We strengthen a result of [13]. We prove that if the vertex set of a d-regular graph is partitioned into classes of size d+⌞d/r⌟, then it is possible to select a transversal inducing vertex disjoint trees on at most r vertices. Our approach applies appropriate triangulations of the simplex and Sperner’s Lemma. We also establish some limitations on the power of this topological method. We give constructions of vertex-partitioned graphs admitting no independent transversals that partially settles an old question of Bollobás, Erdős and Szemerédi. An extension of this construction provides vertex-partitioned graphs with small degree such that every transversal contains a fixed graph H as a subgraph. Finally, we pose several open questions. * Research supported by the joint Berlin/Zurichgrad uate program Combinatorics, Geometry, Computation, financed by the German Science Foundation (DFG) and ETH Zürich. † Research partially supported by Hungarian National Research Fund grants T-037846, T-046234 and AT-048826.     

Sparse second moment analysis for elliptic problems in stochastic domains

We consider the numerical solution of elliptic boundary value problems in domains with random boundary perturbations. Assuming normal perturbations with small amplitude and known mean field and two-point correlation function, we derive, using a second order shape calculus, deterministic equations for the mean field and the two-point correlation function of the random solution for a model Dirichlet problem which are 3rd order accurate in the boundary perturbation size. Using a variational boundary integral equation formulation on the unperturbed, “nominal” boundary and a wavelet discretization, we present and analyze an algorithm to approximate the random solution’s mean and its two-point correlation function at essentially optimal order in essentially work and memory, where N denotes the number of unknowns required for consistent discretization of the boundary of the nominal domain. This work was supported by the EEC Human Potential Programme under contract HPRN-CT-2002-00286, “Breaking Complexity.” Work initiated while HH visited the Seminar for Applied Mathematics at ETH Zürich in the Wintersemester 2005/06 and completed during the summer programme CEMRACS2006 “Modélisation de l’aléatoire et propagation d’incertitudes” in July and August 2006 at the C.I.R.M., Marseille, France.     

Self-similar sets of zero Hausdorff measure and positive packing measure

We prove that there exist self-similar sets of zero Hausdorff measure, but positive and finite packing measure, in their dimension; for instance, for almost everyu ∈ [3, 6], the set of all sums ∑ ₀ ⁸ a _n 4⁻ⁿ a _n 4⁻ⁿ with digits witha _n ∈ {0, 1,u} has this property. Perhaps surprisingly, this behavior is typical in various families of self-similar sets, e.g., for projections of certain planar self-similar sets to lines. We establish the Hausdorff measure result using special properties of self-similar sets, but the result on packing measure is obtained from a general complement to Marstrand’s projection theorem, that relates the Hausdorff measure of an arbitrary Borel set to the packing measure of its projections. Research of Y. Peres was partially supported by NSF grant #DMS-9803597. Research of K. Simon was supported in part by the OTKA foundation grant F019099. Research of B. Solomyak was supported in part by NSF grant #DMS 9800786, the Fulbright Foundation, and the Institute of Mathematics at The Hebrew University of Jerusalem.     

Approximations and Lower Bounds for the Length of Minimal Euclidean Steiner Trees

We give a new lower bound on the length of the minimal Steiner tree with a given topology joining given terminals in Euclidean space, in terms of toroidal images. The lower bound is equal to the length when the topology is full. We use the lower bound to prove bounds on the “error” e in the length of an approximate Steiner tree, in terms of the maximum deviation d of an interior angle of the tree from 120°. Such bounds are useful for validating algorithms computing minimal Steiner trees. In addition we give a number of examples illustrating features of the relationship between e and d, and make a conjecture which, if true, would somewhat strengthen our bounds on the error. J. H. Rubinstein, J. Weng: Research supported by the Australian Research Council N. Wormald: Research supported by the Australian Research Council and the Canada Research Chairs Program. Research partly carried out while the author was in the Department of Mathematics and Statistics, University of Melbourne     

Attractor for lattice system of dissipative Zakharov equation

We consider the asymptotic behavior of solutions of an infinite lattice dynamical system of dissipative Zakharov equation. By introducing new weight inner product and norm in the space and establishing uniform estimate on ＂Tail End＂ of solutions, we overcome some difficulties caused by the lack of Sobolev compact embedding under infinite lattice system, and prove the existence of the global attractor; then by using element decomposition and the covering property of a polyhedron in the finite-dimensional space, we obtain an upper bound for the Kolmogorov ε-entropy of the global attractor; finally, we present the upper semicontinuity of the global attractor.     

Copulas: Tales and facts

“But he does not wear any clothes” said the little child in Hans Christian Andersen’s “The Emperor’s New Clothes.”Mikosch’s research is partially supported by the Danish Research Council (SNF) GrantNo 21-04-0400. This is a discussion paper which was initiated at the 4th InternationalConference on Extreme Value Analysis in Gothenburg, 15–19 August, 2005; see.     

On deformations of <Emphasis Type="Italic">F</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript> in compact Lie groups

We study some properties of the varieties of deformations of free groups in compact Lie groups. In particular, we prove a conjecture of Margulis and Soifer about the density of non-virtually free points in such variety, and a conjecture of Goldman on the ergodicity of the action of Aut(F _n ) on such variety when n ≥ 3. The author was partially supported by NSF grant DMS-0404557, BSF grant 2004010, and the ‘Finite Structures’ Marie Curie Host Fellowship, carried out at the Alfréd Rényi Institute of Mathematics in Budapest.     

Beth’s theorem in cardinality logics

We prove that the Beth definability theorem fails for a comprehensive class of first-order logics with cardinality quantifiers. In particular, we give a counterexample to Beth’s theorem forL(Q), which is finitary first-order logic (with identity) augmented with the quantifier “there exists uncountably many”. This research was partially supported by NSF GP29254.     

Vector Ekeland’s variational principle in an <Emphasis Type="Italic">F</Emphasis>-type topological space

In this paper, we first give a vector-valued version of Brézis and Browder’s scalar general principle. We then apply the vector-valued general principle to study a vector Ekeland’s variational principle in a F-type topological space, which unifies and improves the corresponding vector-valued Ekeland’s variational results in complete metric space. This project was partially supported by the Research Grants Council of Hong Kong (BG771) and National Natural Science Foundation of China (70501015, 70401006).     

On regular semiovals in PG(2,q)

In this paper we prove that a point set in PG(2,q) meeting every line in 0, 1 or r points and having a unique tangent at each of its points is either an oval or a unital. This answers a question of Blokhuis and Szőnyi [1]. Research was partially supported by OTKA Grants T 043758, F 043772; the preparation of the final version was supported by OTKA Grant T 049662 and TéT grant E-16/04.