The negative cycles polyhedron and hardness of checking some polyhedral properties

Given a graph G=(V,E) and a weight function on the edges w:E→ℝ, we consider the polyhedron P(G,w) of negative-weight flows on G, and get a complete characterization of the vertices and extreme directions of P(G,w). Based on this characterization, and using a construction developed in Khachiyan et al. (Discrete Comput. Geom. 39(1–3):174–190, 2008), we show that, unless P=NP, there is no output polynomial-time algorithm to generate all the vertices of a 0/1-polyhedron. This strengthens the NP-hardness result of Khachiyan et al. (Discrete Comput. Geom. 39(1–3):174–190, 2008) for non 0/1-polyhedra, and comes in contrast with the polynomiality of vertex enumeration for 0/1-polytopes (Bussiech and Lübbecke in Comput. Geom., Theory Appl. 11(2):103–109, 1998). As further applications, we show that it is NP-hard to check if a given integral polyhedron is 0/1, or if a given polyhedron is half-integral. Finally, we also show that it is NP-hard to approximate the maximum support of a vertex of a polyhedron in ℝ ⁿ within a factor of 12/n.     

Groups with given properties of finite subgroups

Suppose that in every finite even order subgroup F of a periodic group G, the equality [u, x]² = 1 holds for any involution u of F and for an arbitrary element x of F. Then the subgroup I generated by all involutions in G is locally finite and is a 2-group. In addition, the normal closure of every subgroup of order 2 in G is commutative.     

Jensen’s functional equation on the symmetric group S<Subscript>n</Subscript>

Two natural extensions of Jensen’s functional equation on the real line are the equations f(xy) + f(xy ⁻¹) =  2f(x) and f(xy) + f(y ⁻¹ x) =  2f(x), where f is a map from a multiplicative group G into an abelian additive group H. In a series of papers (see Ng in Aequationes Math 39:85–99, 1990; Ng in Aequationes Math 58:311–320, 1999; Ng in Aequationes Math 62:143–159, 2001), Ng solved these functional equations for the case where G is a free group and the linear group GL_n(R), R=\mathbbZ,\mathbbR{{GL_n(R), R=\mathbb{Z},\mathbb{R}}} , is a quadratically closed field or a finite field. He also mentioned, without a detailed proof, in the above papers and in (see Ng in Aequationes Math 70:131–153, 2005) that when G is the symmetric group S _n , the group of all solutions of these functional equations coincides with the group of all homomorphisms from (S _n , ·) to (H, + ). The aim of this paper is to give an elementary and direct proof of this fact.     

（g, f）-Factorizations Randomly Orthogonal to a Subgraph in Graphs

Let G be a graph with vertex set V(G) and edge set E(G) and let g and f be two integervalued functions defined on V(G) such that 2k - 2 ≤g(x)≤f(x) for all x∈V(G). Let H be a subgraph of G with mk edges. In this paper, it is proved that every (mg m-1,mf-m 1)-graph G has (g, f)-factorizations randomly k-orthogonal to H under some special conditions.     

Leading coefficients of Kazhdan–Lusztig polynomials for Deodhar elements

We show that the leading coefficient of the Kazhdan–Lusztig polynomial P _x,w (q) known as μ(x,w) is always either 0 or 1 when w is a Deodhar element of a finite Weyl group. The Deodhar elements have previously been characterized using pattern avoidance in Billey and Warrington (J. Algebraic Combin. 13(2):111–136, [2001]) and Billey and Jones (Ann. Comb. [2008], to appear). In type A, these elements are precisely the 321-hexagon avoiding permutations. Using Deodhar’s algorithm (Deodhar in Geom. Dedicata 63(1):95–119, [1990]), we provide some combinatorial criteria to determine when μ(x,w)=1 for such permutations w. The author received support from NSF grants DMS-9983797 and DMS-0636297.     

Group algebras in which complements are summands

It is shown that (1) every almost self-injective group algebra is self-injective and (2) if the group algebra KG is continuous, then G is a locally finite group. Furthermore, it follows that the following assertions are equivalent: a CS group algebra KG is continuous; KG is principally self-injective; the group G is locally finite. __________ Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 11, No. 3, pp. 3–11, 2005.     

Compactifications and algebraic completions of limit groups

This paper considers the existence of nondiscrete embeddings Γ ↦ G, where Γ is an abstract limit group and G is topological group. Namely, it is shown that a locally compact group G that admits a nondiscrete nonabelian free subgroup F admits a nondiscrete copy of every nonabelian limit group L. In some cases, for instance if the F is of rank 2 and its closure in G is compact or semisimple algebraic, or if L is a surface group (as considered in [6]), L can be chosen with the same closure as F.     

