Groups of quasi-invariance and the Pontryagin duality

A Polish group G is called a group of quasi-invariance or a QI-group, if there exist a locally compact group X and a probability measure μ on X such that (1) there exists a continuous monomorphism ? from G into X with dense image, and (2) for each g∈X either g∈?(G) and the shift μg is equivalent to μ or g∉?(G) and μg is orthogonal to μ. It is proved that ?(G) is a σ-compact subset of X. We show that there exists a Polish non-locally quasi-convex (and hence nonreflexive) QI-group such that its bidual is not a QI-group. It is proved also that the bidual group of a QI-group may be not a saturated subgroup of X. It is constructed a reflexive non-discrete group topology on the integers.     

Formality theorem for Lie bialgebras and quantization of twists and coboundary r-matrices

Let (g,δ?) be a Lie bialgebra. Let (U?(g),Δ?) a quantization of (g,δ?) through Etingof-Kazhdan functor. We prove the existence of a L_∞-morphism between the Lie algebra C(g)=Λ(g) and the tensor algebra (without unit) T₊U=T₊(U?(g)[−1]) with Lie algebra structure given by the Gerstenhaber bracket. When s is a twist for (g,δ), we deduce from the formality morphism the existence of a quantum twist F. When (g,δ,r) is a coboundary Lie bialgebra, we get the existence of a quantization R of r.     

On the computation of the hull number of a graph

Let G be a graph. If u,v∈V(G), a u-vshortest path of G is a path linking u and v with minimum number of edges. The closed interval I[u,v] consists of all vertices lying in some u-v shortest path of G. For S⊆V(G), the set I[S] is the union of all sets I[u,v] for u,v∈S. We say that S is a convex set if I[S]=S. The convex hull of S, denoted I_h[S], is the smallest convex set containing S. A set S is a hull set of G if I_h[S]=V(G). The cardinality of a minimum hull set of G is the hull number of G, denoted by hn(G). In this work we prove that deciding whether hn(G)≤k is NP-complete.We also present polynomial-time algorithms for computing hn(G) when G is a unit interval graph, a cograph or a split graph.     

Partitioning graphs into complete and empty graphs

Given integers j and k and a graph G, we consider partitions of the vertex set of G into j+k parts where j of these parts induce empty graphs and the remaining k induce cliques. If such a partition exists, we say G is a (j,k)-graph. For a fixed j and k we consider the maximum order n where every graph of order n is a (j,k)-graph. The split-chromatic number of G is the minimum j where G is a (j,j)-graph. Further, the cochromatic number is the minimum j+k where G is a (j,k)-graph. We examine some relations between cochromatic, split-chromatic and chromatic numbers. We also consider some computational questions related to chordal graphs and cographs.     

Compact group actions on equivariant absolute neighborhood retracts and their orbit spaces

We apply equivariant joins to give a new and more transparent proof of the following result: if G is a compact Hausdorff group and X a G-ANR (respectively, a G-AR), then for every closed normal subgroup H of G, the H-orbit space X/H is a G/H-ANR (respectively, a G/H-AR). In particular, X/G is an ANR (respectively, an AR).     

Building blocks for the variety of absolute retracts

Given a graph H with a labelled subgraph G, a retraction of H to G is a homomorphism r:H→G such that r(x)=x for all vertices x in G. We call G a retract of H. While deciding the existence of a retraction to a fixed graph G is NP-complete in general, necessary and sufficient conditions have been provided for certain classes of graphs in terms of holes, see for example Hell and Rival.For any integer k?2 we describe a collection of graphs that generate the variety AR_k of graphs G with the property that G is a retract of H whenever G is a subgraph of H and no hole in G of size at most k is filled by a vertex of H. We also prove that AR_k⊂NUF_k+1, where NUF_k+1 is the variety of graphs that admit a near unanimity function of arity k+1.     

Frobenius splitting and geometry of G-Schubert varieties

