Some properties of m-th root Finsler metrics

We prove that every m-th root metric with isotropic mean Berwald curvature reduces to a weakly Berwald metric. Then we show that an m-th root metric with isotropic mean Landsberg curvature is a weakly Landsberg metric. We find necessary and sufficient condition under which conformal β-change of anm-th root metric is locally dually flat. Finally, we prove that the conformal β-change of locally projectively flat m-th root metrics are locally Minkowskian.     

The neighborhood complex of a random graph

For a graph G, the neighborhood complex N[G] is the simplicial complex having all subsets of vertices with a common neighbor as its faces. It is a well-known result of Lovász that if ‖N[G]‖ is k-connected, then the chromatic number of G is at least k+3.We prove that the connectivity of the neighborhood complex of a random graph is tightly concentrated, almost always between 1/2 and 2/3 of the expected clique number. We also show that the number of dimensions of nontrivial homology is almost always small, O(logd), compared to the expected dimension d of the complex itself.     

Obtainable sizes of topologies on finite sets

We study the smallest possible number of points in a topological space having k open sets. Equivalently, this is the smallest possible number of elements in a poset having k order ideals. Using efficient algorithms for constructing a topology with a prescribed size, we show that this number has a logarithmic upper bound. We deduce that there exists a topology on n points having k open sets, for all k in an interval which is exponentially large in n. The construction algorithms can be modified to produce topologies where the smallest neighborhood of each point has a minimal size, and we give a range of obtainable sizes for such topologies.     

On crossing numbers of geometric proximity graphs

Let P be a set of n points in the plane. A geometric proximity graph on P is a graph where two points are connected by a straight-line segment if they satisfy some prescribed proximity rule. We consider four classes of higher order proximity graphs, namely, the k-nearest neighbor graph, the k-relative neighborhood graph, the k-Gabriel graph and the k-Delaunay graph. For k=0 (k=1 in the case of the k-nearest neighbor graph) these graphs are plane, but for higher values of k in general they contain crossings. In this paper, we provide lower and upper bounds on their minimum and maximum number of crossings. We give general bounds and we also study particular cases that are especially interesting from the viewpoint of applications. These cases include the 1-Delaunay graph and the k-nearest neighbor graph for small values of k.     

On Superconnectivity of (4, g)-Cages

A (k, g)-cage is a graph that has the least number of vertices among all k-regular graphs with girth g. It has been conjectured (Fu et?al. in J. Graph Theory, 24:187?C191, 1997) that all (k, g)-cages are k-connected for every k??? 3. A k-connected graph G is called superconnected if every k-cutset S is the neighborhood of some vertex. Moreover, if G?S has precisely two components, then G is called tightly superconnected. In this paper, we prove that every (4, g)-cage is tightly superconnected when g ???11 is odd.     

Approximation properties of sums of the form Σ k λ k h(λ k z)

A method for approximating functions f analytic in a neighborhood of the point z = 0 by finite sums of the form Σ _k λ _k h(λ _k z) is proposed, where h is a chosen function analytic on the unit disk and the approximation is carried out by choosing the complex numbers λ _k = λ _k (f). Some applications to numerical analysis are given.     

Long range scattering for the modified Schrödinger map in two space dimensions

We study the asymptotic behaviour in time of solutions and the theory of scattering for the modified Schrödinger map in two space dimensions. We solve the Cauchy problem with large finite initial time, up to infinity in time, and we determine the asymptotic behaviour in time of the solutions thereby obtained. As a by product, we obtain global existence for small data in Hk∩FHk with k>1. We also solve the Cauchy problem with infinite initial time, namely we construct solutions defined in a neighborhood of infinity in time, with prescribed asymptotic behaviour of the previous type.     

Partitioning a Graph into Global Powerful k-Alliances

A set S of vertices of a graph is a defensive k-alliance if every vertex ${v\in S}$ has at least k more neighbors in S than it has outside of S. Analogously, a set S is an offensive k-alliance if every vertex in the neighborhood of S has at least k more neighbors in S than it has outside of S. Also, a powerful k-alliance is a set S of vertices of the graph, which is both defensive k-alliance and offensive (k?+?2)-alliance. A powerful k-alliance is called global if it is a dominating set. In this paper we show that for k?≥ 0, no graph is partitionable into global powerful k-alliances and, for k?≤ ?1, we obtain upper bounds on the maximum number of sets belonging to a partition of a graph into global powerful k-alliances. In addition, we study the close relationships that exist between partitions of a Cartesian product graph, Γ₁?× Γ₂, into (global) powerful (k ₁?+?k ₂)-alliances and partitions of Γ _i into (global) powerful k _i -alliances, ${i\in \{1,2\}}$ .     

Disproof of the neighborhood conjecture with implications to SAT