Normal relatively convex subgroups of solvable orderable groups

Orderable solvable groups in which every relatively convex subgroup is normal are studied. If such a class is subgroup closed than it is precisely the class of solvable orderable groups which are locally of finite (Mal’tsev) rank. A criterion for an orderable metabelian group to have every relatively convex subgroup normal is given. Examples of an orderable solvable group G of length three with periodic G/G′ and of an orderable solvable group of length four with only one proper normal relatively convex subgroup are constructed. To the memory of N. Ya. Medvedev Supported by RFBR (project No. 03-01-00320). Translated from Algebra i Logika, Vol. 48, No. 3, pp. 291–308, May–June, 2009.     

Exact simulation of the stationary distribution of the FIFO M/G/c queue: the general case for <Emphasis Type="Italic">ρ</Emphasis><<Emphasis Type="Italic">c</Emphasis>

We present an exact simulation algorithm for the stationary distribution of customer delay for FIFO M/G/c queues in which ρ=λ/μ<c. In Sigman (J. Appl. Probab. 48A:209–216, 2011) an exact simulation algorithm was presented but only under the strong condition that ρ<1 (super stable case). We only assume that the service-time distribution G(x)=P(S≤x), x≥0, with mean 0<E(S)=1/μ<∞, and its corresponding equilibrium distribution $G_{e}(x)=\mu\int_{0}^{x} P(S>y)\,dy$G_{e}(x)=\mu\int_{0}^{x} P(S>y)\,dy are such that samples of them can be simulated. Unlike the methods used in Sigman (J. Appl. Probab. 48A:209–216, 2011) involving coupling from the past, here we use different methods involving discrete-time processes and basic regenerative simulation, in which, as regeneration points, we use return visits to state 0 of a corresponding random assignment (RA) model which serves as a sample-path upper bound.     

On constructible graphs,locally Helly graphs,and convexity

A (finite or infinite) graph G is constructible if there exists a well‐ordering ≤ of its vertices such that for every vertex x which is not the smallest element, there is a vertex y < x which is adjacent to x and to every neighbor z of x with z < x. Particular constructible graphs are Helly graphs and connected bridged graphs. In this paper we study a new class of constructible graphs, the class of locally Helly graphs. A graph G is locally Helly if, for every pair (x,y) of vertices of G whose distance is d ≥ 2, there exists a vertex whose distance to x is d ? 1 and which is adjacent to y and to all neighbors of y whose distance to x is at most d. Helly graphs are locally Helly, and the converse holds for finite graphs. Among different properties we prove that a locally Helly graph is strongly dismantable, hence cop‐win, if and only if it contains no isometric rays. We show that a locally Helly graph G is finitely Helly, that is, every finite family of pairwise non‐disjoint balls of G has a non‐empty intersection. We give a sufficient condition by forbidden subgraphs so that the three concepts of Helly graphs, of locally Helly graphs and of finitely Helly graphs are equivalent. Finally, generalizing different results, in particular those of Bandelt and Chepoi 1 about Helly graphs and bridged graphs, we prove that the Helly number h(G) of the geodesic convexity in a constructible graph G is equal to its clique number ω(G), provided that ω(G) is finite. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 280–298, 2003     

Principal bundles whose restriction to curves are trivial

Let k be an algebraically closed field and X a smooth projective variety defined over k. Let E_G be a principal G–bundle over X, where G is an algebraic group defined over k, with the property that for every smooth curve C in X the restriction of E_G to C is the trivial G–bundle. We prove that the principal G–bundle E_G over X is trivial. We also give examples of nontrivial principal bundle over a quasi-projective variety Y whose restriction to every smooth curve in Y is trivial.     

Groups with an element permuting with finitely many of its conjugates

We study the problem as to which is the cardinality of connected components of the graph Γ_α, defined as follows. Let G be a group and a an element of G. The vertex set V(Γ_α) of the graph is the conjugacy class of elements,Cl _G(a), and two vertices x and y of the graph Γ_α are bridged by an edge iff x=y. If the intersectionC _G(a)∩Cl _G(a) is finite, Γ_α is locally finite. We prove that connected components of the locally finite graph Γ_α are finite in some classes of groups. Supported by RFFR grant No. 94-01-01084. Translated fromAlgebra i Logika, Vol. 35, No. 5, pp. 543–551, September–October, 1996.     

On Compact Graphs