Let X be an equivariant embedding of a connected reductive group G over an algebraically closed field k of positive characteristic. Let B denote a Borel subgroup of G. A G-Schubert variety in X is a subvariety of the form diag(G)⋅V, where V is a B×B-orbit closure in X. In the case where X is the wonderful compactification of a group of adjoint type, the G-Schubert varieties are the closures of Lusztig's G-stable pieces. We prove that X admits a Frobenius splitting which is compatible with all G-Schubert varieties. Moreover, when X is smooth, projective and toroidal, then any G-Schubert variety in X admits a stable Frobenius splitting along an ample divisors. Although this indicates that G-Schubert varieties have nice singularities we present an example of a nonnormal G-Schubert variety in the wonderful compactification of a group of type G₂. Finally we also extend the Frobenius splitting results to the more general class of R-Schubert varieties.     

Selection over classes of ordinals expanded by monadic predicates

A monadic formula ψ(Y) is a selector for a monadic formula φ(Y) in a structure M if ψ defines in M a unique subset P of the domain and this P also satisfies φ in M. If C is a class of structures and φ is a selector for ψ in every M∈C, we say that φ is a selector for φ over C.For a monadic formula φ(X,Y) and ordinals α≤ω₁ and δ<ω^ω, we decide whether there exists a monadic formula ψ(X,Y) such that for every P⊆αof order-type smaller thanδ, ψ(P,Y) selects φ(P,Y) in (α,<). If so, we construct such a ψ.We introduce a criterion for a class C of ordinals to have the property that every monadic formula φ has a selector over it. We deduce the existence of S⊆ω^ω such that in the structure (ω^ω,<,S) every formula has a selector.Given a monadic sentence π and a monadic formula φ(Y), we decide whether φ has a selector over the class of countable ordinals satisfying π, and if so, construct one for it.     

On the complexity of paths avoiding forbidden pairs

Given a graph G=(V,E), two fixed vertices s,t∈V and a set F of pairs of vertices (called forbidden pairs), the problem of a path avoiding forbidden pairs is to find a path from s to t that contains at most one vertex from each pair in F. The problem is known to be NP-complete in general and a few restricted versions of the problem are known to be in P. We study the complexity of the problem for directed acyclic graphs with respect to the structure of the forbidden pairs.We write x?y if and only if there exists a path from x to y and we assume, without loss of generality, that for every forbidden pair (x,y)∈F we have x?y. The forbidden pairs have a halving structure if no two pairs (u,v),(x,y)∈F satisfy v?x or v=x and they have a hierarchical structure if no two pairs (u,v),(x,y)∈F satisfy u?x?v?y. We show that the PAFP problem is NP-hard even if the forbidden pairs have the halving structure and we provide a surprisingly simple and efficient algorithm for the PAFP problem with the hierarchical structure.     

On iterates of fully closed absolutes

In this article we give a sufficient condition for a space X to have the fully closed absolute faX with the property fa(faX)=faX. An example of a compact space X such that the canonical mapping fa(α+1)X→fa(α)X (where α is a given ordinal) is not a homeomorphism is constructed. Also we give an example of a compact space X such that the canonical mapping faX→X is not a homeomorphism but for which there exists a homeomorphism faX→X.     

Interactions

Given a C^∗-algebra B, a closed ^*-subalgebra A⊆B, and a partial isometry S in B which interacts with A in the sense that S^∗aS=H(a)S^∗S and SaS^∗=V(a)SS^∗, where V and H are positive linear operators on A, we derive a few properties which V and H are forced to satisfy. Removing B and S from the picture we define an interaction as being a pair of maps (V,H) satisfying the derived properties. Starting with an abstract interaction (V,H) over a C^∗-algebra A we construct a C^∗-algebra B containing A and a partial isometry S whose interaction with A follows the above rules. We then discuss the possibility of constructing a covariance algebra from an interaction. This turns out to require a generalization of the notion of correspondences (also known as Pimsner bimodules) which we call a generalized correspondence. Such an object should be seen as an usual correspondence, except that the inner-products need not lie in the coefficient algebra. The covariance algebra is then defined using a natural generalization of Pimsner's construction of the celebrated Cuntz-Pimsner algebras.     

