Finsler metrics on symmetric cones

Let V be a simple Euclidean Jordan algebra with an associative inner product and let be the corresponding symmetric cone. Let be the compact symmetric space of all primitive idempotents of V. We show that the function s(a,b) defined by is a (the automorphism group of )-invariant complete metric on and it coincides with a natural Finsler distance on We also show that the metric s(a,b) (strictly) contracts any (strict) conformal compression of . Received: 24 May 1999 / in final form: 15 March 1999     

The dimension of the determinantal scheme vs (t,t,2) of the catalecticant matrix

Let T be a Gorenstein sequence of a graded artinian Gorenstein ring k[x ₀,x ₁,x ₂]/I We develop a dimension formula for PGor(T) in terms of the alignment character. Based on our formula, we find a very large component of V_s (t,t,2) when s=r_t-1+1 and t is large enough. This answers Diesel’s conjecture negatively. Further we show that V_s (t,t,2) is irreducible of dimension 3s-1 for s ≤t+1,t ≥ 2 and dim V_s (t,t,2)= 3s-1 for small s. Finally an algorithm to calculate dim V_s (t,t,2) is constructed, and we find the values of dim V_s (t,t,2) for t ≤ 16.     

A linear worst-case lower bound on the number of holes inside regions visible due to multiple diffuse reflections

It is known that the region V(s) of a simple polygon P, directly visible (illuminable) from an internal point s, is simply connected. Aronov et al. [2] established that the region V₁(s) of a simple polygon visible from an internal point s due to at most one diffuse reflection on the boundary of the polygon P, is also simply connected. In this paper we establish that the region V₂(s), visible from s due to at most two diffuse reflections may be multiply connected; we demonstrate the construction of an n-sided simple polygon with a point s inside it so that the region of P visible from s after at most two diffuse reflections is multiply connected. We also show that V₃(s), the region of P visible from s after at most three diffuse reflections, can have (n) holes.A part of this work was done when this author was visiting the University of Miami, Coral Gables, Florida, USA.     

Vertex coloring complete multipartite graphs from random lists of size 2

Let K_s×m be the complete multipartite graph with s parts and m vertices in each part. Assign to each vertex v of K_s×m a list L(v) of colors, by choosing each list uniformly at random from all 2-subsets of a color set C of size σ(m). In this paper we determine, for all fixed s and growing m, the asymptotic probability of the existence of a proper coloring φ, such that φ(v)∈L(v) for all v∈V(K_s×m). We show that this property exhibits a sharp threshold at σ(m)=2(s−1)m.     

Splitting Off Edges within a Specified Subset Preserving the Edge-Connectivity of the Graph

Splitting off a pair su, sv of edges in a graph G means the operation that deletes su and sv and adds a new edge uv. Given a graph G = (V + s, E) which is k-edge-connected (k ≥ 2) between vertices of V and a specified subset R  V, first we consider the problem of finding a longest possible sequence of disjoint pairs of edges sx, sy, (x ,y  R) which can be split off preserving k-edge-connectivity in V. If R = V and d(s) is even then a well-known theorem of Lovász asserts that a complete R-splitting exists, that is, all the edges connecting s to R can be split off in pairs. This is not the case in general. We characterize the graphs possessing a complete R-splitting and give a formula for the length of a longest R-splitting sequence. Motivated by the connection between splitting off results and connectivity augmentation problems we also investigate the following problem that we call the split completion problem: given G and R as above, find a smallest set F of new edges incident to s such that G′ = (V + s, E + F) has a complete R-splitting. We give a min-max formula for F as well as a polynomial algorithm to find a smallest F. As a corollary we show a polynomial algorithm which finds a solution of size at most k/2 + 1 more than the optimum for the following augmentation problem, raised in [[2]]: given a graph H = (V, E), an integer k ≥ 2, and a set R  V, find a smallest set F′ of new edges for which H′ = (V, E + F′) is k-edge-connected and no edge of F′ crosses R.     

Insertible vertices,neighborhood intersections,and hamiltonicity

Let G be a simple undirected graph of order n. For an independent set S ? V(G) of k vertices, we define the k neighborhood intersections S_i = {v ? V(G)\S|N(v) ∩ S| = i}, 1 ≦ i ≦ k, with s_i = |S_i|. Using the concept of insertible vertices and the concept of neighborhood intersections, we prove the following theorem.     

Discriminant loci of ample and spanned line bundles

Let (X,L,V) be a triplet where X is an irreducible smooth complex projective variety, L is an ample and spanned line bundle on X and V⊆H⁰(X,L) spans L. The discriminant locus D(X,V)⊂|V| is the algebraic subset of singular elements of |V|. We study the components of D(X,V) in connection with the jumping sets of (X,V), generalizing the classical biduality theorem. We also deal with the degree of the discriminant (codegree of (X,L,V)) giving some bounds on it and classifying curves and surfaces of codegree 2 and 3. We exclude the possibility for the codegree to be 1. Significant examples are provided.     

