On the Hardness of Computing Intersection,Union and Minkowski Sum of Polytopes

For polytopes P ₁,P ₂⊂ℝ ^d , we consider the intersection P ₁∩P ₂, the convex hull of the union CH(P ₁∪P ₂), and the Minkowski sum P ₁+P ₂. For the Minkowski sum, we prove that enumerating the facets of P ₁+P ₂ is NP-hard if P ₁ and P ₂ are specified by facets, or if P ₁ is specified by vertices and P ₂ is a polyhedral cone specified by facets. For the intersection, we prove that computing the facets or the vertices of the intersection of two polytopes is NP-hard if one of them is given by vertices and the other by facets. Also, computing the vertices of the intersection of two polytopes given by vertices is shown to be NP-hard. Analogous results for computing the convex hull of the union of two polytopes follow from polar duality. All of the hardness results are established by showing that the appropriate decision version, for each of these problems, is NP-complete.     

Embeddings of bipartite graphs

If G is a bipartite graph with bipartition A, B then let G_m,n(A, B) be obtained from G by replacing each vertex a of A by an independent set a₁, …, a_m, each vertex b of B by an independent set b₁,…, b_n, and each edge ab of G by the complete bipartite graph with edges a_ib_j (1 ≤ i ≤ m and 1 ≤ j ≤ n). Whenever G has certain types of spanning forests, then cellular embeddings of G in surfaces S may be lifted to embeddings of G_m,n(A, B) having faces of the same sizes as those of G in S. These results are proved by the technique of “excess-current graphs.” They include new genus embeddings for a large class of bipartite graphs.     

Localisation in rings equipped with a solvable Lie algebra action

Let k be an algebraically closed uncountable field of characteristic 0,g a finite dimensional solvable k-Lie algebraR a noetherian k-algebra on which g acts by k-derivationsU(g) the enveloping algebra of g,A=R*g the crossed product of R by U(g)P a prime ideal of A and Ω(P) the clique of P. Suppose that the prime ideals of the polynomial ring R[x] are completely prime. If R is g-hypernormal, then Ω(P) is classical. Denote by A_T the localised ring and let M be a primitive ideal of A_T Set Q=P∩R In this note, we show that if R is a strongly (R,g)-admissible integral domain and if QR_Q is generated by a regular g-centralising set of elements, then

