Minimum cost and list homomorphisms to semicomplete digraphs

For digraphs D and H, a mapping f:V(D)→V(H) is a homomorphism of D to H if uv∈A(D) implies f(u)f(v)∈A(H). Let H be a fixed directed or undirected graph. The homomorphism problem for H asks whether a directed or undirected input graph D admits a homomorphism to H. The list homomorphism problem for H is a generalization of the homomorphism problem for H, where every vertex x∈V(D) is assigned a set L_x of possible colors (vertices of H).The following optimization version of these decision problems generalizes the list homomorphism problem and was introduced in Gutin et al. [Level of repair analysis and minimum cost homomorphisms of graphs, Discrete Appl. Math., to appear], where it was motivated by a real-world problem in defence logistics. Suppose we are given a pair of digraphs D,H and a positive integral cost c_i(u) for each u∈V(D) and i∈V(H). The cost of a homomorphism f of D to H is . For a fixed digraph H, the minimum cost homomorphism problem for H is stated as follows: for an 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 one exists, find such a homomorphism of minimum cost.We obtain dichotomy classifications of the computational complexity of the list homomorphism and minimum cost homomorphism problems, when H is a semicomplete digraph (digraph in which there is at least one arc between any two vertices). Our dichotomy for the list homomorphism problem coincides with the one obtained by Bang-Jensen, Hell and MacGillivray in 1988 for the homomorphism problem when H is a semicomplete digraph: both problems are polynomial solvable if H has at most one cycle; otherwise, both problems are NP-complete. The dichotomy for the minimum cost homomorphism problem is different: the problem is polynomial time solvable if H is acyclic or H is a cycle of length 2 or 3; otherwise, the problem is NP-hard.     

Two-parameter families of quantum symmetry groups

We introduce and study natural two-parameter families of quantum groups motivated on one hand by the liberations of classical orthogonal groups and on the other by quantum isometry groups of the duals of the free groups. Specifically, for each pair (p,q) of non-negative integers we define and investigate quantum groups O⁺(p,q), B⁺(p,q), S⁺(p,q) and H⁺(p,q) corresponding to, respectively, orthogonal groups, bistochastic groups, symmetric groups and hyperoctahedral groups. In the first three cases the new quantum groups turn out to be related to the (dual free products of ) free quantum groups studied earlier. For H⁺(p,q) the situation is different and we show that , where the latter can be viewed as a liberation of the classical isometry group of the p-dimensional torus.     

Aspects of compact quantum group theory

We show that if a compact quantum semigroup satisfies certain weak cancellation laws, then it admits a Haar measure, and using this we show that it is a compact quantum group. Thus, we obtain a new characterization of a compact quantum group. We also give a necessary and sufficient algebraic condition for the Haar measure of a compact quantum group to be faithful, in the case that its coordinate -algebra is exact. A representation is given for the linear dual of the Hopf -algebra of a compact quantum group, and a functional calculus for unbounded linear functionals is derived.

     

Level of repair analysis and minimum cost homomorphisms of graphs

Level of repair analysis (LORA) is a prescribed procedure for defense logistics support planning. For a complex engineering system containing perhaps thousands of assemblies, sub-assemblies, components, etc. organized into several levels of indenture and with a number of possible repair decisions, LORA seeks to determine an optimal provision of repair and maintenance facilities to minimize overall life-cycle costs. For a LORA problem with two levels of indenture with three possible repair decisions, which is of interest in UK and US military and which we call LORA-BR, Barros [The optimisation of repair decisions using life-cycle cost parameters. IMA J. Management Math. 9 (1998) 403-413] and Barros and Riley [A combinatorial approach to level of repair analysis, European J. Oper. Res. 129 (2001) 242-251] developed certain branch-and-bound heuristics. The surprising result of this paper is that LORA-BR is, in fact, polynomial-time solvable. To obtain this result, we formulate the general LORA problem as an optimization homomorphism problem on bipartite graphs, and reduce a generalization of LORA-BR, LORA-M, to the maximum weight independent set problem on a bipartite graph. We prove that the general LORA problem is NP-hard by using an important result on list homomorphisms of graphs. We introduce the minimum cost graph homomorphism problem, provide partial results and pose an open problem. Finally, we show that our result for LORA-BR can be applied to prove that an extension of the maximum weight independent set problem on bipartite graphs is polynomial time solvable.     

The small quantum group as a quantum double

We prove that the quantum double of the quasi-Hopf algebra of dimension attached in [P. Etingof, S. Gelaki, On radically graded finite-dimensional quasi-Hopf algebras, Mosc. Math. J. 5 (2) (2005) 371–378] to a simple complex Lie algebra and a primitive root of unity q of order n² is equivalent to Lusztig's small quantum group (under some conditions on n). We also give a conceptual construction of using the notion of de-equivariantization of tensor categories.     

Quantum group of orientation-preserving Riemannian isometries

We formulate a quantum group analogue of the group of orientation-preserving Riemannian isometries of a compact Riemannian spin manifold, more generally, of a (possibly R-twisted and of compact type) spectral triple. The main advantage of this formulation, which is directly in terms of the Dirac operator, is that it does not need the existence of any ‘good’ Laplacian as in our previous works on quantum isometry groups. Several interesting examples, including those coming from Rieffel-type deformation as well as the equivariant spectral triples on SU_μ(2) and are discussed.     