Centers to centroids in graphs

For S ? V(G) the S-center and S-centroid of G are defined as the collection of vertices u ∈ V(G) that minimize e_s(u) = max {d(u, v): v ∈ S} and d_s(u) = ∑_u∈S d(u, v), respectively. This generalizes the standard definition of center and centroid from the special case of S = V(G). For 1 ? k ?|V(G)| and u ∈ V(G) let r_k(u) = max {∑_s∈S d(u, s): S ? V(G), |S| = k}. The k-centrum of G, denoted C(G; k), is defined to be the subset of vertices u in G for which r_k(u) is a minimum. This also generalizes the standard definitions of center and centroid since C(G; 1) is the center and C(G; |V(G)|) is the centroid. In this paper the structure of these sets for trees is examined. Generalizations of theorems of Jordan and Zelinka are included.     

Extremal problems involving neighborhood unions

We examine several extremal problems for graphs satisfying the property |N(x) ∪ N(y)| ? s for every pair of nonadjacent vertices x, y ? V(G). In particular, values for s are found that ensure that the graph contains an s-matching, a 1-factor, a path of a specific length, or a cycle of a specific length.     

Long cycles passing through a specified path in a graph

For a graph G and an integer k ≥ 1, let ς_k(G) = d_G(v_i): {v₁, …, v_k} is an independent set of vertices in G}. Enomoto proved the following theorem. Let s ≥ 1 and let G be a (s + 2)-connected graph. Then G has a cycle of length ≥ min{|V(G)|, ς₂(G) − s} passing through any path of length s. We generalize this result as follows. Let k ≥ 3 and s ≥ 1 and let G be a (k + s − 1)-connected graph. Then G has a cycle of length ≥ min{|V(G)|, − s} passing through any path of length s. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 177–184, 1998     

Differentiability with respect to (t,s) of the parabolic evolution operator

We give further regularity results with respect to (t, s) for the evolution operatorG(t, s) of abstract parabolic initial value problems in general Banach space. Such results are then used to establish a representation formula for the solutions of parabolic initial-boundary value problems with nonvanishing data at the boundary.     

Hamilton cycles and closed trails in iterated line graphs

Let G be an undirected connected graph that is not a path. We define h(G) (respectively, s(G)) to be the least integer m such that the iterated line graph L^m(G) has a Hamiltonian cycle (respectively, a spanning closed trail). To obtain upper bounds on h(G) and s(G), we characterize the least integer m such that L^m(G) has a connected subgraph H, in which each edge of H is in a 3-cycle and V(H) contains all vertices of degree not 2 in L^m(G). We characterize the graphs G such that h(G) — 1 (respectively, s(G)) is greater than the radius of G.     

2-Normalization of lattices

Let τ be a type of algebras. A valuation of terms of type τ is a function v assigning to each term t of type τ a value v(t) ⩾ 0. For k ⩾ 1, an identity s ≈ t of type τ is said to be k-normal (with respect to valuation v) if either s = t or both s and t have value ⩾ k. Taking k = 1 with respect to the usual depth valuation of terms gives the well-known property of normality of identities. A variety is called k-normal (with respect to the valuation v) if all its identities are k-normal. For any variety V, there is a least k-normal variety N _k (V) containing V, namely the variety determined by the set of all k-normal identities of V. The concept of k-normalization was introduced by K. Denecke and S. L. Wismath in their paper (Algebra Univers., 50, 2003, pp.107–128) and an algebraic characterization of the elements of N _k (V) in terms of the algebras in V was given in (Algebra Univers., 51, 2004, pp. 395–409). In this paper we study the algebras of the variety N ₂(V) where V is the type (2, 2) variety L of lattices and our valuation is the usual depth valuation of terms. We introduce a construction called the 3-level inflation of a lattice, and use the order-theoretic properties of lattices to show that the variety N ₂(L) is precisely the class of all 3-level inflations of lattices. We also produce a finite equational basis for the variety N ₂(L). This research was supported by Research Project MSM6198959214 of the Czech Government and by NSERC of Canada.     

Bi‐arc graphs and the complexity of list homomorphisms

Given graphs G, H, and lists L(v) ? V(H), v ε V(G), a list homomorphism of G to H with respect to the lists L is a mapping f : V(G) → V(H) such that uv ε E(G) implies f(u)f(v) ε E(H), and f(v) ε L(v) for all v ε V(G). The list homomorphism problem for a fixed graph H asks whether or not an input graph G, together with lists L(v) ? V(H), v ε V(G), admits a list homomorphism with respect to L. In two earlier papers, we classified the complexity of the list homomorphism problem in two important special cases: When H is a reflexive graph (every vertex has a loop), the problem is polynomial time solvable if H is an interval graph, and is NP‐complete otherwise. When H is an irreflexive graph (no vertex has a loop), the problem is polynomial time solvable if H is bipartite and H is a circular arc graph, and is NP‐complete otherwise. In this paper, we extend these classifications to arbitrary graphs H (each vertex may or may not have a loop). We introduce a new class of graphs, called bi‐arc graphs, which contains both reflexive interval graphs (and no other reflexive graphs), and bipartite graphs with circular arc complements (and no other irreflexive graphs). We show that the problem is polynomial time solvable when H is a bi‐arc graph, and is NP‐complete otherwise. In the case when H is a tree (with loops allowed), we give a simpler algorithm based on a structural characterization. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 61–80, 2003     