We study a special class of binary trees. Our results have implications on Maker/Breaker games and SAT: We disprove a conjecture of Beck on positional games and construct an unsatisfiable k-CNF formula with few occurrences per variable, thereby improving a previous result by Hoory and Szeider and showing that the bound obtained from the Lovász Local Lemma is tight up to a constant factor. A (k, s)-CNF formula is a boolean formula in conjunctive normal form where every clause contains exactly k distinct literals and every variable occurs in at most s clauses. The (k, s)-SAT problem is the satisfiability problem restricted to (k, s)-CNF formulas. Kratochvíl, Savický and Tuza showed that for every k≥3 there is an integer f(k) such that every (k, f(k))-CNF formula is satisfiable, but (k, f(k) + 1)-SAT is already NP-complete (it is not known whether f(k) is computable). Kratochvíl, Savický and Tuza also gave the best known lower bound $f(k) = \Omega \left( {\tfrac{{2^k }} {k}} \right)$ , which is a consequence of the Lovász Local Lemma. We prove that, in fact, $f(k) = \Theta \left( {\tfrac{{2^k }} {k}} \right)$ , improving upon the best known upper bound $O\left( {(\log k) \cdot \tfrac{{2^k }} {k}} \right)$ by Hoory and Szeider. Finally we establish a connection between the class of trees we consider and a certain family of positional games. The Maker/Breaker game we study is as follows. Maker and Breaker take turns in choosing vertices from a given n-uniform hypergraph $\mathcal{F}$ , with Maker going first. Maker’s goal is to completely occupy a hyperedge and Breaker tries to prevent this. The maximum neighborhood size of a hypergraph $\mathcal{F}$ is the maximal s such that some hyperedge of $\mathcal{F}$ intersects exactly s other hyperedges. Beck conjectures that if the maximum neighborhood size of $\mathcal{F}$ is smaller than 2 ^n?1 ? 1 then Breaker has a winning strategy. We disprove this conjecture by establishing, for every n≥3, the existence of an n-uniform hypergraph with maximum neighborhood size 3·2 ^n?3 where Maker has a winning strategy. Moreover, we show how to construct, for every n, an n-uniform hypergraph with maximum degree at most $\frac{{2^{n + 2} }} {n}$ where Maker has a winning strategy. In addition we show that each n-uniform hypergraph with maximum degree at most $\frac{{2^{n - 2} }} {{en}}$ has a proper halving 2-coloring, which solves another open problem posed by Beck related to the Neighborhood Conjecture.     

Binary central relations and submaximal clones determined by nontrivial equivalence relations

Let k ≥ 3, θ a nontrivial equivalence relation on E _k = {0, . . . ,k – 1}, and ρ a binary central relation on E _k (a reflexive graph with a vertex having E _k as its neighborhood). It is known that the clones Pol θ and Pol ρ (of operations on E _k preserving θ and ρ, respectively) are maximal clones; i.e., covered by the largest clone in the inclusion-ordered lattice of clones on E _k . In this paper, we give the classification of all binary central relations ρ on E _k such that the clone Pol θ ∩ Pol ρ is maximal in Pol θ.     

Homotopy type of neighborhood complexes of Kneser graphs, $$\varvec{KG_{2,k}}$$

Schrijver (Nieuw Archief voor Wiskunde, 26(3) (1978) 454–461) identified a family of vertex critical subgraphs of the Kneser graphs called the stable Kneser graphs \(SG_{n,k}\). Björner and de Longueville (Combinatorica 23(1) (2003) 23–34) proved that the neighborhood complex of the stable Kneser graph \(SG_{n,k}\) is homotopy equivalent to a k-sphere. In this article, we prove that the homotopy type of the neighborhood complex of the Kneser graph \(KG_{2,k}\) is a wedge of \((k+4)(k+1)+1\) spheres of dimension k. We construct a maximal subgraph \(S_{2,k}\) of \(KG_{2,k}\), whose neighborhood complex is homotopy equivalent to the neighborhood complex of \(SG_{2,k}\). Further, we prove that the neighborhood complex of \(S_{2,k}\) deformation retracts onto the neighborhood complex of \(SG_{2,k}\).     

Exposing Points on the Boundary of a Strictly Pseudoconvex or a Locally Convexifiable Domain of Finite 1-Type

We show that for any bounded domain \(\varOmega\subset\mathbb{C} ^{n}\) of 1-type 2k which is locally convexifiable at p∈bΩ, having a Stein neighborhood basis, there is a biholomorphic map \(f:\bar{\varOmega}\rightarrow\mathbb{C} ^{n} \) such that f(p) is a global extreme point of type 2k for \(f{(\overline{\varOmega})}\) .     

Finite-dimensional Perron effect of change of all values of characteristic exponents of differential systems

We obtain a finite-dimensional Perron effect of change of values λ ₁ ≤ … ≤ λ _n < 0 of all arbitrarily specified negative characteristic exponents of the n-dimensional system of linear approximation with infinitely differentiable bounded coefficients to arbitrarily specified, arranged in ascending order, values β _k ≥ λ _k , k = 1, …, n, of characteristic exponents of all nontrivial solutions of an n-dimensional nonlinear differential system with an infinitely differentiable perturbation of arbitrary order m > 1 of smallness in a neighborhood of the origin and growth outside it. Each value β _k is realized by all nontrivial solutions of the perturbed system issuing from the difference R ^k |R ^k?1 of embedded subspaces R ¹ ? R ² ? … ? R ⁿ .     