Let G be a finite simple graph with adjacency matrix A, and let P（A） be the convex closure of the set of all permutation matrices commuting with A. G is said to be compact if every doubly stochastic matrix which commutes with A is in P（A）. In this paper, we characterize 3-regular compact graphs and prove that if G is a connected regular compact graph, G - v is also compact, and give a family of almost regular compact connected graphs.     

Commutators in Residually Finite Groups

 The following result is proved. Let G be a residually finite group satisfying the identity ([x ₁, x ₂][x ₃, x ₄]) ⁿ  ≡ 1 for a positive integer n that is not divisible by p ² q ² for any distinct primes p and q. Then G′ is locally finite. Received 7 May 2001; in revised form 3 December 2001     

Symmetrized Induced Ramsey Theory

We prove induced Ramsey theorems in which the monochromatic induced subgraph satisfies that all members of a prescribed set of its partial isomorphisms extend to automorphisms of the colored graph (without requirement of preservation of colors). We consider vertex and edge colorings, and extensions of partial isomorphisms in the set of all partial isomorphisms between singletons as considered by Babai and Sós (European J Combin 6(2):101–114, 1985), the set of all finite partial isomorphisms as considered by Hrushovski (Combinatorica 12(4):411–416, 1992), Herwig (Combinatorica 15:365–371, 1995) and Herwig-Lascar (Trans Amer Math Soc 5:1985–2021, 2000), and the set of all total isomorphisms. We observe that every finite graph embeds into a finite vertex transitive graph by a so called bi-embedding, an embedding that is compatible with a monomorphism between the corresponding automorphism groups. We also show that every countable graph bi-embeds into Rado’s universal countable graph Γ.     

Two cancellative commutative congruences and group diagrams

Remmers (Adv. Math. 36:283–296, 1980) uses group diagrams in the Euclidean plane to demonstrate how equality in a semigroup S “mirrors” that inside the group G sharing the same presentation with S, when S satisfies Adyan’s condition—no cycles in the left/right graphs of the semigroup’s presentation. Goldstein and Teymouri (Semigroup Forum 47:299–304, 1993) introduce a conjugacy equivalence relation for semigroups S. By closely examining the geometry of annular group diagrams in the plane, they show how their equivalence relation mirrors conjugacy inside G, for S satisfying Adyan’s. In this article we introduce two cancellative commutative congruences. Following their leads, we examine the geometry of group diagrams on closed surfaces of higher genera to demonstrate how these congruences mirror equality inside two naturally associated Abelian quotient groups G/[G,G] and G/G ², respectively. In these instances we can drop Adyan’s condition.     

<Emphasis Type="Italic">C</Emphasis><Superscript>1+<Emphasis Type="Italic">α</Emphasis></Superscript>-Regularity for Two-Dimensional Almost-Minimal Sets in ℝ<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>

We give a new proof and a partial generalization of Jean Taylor’s result (Ann. Math. (2) 103(3), 489–539, 1976) that says that Almgren almost-minimal sets of dimension 2 in ℝ³ are locally C ^1+α -equivalent to minimal cones. The proof is rather elementary, but uses a local separation result proved in Ann. Fac. Sci. Toulouse 18(1), 65–246, 2009 and an extension of Reifenberg’s parameterization theorem (David et al. in Geom. Funct. Anal. 18, 1168–1235, 2008). The key idea is still that if X is the cone over an arc of small Lipschitz graph in the unit sphere, but X is not contained in a disk, we can use the graph of a harmonic function to deform X and substantially diminish its area. The local separation result is used to reduce to unions of cones over arcs of Lipschitz graphs. A good part of the proof extends to minimal sets of dimension 2 in ℝ ⁿ , but in this setting our final regularity result on E may depend on the list of minimal cones obtained as blow-up limits of E at a point.     

Domination in Graphs of Minimum Degree Five

Let G=(V,E) be a simple graph. A subset D⊆V is a dominating set of G, if for any vertex x ∈ V−D, there exists a vertex y ∈ D such that xy ∈ E. By using the so-called vertex disjoint paths cover introduced by Reed, in this paper we prove that every graph G on n vertices with minimum degree at least five has a dominating set of order at most 5n/14.     

Locality of the perimeter in Carnot groups and chain rule

In the class of Carnot groups, we study fine properties of sets of finite perimeter. Improving a recent result by Ambrosio–Kleiner–Le Donne, we show that the perimeter measure is local, i.e., that given any pair of sets of finite perimeter their perimeter measures coincide on the intersection of their essential boundaries. This solves a question left open in Ambrosio et al. (Calculus of variations: topics from mathematical heritage of Ennio De Giorgi. Quad Mat). As a consequence, we prove a general chain rule for BV functions in this setting.