The structure of the set of satisfying assignments for a random <Emphasis Type="Italic">k</Emphasis>-CNF

Let F _k (n, m) be a random k-CNF obtained by a random, equiprobable, and independent choice of m brackets from among all k-literal brackets on n variables. We investigate the structure of the set of satisfying assignments of F _k (n, m). A method is proposed for finding r(k, s)such that the probability of presence of ns-dimensional faces (0 < s < 1) in the set of satisfying assignments of the formula F _k s(n, r(k, s)n) goes to 1 as n goes to infinity. We prove the existence of a sequential threshold for the property of having ns-dimensional faces (0 < s < 1). In other words, there exists a sequence r _n (k, s) such that the probability of having an ns-dimensional face in the set of satisfying assignments of the formula F _k (n, r _n (k, s)(1 + d)n) goes to 0 for all d > 0 and to 1 for all d < 0. __________ Translated from Prikladnaya Matematika i Informatika, No. 26, pp. 61–95, 2007.     

Positive ground state of coupled systems of Schrödinger equations in involving critical exponential growth

In this paper, we study the existence of a positive ground state solution to the following coupled system of nonlinear Schrödinger equations: where the nonlinearities f₁(x,s) and f₂(x,s) are superlinear at infinity and have exponential critical growth of the Trudinger‐Moser type. The potentials V₁(x) and V₂(x) are nonnegative and satisfy a condition involving the coupling term λ(x), namely, λ(x)²<δ²V₁(x)V₂(x) for some 0<δ<1. For this purpose, we use the minimization technique over the Nehari manifold and strong maximum principle to get a positive ground state solution. Moreover, by using a bootstrap argument and L^q‐estimates, we get regularity and asymptotic behavior.     

Lower Bound of the Number of Maximum Genus Embeddings and Genus Embeddings of K 12s+7

In this paper, we study lower bound of the number of maximum orientable genus embeddings (or MGE in short) for a loopless graph. We show that a connected loopless graph of order n has at least \frac14^g_M(G)?_{v ? V(G)}(d(v)-1)!{\frac{1}{4^{\gamma_M(G)}}\prod_{v\in{V(G)}}{(d(v)-1)!}} distinct MGE’s, where γ _M (G) is the maximum orientable genus of G. Infinitely many examples show that this bound is sharp (i.e., best possible) for some types of graphs. Compared with a lower bound of Stahl (Eur J Combin 13:119–126, 1991) which concerns upper-embeddable graphs (i.e., embedded graphs with at most two facial walks), this result is more general and effective in the case of (sparse) graphs permitting relative small-degree vertices. We also obtain a similar formula for maximum nonorientable genus embeddings for general graphs. If we apply our orientable results to the current graph G _s of K _12s+7, then G _s has at least 2^3s distinct MGE’s.This implies that K _12s+7 has at least (22) ^s nonisomorphic cyclic oriented triangular embeddings for sufficient large s.     

Signed 2-independence in graphs

A function f : V→{−1,1} defined on the vertices of a graph G=(V,E) is a signed 2-independence function if the sum of its function values over any closed neighbourhood is at most one. That is, for every vV, f(N[v])1, where N[v] consists of v and every vertex adjacent to v. The weight of a signed 2-independence function is f(V)=∑f(v), over all vertices vV. The signed 2-independence number of a graph G, denoted α_s²(G), equals the maximum weight of a signed 2-independence function of G. In this paper, we establish upper bounds for α_s²(G) in terms of the order and size of the graph, and we characterize the graphs attaining these bounds. For a tree T, upper and lower bounds for α_s²(T) are established and the extremal graphs characterized. It is shown that α_s²(G) can be arbitrarily large negative even for a cubic graph G.     

Essential variables in hypersubstitutions

For a variety V of algebras of type , we consider the set M _i (V) of all hypersubstitutions such that the variable x _i is essential in the term (f) with respect to the variety V. We will give a complete answer to the question for which varieties V of type = (n) the set M _i (v) of hypersubstitutions forms a monoid. This is important since to every monoid of hypersubstitutions there corresponds a complete sublattice of the lattice of all varieties of algebras of the given type. For varieties of semigroups we get the monoid of all leftmost and all rightmost hypersubstitutions. Received December 2, 1998; accepted in final form December 18, 2000.