Domination by second countable spaces and Lindelöf Σ-property

Given a space M, a family of sets A of a space X is ordered by M if A={AK:K is a compact subset of M} and K⊂L implies AK⊂AL. We study the class M of spaces which have compact covers ordered by a second countable space. We prove that a space Cp(X) belongs to M if and only if it is a Lindelöf Σ-space. Under MA(ω₁), if X is compact and (X×X)\Δ has a compact cover ordered by a Polish space then X is metrizable; here Δ={(x,x):x∈X} is the diagonal of the space X. Besides, if X is a compact space of countable tightness and X²\Δ belongs to M then X is metrizable in ZFC.We also consider the class M^? of spaces X which have a compact cover F ordered by a second countable space with the additional property that, for every compact set P⊂X there exists F∈F with P⊂F. It is a ZFC result that if X is a compact space and (X×X)\Δ belongs to M^? then X is metrizable. We also establish that, under CH, if X is compact and Cp(X) belongs to M^? then X is countable.     

Minimum cost homomorphisms to semicomplete multipartite digraphs

For digraphs D and H, a mapping f:V(D)→V(H) is a homomorphism ofDtoH if uv∈A(D) implies f(u)f(v)∈A(H). For a fixed directed or undirected graph H and an input graph D, the problem of verifying whether there exists a homomorphism of D to H has been studied in a large number of papers. We study an optimization version of this decision problem. Our optimization problem is motivated by a real-world problem in defence logistics and was introduced recently by the authors and M. Tso.Suppose we are given a pair of digraphs D,H and a cost c_i(u) for each u∈V(D) and i∈V(H). The cost of a homomorphism f of D to H is ∑_u∈V(D)c_f(u)(u). Let H be a fixed digraph. The minimum cost homomorphism problem for H, MinHOMP(H), is stated as follows: For input digraph D and costs c_i(u) for each u∈V(D) and i∈V(H), verify whether there is a homomorphism of D to H and, if it does exist, find such a homomorphism of minimum cost. In our previous paper we obtained a dichotomy classification of the time complexity of when H is a semicomplete digraph. In this paper we extend the classification to semicomplete k-partite digraphs, k≥3, and obtain such a classification for bipartite tournaments.     

On then-cutset property

For a partially ordered setP and an elementx ofP, a subsetS ofP is called a cutset forx inP if every element ofS is noncomparable tox and every maximal chain ofP meets {x}∪S. We letc(P) denote the smallest integerk such that every elementx ofP has a cutsetS with ‖S‖?k: Ifc(P)?n we say thatP has then-cutset property. Our results bear on the following question: givenP, what is the smallestn such thatP can be embedded in a partially ordered set having then-cutset property? As usual, 2 ⁿ denotes the Boolean lattice of all subsets of ann-element set, andB _n denotes the set of atoms and co-atoms of 2 ⁿ . We establish the following results: (i) a characterization, by means of forbidden configurations, of whichP can be embedded in a partially ordered set having the 1-cutset property; (ii) ifP contains a copy of 2 ⁿ , thenc(P)?2^[n/2]?1; (iii) for everyn>3 there is a partially ordered setP containing 2 ⁿ such thatc(P)<c(2 ⁿ ); (iv) for every positive integern there is a positive integerN such that, ifB _m is contained in a partially ordered set having then-cutset property, thenm?N.     

A Sard theorem for tame set-valued mappings

If F is a set-valued mapping from Rn into Rm with closed graph, then y∈Rm is a critical value of F if for some x with y∈F(x), F is not metrically regular at (x,y). We prove that the set of critical values of a set-valued mapping whose graph is a definable (tame) set in an o-minimal structure containing additions and multiplications is a set of dimension not greater than m−1 (respectively a σ-porous set). As a corollary of this result we get that the collection of asymptotically critical values of a set-valued mapping with a semialgebraic graph has dimension not greater than m−1. We also give an independent proof of the fact that a definable continuous real-valued function is constant on components of the set of its subdifferentiably critical points.     

