The notion of a boundary graph class was recently introduced for a classification of hereditary graph classes according to the complexity of a considered problem. Two concrete graph classes are known to be boundary for several graph problems. We formulate a criterion to determine whether these classes are boundary for a given graph problem or not. We also demonstrate that the classes are simultaneously boundary for some continuous set of graph problems and they are not simultaneously boundary for another set of the same cardinality. Both families of problems are constituted by variants of the maximum induced subgraph problem.
Понятие граничного свойства графов было недавно введено в качестве релаксации минимального по включению свойства и было применено к нескольким задачам алгоритмической и комбинаторной природы. В настоящей работе мы в начале делаем обзор недавних результатов, связанных с этими понятием, а затем применяем их к двум алгоритмическим задачам: задаче о гамильтоновом цикле и задаче о вершинной k-раскраске. В частности, мы выявляем два граничных класса для задачи о гамильтоновом цикле и доказываем, что при k>3 существует континуум граничных классов для задачи о вершинной k-раскраске.
We introduce the notion of a braided algebra and study some examples of these. In particular, R-symmetric and R-skew-symmetric algebras of a linear space V equipped with a skew-invertible Hecke symmetry R are braided algebras. We prove the “mountain property” for the numerators and denominators of their Poincaré–Hilbert series (which are always rational functions). Also, we further develop a differential calculus on modified Reflection Equation algebras. Thus, we exhibit a new form of the Leibniz rule for partial derivatives on such algebras related to involutive symmetries R. In particular, we present this rule for the algebra U(gl(m)). The case of the algebra U(gl(2)) and its compact form U(u(2)) (which can be treated as a deformation of the Minkowski space algebra) is considered in detail. On the algebra U(u(2)) we introduce the notion of the quantum radius, which is a deformation of the usual radius, and compute the action of rotationally invariant operators and in particular of the Laplace operator. This enables us to define analogs of the Laplace–Beltrami operators corresponding to certain Schwarzschild-type metrics and to compute their actions on the algebra U(u(2)) and its central extension. Some “physical” consequences of our considerations are presented.
On any reflection equation algebra corresponding to a skew-invertible Hecke symmetry (i.e., a special type solution of the Quantum Yang-Baxter equation) we define analogs of the partial derivatives. Together with elements of the initial reflection equation algebra they generate a "braided analog" of the Weyl algebra. When q→1, the braided Weyl algebra corresponding to the Quantum Group U q(sl(2)) goes to the Weyl algebra defined on the algebra Sym(u(2)) or U(u(2)) depending on the way of passing to the limit. Thus, we define partial derivatives on the algebra U(u(2)), find their "eigenfunctions", and introduce an analog of the Laplace operator on this algebra. Also, we define the "radial part" of this operator, express it in terms of "quantum eigenvalues", and sketch an analog of the de Rham complex on the algebra U(u(2)). Eventual applications of our approach are discussed.
We construct an analog of the subalgebra Ugl(n)⊗Ugl(m)⊂Ugl(m+n) in the setting of quantum toroidal algebras and study the restrictions of various representations to this subalgebra.
It is known that by dualizing the Bochner–Lichnerowicz–Weitzenböck formula, one obtains Poincaré-type inequalities on Riemannian manifolds equipped with a density, which satisfy the Bakry–Émery Curvature-Dimension condition (combining a lower bound on its generalized Ricci curvature and an upper bound on its generalized dimension). When the manifold has a boundary, an appropriate generalization of the Reilly formula may be used instead. By systematically dualizing this formula for various combinations of boundary conditions of the domain (convex, mean-convex) and the function (Neumann, Dirichlet), we obtain new Brascamp–Lieb-type inequalities on the manifold. All previously known inequalities of Lichnerowicz, Brascamp–Lieb, Bobkov–Ledoux, and Veysseire are recovered, extended to the Riemannian setting and generalized into a single unified formulation, and their appropriate versions in the presence of a boundary are obtained. Our framework allows to encompass the entire class of Borell’s convex measures, including heavy-tailed measures, and extends the latter class to weighted-manifolds having negative generalized dimension.