(1)M is generated by a regular g-semi-invariant normalising set of elements of cardinald = dim (R_Q 0 + ∣X_A (P)∣

(2)d gldim(A_T ) = Kdim(A_T ) = ht(M) = ht(P).     

A Class of 2-Colorable Orthogonal Double Covers of Complete Graphs by Hamiltonian Paths

K _n by a graph G is a collection ? of n spanning subgraphs of K _n , all isomorphic to G, such that any two members of ? share exactly one edge and every edge of K _n is contained in exactly two members of ?. In the 1980's Hering posed the problem to decide the existence of an ODC for the case that G is an almost-hamiltonian cycle, i.e. a cycle of length n−1. It is known that the existence of an ODC of K _n by a hamiltonian path implies the existence of ODCs of K _4n and K _16n , respectively, by almost-hamiltonian cycles. Horton and Nonay introduced 2-colorable ODCs and showed: If for n≥3 and a prime power q≥5 there are an ODC of K _n by a hamiltonian path and a 2-colorable ODC of K _q by a hamiltonian path, then there is an ODC of K _qn by a hamiltonian path. We construct 2-colorable ODCs of K _n and K _2n , respectively, by hamiltonian paths for all odd square numbers n≥9. Received: January 27, 2000     

Automorphisms of Relatively Free Nilpotent Lie Algebras

Let L be a relatively free nilpotent Lie algebra over ? of rank n and class c, with n ≥ 2; freely generated by a set 𝒵. Give L the structure of a group, denoted by R, by means of the Baker–Campbell–Hausdorff formula. Let G be the subgroup of R generated by the set 𝒵 and N _Aut(L)(G) the normalizer in Aut(L) of the set G. We prove that the automorphism group of L is generated by GL _n (?) and N _Aut(L)(G). Let H be a subgroup of finite index in Aut(G) generated by the tame automorphisms and a finite subset X of IA-automorphisms with cardinal s. We construct a set Y consisting of s + 1 IA-automorphisms of L such that Aut(L) is generated by GL _n (?) and Y. We apply this particular method to construct generating sets for the automorphism groups of certain relatively free nilpotent Lie algebras.     

Equations of Mathematical Physics and Compositions of Brownian and Cauchy Processes

We consider different types of processes obtained by composing Brownian motion B(t), fractional Brownian motion B _H (t) and Cauchy processes C(t) in different manners. We study also multidimensional iterated processes in ? ^d , like, for example, (B ₁(|C(t)|),…, B _d (|C(t)|)) and (C ₁(|C(t)|),…, C _d (|C(t)|)), deriving the corresponding partial differential equations satisfied by their joint distribution. We show that many important partial differential equations, like wave equation, equation of vibration of rods, higher-order heat equation, are satisfied by the laws of the iterated processes considered in the work. Similarly, we prove that some processes like C(|B ₁(|B ₂(…|B _n+1(t)|…)|)|) are governed by fractional diffusion equations.     

Lattices Generated by Orbits of Flats Under Finite Affine Groups

Let AG(n, _q ) be the n-dimensional affine space over  _q . For a given integer m with 0 ≤ m ≤ n, all m-flats form an orbit, denoted by ?(m,n), under the action of the affine group AGL _n ( _q ) of AG(n, _q ). Denote the set of all intersections of m-flats in ?(m,n) by ?(m,n). By ordering ?(m,n) by ordinary or reverse inclusion, two classes of lattices are obtained. This article discusses their geometricity, and computes their character polynomials.     

Hitting times for random walks on subdivision and triangulation graphs

Let G be a connected graph. The subdivision graph of G, denoted by S(G), is the graph obtained from G by inserting a new vertex into every edge of G. The triangulation graph of G, denoted by R(G), is the graph obtained from G by adding, for each edge uv, a new vertex whose neighbours are u and v. In this paper, we first provide complete information for the eigenvalues and eigenvectors of the probability transition matrix of a random walk on S(G) (res. R(G)) in terms of those of G. Then we give an explicit formula for the expected hitting time between any two vertices of S(G) (res. R(G)) in terms of those of G. Finally, as applications, we show that, the relations between the resistance distances, the number of spanning trees and the multiplicative degree-Kirchhoff index of S(G) (res. R(G)) and G can all be deduced from our results directly.     

Almost sure exponential stabilization by stochastic feedback control based on discrete-time observations

Since Mao initiated the study of stabilization of ordinary differential equations (ODEs) by stochastic feedback controls based on discrete-time state observations in 2016, no more work on this intriguing topic has been reported. This article investigates how to stabilize a given unstable linear non-autonomous ODE by controller σ(t)x(δ_t)dB(t), and how to stabilize an unstable nonlinear hybrid SDE by controller G(r(δ_t))x(δ_t)dB(t), where δ_t represents time points of observation with sufficiently small observation interval, B(t) is a Brownian motion and r(t) is the Markov Chain, in the sense of pth moment (0 < p < 1) and almost sure exponential stability.     

On Genuine Bernstein–Durrmeyer Operators

We continue the studies on the so–called genuine Bernstein–Durrmeyer operators U _n by establishing a recurrence formula for the moments and by investigating the semigroup T(t) approximated by U _n . Moreover, for sufficiently smooth functions the degree of this convergence is estimated. We also determine the eigenstructure of U _n , compute the moments of T(t) and establish asymptotic formulas. Received: January 26, 2007.     

Extensions and biextensions of locally constant group schemes,tori and abelian schemes

Let S be a scheme. We compute explicitly the group of homomorphisms, the S-sheaf of homomorphisms, the group of extensions, and the S-sheaf of extensions involving locally constant S-group schemes, abelian S-schemes, and S-tori. Using the obtained results, we study the categories of biextensions involving these geometrical objects. In particular, we prove that if G _i (for i = 1, 2, 3) is an extension of an abelian S-scheme A _i by an S-torus T _i , the category of biextensions of (G ₁, G ₂) by G ₃ is equivalent to the category of biextensions of the underlying abelian S-schemes (A ₁, A ₂) by the underlying S-torus T ₃.      

Generalisation des fonctions analytiques hyperboliques

We generalize the results previously given [1], by puting u = a x + ɛ b y by (a and b are real and positive, ɛ is a number of Clifford not real having a square equal to 1. Consider x and y being the coordinates of a point M, the axises being rectangular). The analytic functions f (u) are defined by

A note on homomorphic images, subalgebras and various products

Let I, H, S, P, P_fin, P_f , P_u, P_s be the usual operators on classes of algebras of the same type (P, P_fin, P_f, P_u, P_s are respectively for direct, finite, filtered, ultra and subdirect products). The partially ordered monoid generated by the operators H, S, P with respect to composition of operators, I as an identity element, and natural ordering between operators is described by Pigozzi (Algebra Universalis 2 (1972), 346–353). The aim of this note is to describe the partially ordered monoids generated by H, S, P_u and by H, S, P_s and as well to summarize known results on the partially ordered monoids of operators generated by H, S and some of the above introduced products.Dedicated to the memory of Aleksandar PopoviReceived April 1, 2001; accepted in final form July 11, 2004.     

Extremal cover times for random walks on trees

Let C_ν(T) denote the “cover time” of the tree T from the vertex v, that is, the expected number of steps before a random walk starting at v hits every vertex of T. Asymptotic lower bounds for C_ν(T) (for T a tree on n vertices) have been obtained recently by Kahn, Linial, Nisan and Saks, and by Devroye and Sbihi; here, we obtain the exact lower bound (approximately 2n In n) by showing that C_ν(T) is minimized when T is a star and v is one of its leaves. In addition, we show that the time to cover all vertices and then return to the starting point is minimized by a star (beginning at the center) and maximized by a path (beginning at one of the ends).     

Hausdorff measure of uniform self-similar fractals

Let d ≥ 1 be an integer and E a self-similar fractal set, which is the attractor of a uniform contracting iterated function system (UIFS) on R ^d . Denote by D the Hausdorff dimension, by H ^D (E) the Hausdorff measure and by diam(E) the diameter of E. If the UIFS is parametrised by its contracting factor c, while the set ω of fixed points of the UIFS does not depend on c, we will show the existence of a positive constant depending only on ω, such that the Hausdorff dimension is smaller than one and H ^D (E) = diam(E) ^D if c is smaller than this constant. We apply our result to modified versions of various classical fractals. Moreover, we present a parametrised UIFS, where ω depends on c and show the inequatily H ^D (E) < diam(E) ^D , if c is small enough.     

Topological properties of the multifunction space <Emphasis Type="Italic">L</Emphasis>(<Emphasis Type="Italic">X</Emphasis>) of cusco maps

A set-valued mapping F from a topological space X to a topological space Y is called a cusco map if F is upper semicontinuous and F(x) is a nonempty, compact and connected subset of Y for each x ∈ X. We denote by L(X), the space of all subsets F of X × ℝ such that F is the graph of a cusco map from the space X to the real line ℝ. In this paper, we study topological properties of L(X) endowed with the Vietoris topology. The second author is supported by the SPM fellowship awarded by the Council of Scientific and Industrial Research, India.     

On 2-Detour Subgraphs of the Hypercube

A spanning subgraph H of a graph G is a 2-detour subgraph of G if for each x, y ∈ V(G), d _H (x, y) ≤ d _G (x, y) + 2. We prove a conjecture of Erdős, Hamburger, Pippert, and Weakley by showing that for some positive constant c and every n, each 2-detour subgraph of the n-dimensional hypercube Q _n has at least clog₂ n · 2 ⁿ edges. József Balogh: Research supported in part by NSF grants DMS-0302804, DMS-0603769 and DMS-0600303, UIUC Campus Reseach Board #06139 and #07048, and OTKA 049398. Alexandr Kostochka: Research supported in part by NSF grants DMS-0400498 and DMS-0650784, and grant 06-01-00694 of the Russian Foundation for Basic Research.     

A generalized Turán problem in random graphs

We study a generalization of the Turán problem in random graphs. Given graphs T and H, let ex(G(n,p),T,H) be the largest number of copies of T in an H‐free subgraph of G(n,p). We study the threshold phenomena arising in the evolution of the typical value of this random variable, for every H and every 2‐balanced T. Our results in the case when m₂(H) > m₂(T) are a natural generalization of the Erd?s‐Stone theorem for G(n,p), proved several years ago by Conlon‐Gowers and Schacht; the case T = K_m was previously resolved by Alon, Kostochka, and Shikhelman. The case when m₂(H) ≤ m₂(T) exhibits a more complex behavior. Here, the location(s) of the (possibly multiple) threshold(s) are determined by densities of various coverings of H with copies of T and the typical value(s) of ex(G(n,p),T,H) are given by solutions to deterministic hypergraph Turán‐type problems that we are unable to solve in full generality.     

Procreating tiles of double commutative-step digraphs

Double commutative-step digraph generalizes the double-loop digraph. A double commutative-step digraph can be represented by an L-shaped tile, which periodically tessellates the plane. Given an initial tile L（l, h, x, y）, Aguil5 et al. define a discrete iteration L（p） = L（l ＋ 2p, h ＋ 2p, x ＋ p, y ＋ p）, p = 0, 1, 2,..., over L-shapes （equivalently over double commutative-step digraphs）, and obtain an orbit generated by L（l, h, x,y）, which is said to be a procreating k-tight tile if L（p）（p = 0, 1, 2, ~ ~ ~ ） are all k-tight tiles. They classify the set of L-shaped tiles by its behavior under the above-mentioned discrete dynamics and obtain some procreating tiles of double commutative-step digraphs. In this work, with an approach proposed by Li and Xu et al., we define some new discrete iteration over L-shapes and classify the set of tiles by the procreating condition. We also propose some approaches to find infinite families of realizable k-tight tiles starting from any realizable k-tight L-shaped tile L（l, h, x, y）, 0 ≤ y - x ≤ 2k ＋ 2. As an example, we present an infinite family of 3-tight optimal double-loop networks to illustrate our approaches.     

The number of labeled graphs placeable by a given permutation

Let S be a finite set and σ a permutation on S. The permutation σ* on the set of 2-subsets of S is naturally induced by σ. Suppose G is a graph and V(G), E(G) are the vertex set, the edge set, respectively. Let V(G) = S. If E(G) and σ*(E(G)), the image of E(G) by σ*, have no common element, then G is said to be placeable by σ. This notion is generalized as follows. If any two sets of {E(G), (σ¹)*(E(G)),…,(σ^l−1)* (E(G))} have no common element, then G is said to be I-placeable by σ. In this paper, we count the number of labeled graphs which are I-placeable by a given permutation. At first, we introduce the interspaced Ith Fibonacci and Lucas numbers. When I = 2 these numbers are the ordinary Fibonacci and Lucas numbers. It is known that the Fibonacci and Lucas numbers are rounded powers. We show that the interspaced Ith Fibonacci and Lucas numbers are also rounded powers when I = 3. Next, we show the number of labeled graphs which are I-placeable by a given permutation is a product of the interspaced Ith Lucas numbers. Finally, using a property of the generalized binomial series, we count the number of labeled graphs of size k which are I-placeable by σ. © 1996 John Wiley & Sons, Inc.