Perfect dexagon triple systems with given subsystems

The graph consisting of the six triples (or triangles) {a,b,c}, {c,d,e}, {e,f,a}, {x,a,y}, {x,c,z}, {x,e,w}, where a,b,c,d,e,f,x,y,z and w are distinct, is called a dexagon triple. In this case the six edges {a,c}, {c,e}, {e,a}, {x,a}, {x,c}, and {x,e} form a copy of K₄ and are called the inside edges of the dexagon triple. A dexagon triple system of order v is a pair (X,D), where D is a collection of edge disjoint dexagon triples which partitions the edge set of 3K_v. A dexagon triple system is said to be perfect if the inside copies of K₄ form a block design. In this note, we investigate the existence of a dexagon triple system with a subsystem. We show that the necessary conditions for the existence of a dexagon triple system of order v with a sub-dexagon triple system of order u are also sufficient.     

The interval function of a connected graph and road systems

Let V be a finite nonempty set. In this paper, a road system on V (as a generalization of the set of all geodesics in a connected graph G with V(G)=V) and an intervaloid function on V (as a generalization of the interval function (in the sense of Mulder) of a connected graph G with V(G)=V) are introduced. A natural bijection of the set of all intervaloid functions on V onto the set of all road systems on V is constructed. This bijection enables to deduce an axiomatic characterization of the interval function of a connected graph G from a characterization of the set of all geodesics in G.     

Graphs with small boundary

For a pair of vertices x and y in a graph G, we denote by d_G(x,y) the distance between x and y in G. We call x a boundary vertex of y if x and y belong to the same component and d_G(y,v)?d_G(y,x) for each neighbor v of x in G. A boundary vertex of some vertex is simply called a boundary vertex, and the set of boundary vertices in G is called the boundary of G, and is denoted by B(G).In this paper, we investigate graphs with a small boundary. Since a pair of farthest vertices are boundary vertices, |B(G)|?2 for every connected graph G of order at least two. We characterize the graphs with boundary of order at most three. We cannot give a characterization of graphs with exactly four boundary vertices, but we prove that such graphs have minimum degree at most six. Finally, we give an upper bound to the minimum degree of a connected graph G in terms of |B(G)|.     

On derivable mappings

A linear mapping δ from an algebra A into an A-bimodule M is called derivable at c∈A if δ(a)b+aδ(b)=δ(c) for all a,b∈A with ab=c. For a norm-closed unital subalgebra A of operators on a Banach space X, we show that if C∈A has a right inverse in B(X) and the linear span of the range of rank-one operators in A is dense in X then the only derivable mappings at C from A into B(X) are derivations; in particular the result holds for all completely distributive subspace lattice algebras, J-subspace lattice algebras, and norm-closed unital standard algebras of B(X). As an application, every Jordan derivation from such an algebra into B(X) is a derivation. For a large class of reflexive algebras A on a Banach space X, we show that inner derivations from A into B(X) can be characterized by boundedness and derivability at any fixed C∈A, provided C has a right inverse in B(X). We also show that if A is a canonical subalgebra of an AF C^∗-algebra B and M is a unital Banach A-bimodule, then every bounded local derivation from A into M is a derivation; moreover, every bounded linear mapping from A into B that is derivable at the unit I is a derivation.     

Singular values and Schmidt pairs of composition operators on the Hardy space

We find the singular values and corresponding Schmidt pairs of a compact composition operator Cφ induced by φ(z)=az+b, where |a|+|b|<1, on the classical Hardy space. We do so by solving a functional equation that is a generalization of Schröder's equation: find a function f, holomorphic on the open unit disc, and a complex number λ such that G(z)f(ψ(z))=λf(ψ(z)), where ψ is a holomorphic self-map of the open unit disc with an interior fixed point and G is a bounded holomorphic function on the open unit disc. In addition, we find the spectrum of the weighted composition operator MGCψ.