共查询到20条相似文献,搜索用时 15 毫秒
1.
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 Lx 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 ci(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 ci(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. 相似文献
2.
Teodor Banica 《Journal of Functional Analysis》2011,260(11):3252-3282
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. 相似文献
3.
4.
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.
5.
Gregory Gutin 《Discrete Applied Mathematics》2006,154(6):881-889
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. 相似文献
6.
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 n2 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. 相似文献
7.
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. 相似文献
8.
构造了水平为零的扭的Heisenberg-Virasoro代数的一个q-形变Hvirq,证明它是一个quasi-hom-李代数.给出该代数的一个非平凡的量子群结构,即它是一个非交换且余交换的Hopf代数. 相似文献
9.
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. 相似文献
10.
Peter Borg 《Journal of Combinatorial Theory, Series A》2010,117(4):483-487
For positive integers r and n with r?n, let Pr,n be the family of all sets {(1,y1),(2,y2),…,(r,yr)} such that y1,y2,…,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 A1,A2,…,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 A1,A2,…,Ak of Pr,n is a maximum, hence solving a recent conjecture (suggested by the author). 相似文献
11.
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. 相似文献
12.
《Expositiones Mathematicae》2020,38(2):168-179
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. 相似文献
13.
Ákos Kisvölcsey 《Discrete Mathematics》2008,308(11):2247-2260
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. 相似文献
14.
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. 相似文献
15.
Ryszard Nest 《Journal of Functional Analysis》2010,258(5):1466-1913
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. 相似文献
16.
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 相似文献
17.
设U≥ 0 是量子群Uq(sl(2 ) )的非负部分 .在本文中 ,我们确定了U≥ 0 的中心Z(U≥ 0 )和U≥ 0 的所有不可约表示 相似文献
18.
Peter Borg 《Journal of Combinatorial Theory, Series A》2012,119(4):871-881
Families A1,A2,…,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 X2 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 X2 and any k?|X|+1, both the sum and the product of sizes of k cross-intersecting sub-families A1,A2,…,Ak (not necessarily distinct or non-empty) of H are maxima if A1=A2=?=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 A1=A2=?=Ak=S is optimal for any hereditary H and any k?2, and we prove this for a special case. 相似文献
19.
20.