Heisenberg-Virasoro代数的q-形变的量子群结构

构造了水平为零的扭的Heisenberg-Virasoro代数的一个q-形变Hvirq,证明它是一个quasi-hom-李代数.给出该代数的一个非平凡的量子群结构,即它是一个非交换且余交换的Hopf代数.     

Quantum double constructions for compact quantum group

For a non-degenerate pair of compact quantum groups, we first construct the quantum double as an algebraic compact quantum group in an algebraic framework. Then by adopting some completion procedure, we give the universal and reduced quantum double constructions in the correspondence C＊-algebraic settings, which generalize Drinfeld＇s quantum double construction and yield new C＊-algebraic compact quantum groups.     

Cross-intersecting families of permutations

For positive integers r and n with r?n, let Pr,n be the family of all sets {(1,y₁),(2,y₂),…,(r,yr)} such that y₁,y₂,…,yr are distinct elements of [n]={1,2,…,n}. Pn,n describes permutations of [n]. For r<n, Pr,n describes permutations of r-element subsets of [n]. Families A₁,A₂,…,Ak of sets are said to be cross-intersecting if, for any distinct i and j in [k], any set in Ai intersects any set in Aj. For any r, n and k?2, we determine the cases in which the sum of sizes of cross-intersecting sub-families A₁,A₂,…,Ak of Pr,n is a maximum, hence solving a recent conjecture (suggested by the author).     

Quantum invariant families of matrices in free probability

We consider (self-adjoint) families of infinite matrices of noncommutative random variables such that the joint distribution of their entries is invariant under conjugation by a free quantum group. For the free orthogonal and hyperoctahedral groups, we obtain complete characterizations of the invariant families in terms of an operator-valued R-cyclicity condition. This is a surprising contrast with the Aldous-Hoover characterization of jointly exchangeable arrays.     

Quantum Spacetime,Quantum Geometry and Planck scales

The Principles of Quantum Mechanics and of Classical General Relativity indicate that Spacetime in the small (Planck scale) ought to be described by a noncommutative C* Algebra, implementing spacetime uncertainty relations. A model C* algebra of Quantum Spacetime and its Quantum Geometry is described. Interacting Quantum Field Theory on such a background is discussed, with open problems and recent progress. Applications to cosmology suggest that the Planck scale ought to depend upon dynamics, and possible consequences in the large of the quantum structure in the small are outlined.     

Weighted cross-intersecting families

In this paper we investigate weighted cross-intersecting families: if α,β>0 are given constants, we want to find the maximum of α|A|+β|B| for A,B uniform cross-intersecting families. We determine the maximum sum, even if we have restrictions of the size of A.As corollaries, we will obtain some new bounds on the shadows and the shades of uniform families. We give direct proofs for these bounds, as well, and show that the theorems for cross-intersecting families also follow from these results.Finally, we will generalize the LYM inequality not only for cross-intersecting families, but also for arbitrary Sperner families.     

On generalized separating hash families

Separating hash families are useful combinatorial structures which are studied in a general form in this paper. Necessary and sufficient conditions for the existence of certain types of generalized hash functions are considered.     

Equivariant Poincaré duality for quantum group actions

We extend the notion of Poincaré duality in KK-theory to the setting of quantum group actions. An important ingredient in our approach is the replacement of ordinary tensor products by braided tensor products. Along the way we discuss general properties of equivariant KK-theory for locally compact quantum groups, including the construction of exterior products. As an example, we prove that the standard Podle? sphere is equivariantly Poincaré dual to itself.     

Cyclotomic constructions of external difference families and disjoint difference families

External difference families (EDFs) are a type of new combinatorial designs originated from cryptography. Some results had been obtained by Chang and Ding, the connection between EDFs and disjoint difference families (DDFs) was also established. In this paper, further cyclotomic constructions of EDFs and DDFs are presented, and several classes of EDFs and DDFs are obtained. Answers to problems 1 and 4 by Chang and Ding are also given. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 333–341, 2009     

量子群U_q(sl(2 ) )的非负部分(英文)

设U≥ 0 是量子群Uq(sl(2 ) )的非负部分 .在本文中 ,我们确定了U≥ 0 的中心Z(U≥ 0 )和U≥ 0 的所有不可约表示     

Cross-intersecting sub-families of hereditary families

Families A₁,A₂,…,Ak of sets are said to be cross-intersecting if for any i and j in {1,2,…,k} with i≠j, any set in Ai intersects any set in Aj. For a finite set X, let X² denote the power set of X (the family of all subsets of X). A family H is said to be hereditary if all subsets of any set in H are in H; so H is hereditary if and only if it is a union of power sets. We conjecture that for any non-empty hereditary sub-family H≠{∅} of X² and any k?|X|+1, both the sum and the product of sizes of k cross-intersecting sub-families A₁,A₂,…,Ak (not necessarily distinct or non-empty) of H are maxima if A₁=A₂=?=Ak=S for some largest starSofH (a sub-family of H whose sets have a common element). We prove this for the case when H is compressed with respect to an element x of X, and for this purpose we establish new properties of the usual compression operation. As we will show, for the sum, the condition k?|X|+1 is sharp. However, for the product, we actually conjecture that the configuration A₁=A₂=?=Ak=S is optimal for any hereditary H and any k?2, and we prove this for a special case.