Analysis of Random Restart and Iterated Improvement for Global Optimization with Application to the Traveling Salesman Problem

The optimization method employing iterated improvement with random restart (I2R2) is studied. Associated with each instance of an I2R2 search is a fundamental polynomial, in which the coefficient p_k is the probability of starting a search k improvement steps from a local minimum. The positive root of f can be used to calculate the convergence and speedup properties of that instance.Since the coefficients of f are naturally related to the search, it is possible to estimate them online if an a priori estimate of the size of the goal basin is available, for example by analysis or prior experience. In this case, the runtime statistical estimate of converges many times faster than the estimates of the coefficients themselves.The foregoing is illustrated with an application to the traveling salesman problem (TSP) using the k-change as the improvement discipline. Among other things, it is shown that a k-change improvement can be affected by k 2-changes, that =1 for convex city sets, and that good estimates of can be made from a reduced TSP related to the given one.This research was partially supported by the National Sciences and Engineering Research Council of Canada (NSERC) in the form of a discovery grant. The authors thank the referees for helpful suggestions and timeliness.     

Upper bounds on the signed (k, k)-domatic number

Let G be a graph with vertex set V(G), and let f : V(G) → {?1, 1} be a two-valued function. If k ≥ 1 is an integer and ${\sum_{x\in N[v]} f(x) \ge k}$ for each ${v \in V(G)}$ , where N[v] is the closed neighborhood of v, then f is a signed k-dominating function on G. A set {f ₁,f ₂, . . . ,f _d } of distinct signed k-dominating functions on G with the property that ${\sum_{i=1}^d f_i(x) \le k}$ for each ${x \in V(G)}$ , is called a signed (k, k)-dominating family (of functions) on G. The maximum number of functions in a signed (k, k)-dominating family on G is the signed (k, k)-domatic number of G. In this article we mainly present upper bounds on the signed (k, k)-domatic number, in particular for regular graphs.     

The {k}-domatic number of a graph

For a positive integer k, a {k}-dominating function of a graph G is a function f from the vertex set V(G) to the set {0, 1, 2, . . . , k} such that for any vertex ${v\in V(G)}$ , the condition ${\sum_{u\in N[v]}f(u)\ge k}$ is fulfilled, where N[v] is the closed neighborhood of v. A {1}-dominating function is the same as ordinary domination. A set {f ₁, f ₂, . . . , f _d } of {k}-dominating functions on G with the property that ${\sum_{i=1}^df_i(v)\le k}$ for each ${v\in V(G)}$ , is called a {k}-dominating family (of functions) on G. The maximum number of functions in a {k}-dominating family on G is the {k}-domatic number of G, denoted by d _{k}(G). Note that d _{1}(G) is the classical domatic number d(G). In this paper we initiate the study of the {k}-domatic number in graphs and we present some bounds for d _{k}(G). Many of the known bounds of d(G) are immediate consequences of our results.     

Randers change of <Emphasis Type="Italic">m</Emphasis><Superscript>th</Superscript> root metric

The present paper deals with a Randers metric that has been derived after a particular β-change in the mth root metric. Various geometers such as [7], [9], [10] etc. have studied the mth root metric and its transformations. We have obtained some tensors and theorems holding the relation between the Finsler space equipped with the mth root metric and the one obtained after its Randers change.     

Perturbation from Dirichlet problem involving oscillating nonlinearities

In this paper we prove that if the potential has a suitable oscillating behavior in any neighborhood of the origin (respectively +∞), then under very mild conditions on the perturbation term g, for every k∈N there exists bk>0 such that

     

Stability estimates for h-p spectral element methods for elliptic problems

In a series of papers of which this is the first we study how to solve elliptic problems on polygonal domains using spectral methods on parallel computers. To overcome the singularities that arise in a neighborhood of the corners we use a geometrical mesh. With this mesh we seek a solution which minimizes a weighted squared norm of the residuals in the partial differential equation and a fractional Sobolev norm of the residuals in the boundary conditions and enforce continuity by adding a term which measures the jump in the function and its derivatives at inter-element boundaries, in an appropriate fractional Sobolev norm, to the functional being minimized. Since the second derivatives of the actual solution are not square integrable in a neighborhood of the corners we have to multiply the residuals in the partial differential equation by an appropriate power of r_k, where r_k measures the distance between the pointP and the vertexA _k in a sectoral neighborhood of each of these vertices. In each of these sectoral neighborhoods we use a local coordinate system (τ_k, θ_k) where τ_k = lnr_k and (r_k, θ_k) are polar coordinates with origin at A_k, as first proposed by Kondratiev. We then derive differentiability estimates with respect to these new variables and a stability estimate for the functional we minimize. In [6] we will show that we can use the stability estimate to obtain parallel preconditioners and error estimates for the solution of the minimization problem which are nearly optimal as the condition number of the preconditioned system is polylogarithmic inN, the number of processors and the number of degrees of freedom in each variable on each element. Moreover if the data is analytic then the error is exponentially small inN.