The paper is concerned with subsets I of the residue group Z(d) in which the difference of any two elements is not relatively prime to d. The class of such subsets is denoted by U (d), the class of sets from U (d) of ...
详细信息
The paper is concerned with subsets I of the residue group Z(d) in which the difference of any two elements is not relatively prime to d. The class of such subsets is denoted by U (d), the class of sets from U (d) of cardinality r is denoted by U (d, r). The present paper gives formulas for evaluation or estimation of vertical bar U (d)vertical bar and vertical bar U (d, r)vertical bar.
This paper examines a problem in enumerative and asymptotic combinatorics involving the classical structure of integer compositions. What is sought is an analysis on average and in distribution of the length of the lo...
详细信息
This paper examines a problem in enumerative and asymptotic combinatorics involving the classical structure of integer compositions. What is sought is an analysis on average and in distribution of the length of the longest run of consecutive equal parts in a composition of size n. The problem was posed by Herbert Wilf at the Analysis of Algorithms conference in July 2009 (see arXiv:0906.5196). (C) 2014 Elsevier B.V. All rights reserved.
We introduce and study a new mathematical structure in the generalised (quantum) cohomology theory for Grassmannians. Namely, we relate the Schubert calculus to a quantum integrable system known in the physics literat...
详细信息
We introduce and study a new mathematical structure in the generalised (quantum) cohomology theory for Grassmannians. Namely, we relate the Schubert calculus to a quantum integrable system known in the physics literature as the asymmetric six-vertex model. Our approach offers a new perspective on already established and well-studied special cases, for example equivariant K-theory, and in addition allows us to formulate a conjecture on the so-far unknown case of quantum equivariant K-theory. (C) 2017 Elsevier Inc. All rights reserved.
We relate the counting of rational curves intersecting Schubert varieties of the Grassmannian to the counting of certain non-intersecting lattice paths on the cylinder, so-called vicious and osculating walkers. These ...
详细信息
We relate the counting of rational curves intersecting Schubert varieties of the Grassmannian to the counting of certain non-intersecting lattice paths on the cylinder, so-called vicious and osculating walkers. These lattice paths form exactly solvable statistical mechanics models and are obtained from solutions to the Yang-Baxter equation. The eigenvectors of the transfer matrices of these models yield the idempotents of the Verlinde algebra of the gauged -WZNW model. The latter is known to be closely related to the small quantum cohomology ring of the Grassmannian. We establish further that the partition functions of the vicious and osculating walker model are given in terms of Postnikov's toric Schur functions and can be interpreted as generating functions for Gromov-Witten invariants. We reveal an underlying quantum group structure in terms of Yang-Baxter algebras and use it to give a generating formula for toric Schur functions in terms of divided difference operators which appear in known representations of the nil-Hecke algebra.
We connect k-triangulations of a convex n-gon to the theory of Schubert polynomials. We use this connection to prove that the simplicial complex with k-triangulations as facets is a vertex-decomposable triangulated sp...
详细信息
We connect k-triangulations of a convex n-gon to the theory of Schubert polynomials. We use this connection to prove that the simplicial complex with k-triangulations as facets is a vertex-decomposable triangulated sphere, and we give a new proof of the determinantal formula for the number of k-triangulations. (C) 2011 Elsevier Inc. All rights reserved.
For a set of vertices of a connected graph , a Steiner W-tree is a connected subgraph of such that and is minimum. Vertices in are called terminals. In this work, we design an algorithm for the enumeration of all Stei...
详细信息
For a set of vertices of a connected graph , a Steiner W-tree is a connected subgraph of such that and is minimum. Vertices in are called terminals. In this work, we design an algorithm for the enumeration of all Steiner -trees for a constant number of terminals, which is the usual scenario in many applications. We discuss algorithmic issues involving space requirements to compactly represent the optimal solutions and the time delay to generate them. After generating the first Steiner -tree in polynomial time, our algorithm enumerates the remaining trees with delay (where ). An algorithm to enumerate all Steiner trees was already known (Khachiyan et al., SIAM J Discret Math 19:966-984, 2005), but this is the first one achieving polynomial delay. A by-product of our algorithm is a representation of all (possibly exponentially many) optimal solutions using polynomially bounded space. We also deal with the following problem: given and a vertex , is in a Steiner -tree for some ? This problem is investigated from the complexity point of view. We prove that it is NP-hard when has arbitrary size. In addition, we prove that deciding whether is in some Steiner -tree is NP-hard as well. We discuss how these problems can be used to define a notion of Steiner convexity in graphs.
Consider a finitely generated restricted Lie algebra L over the finite field F-q and, given n a parts per thousand yen 0, denote the number of restricted ideals H aS, L with $${\dim _{{F_q}}}$$ L/H = n by c (n) (L). W...
详细信息
Consider a finitely generated restricted Lie algebra L over the finite field F-q and, given n a parts per thousand yen 0, denote the number of restricted ideals H aS, L with $${\dim _{{F_q}}}$$ L/H = n by c (n) (L). We show for the free metabelian restricted Lie algebra L of finite rank that the ideal growth sequence grows superpolynomially;namely, there exist positive constants lambda(1) and lambda(2) such that $${q boolean AND{{\lambda _1}{n boolean AND 2}}} \leqslant {c_n}\left( L \right) \leqslant {q boolean AND{{\lambda _2}{n boolean AND 2}}}$$ for n large enough.
作者：
Bostan, A.Kurkova, I.Raschel, K.INRIA Saclay Ile de France
Batiment Alan Turing1 Rue Honore Estienne dOrves F-91120 Palaiseau France Univ Paris 06
Lab Probabilites & Modeles Aleatoires 4 Pl Jussieu F-75252 Paris 05 France Univ Tours
CNRS Parc Grandmont F-37200 Tours France Univ Tours
Federat Rech Denis Poisson Parc Grandmont F-37200 Tours France Univ Tours
Lab Math & Phys Theor Parc Grandmont F-37200 Tours France
Gessel walks are lattice paths confined to the quarter plane that start at the origin and consist of unit steps going eitherWest, East, South-West or North-East. In 2001, Ira Gessel conjectured a nice closed-form expr...
详细信息
Gessel walks are lattice paths confined to the quarter plane that start at the origin and consist of unit steps going eitherWest, East, South-West or North-East. In 2001, Ira Gessel conjectured a nice closed-form expression for the number of Gessel walks ending at the origin. In 2008, Kauers, Koutschan and Zeilberger gave a computer-aided proof of this conjecture. The same year, Bostan and Kauers showed, again using computer algebra tools, that the complete generating function of Gessel walks is algebraic. In this article we propose the first "human proofs" of these results. They are derived from a new expression for the generating function of Gessel walks in terms of Weierstrass zeta functions.
C. Jensen, J. McCammond and J. Meier have used weighted hypertrees to compute the Euler characteristic of a subgroup of the automorphism group of a free product. Weighted hypertrees also appear in the study of the hom...
详细信息
C. Jensen, J. McCammond and J. Meier have used weighted hypertrees to compute the Euler characteristic of a subgroup of the automorphism group of a free product. Weighted hypertrees also appear in the study of the homology of the hypertree poset. We link them to decorated hypertrees after a general study on decorated hypertrees, which we enumerate using box trees. (C) 2013 Elsevier Inc. All rights reserved.
We refine an identity between the numbers of certain non-crossing graphs and multigraphs, by modifying a bijection found by P. Podbrdsky [A bijective proof of an identity for noncrossing graphs, Discrete Math. 260 (20...
详细信息
We refine an identity between the numbers of certain non-crossing graphs and multigraphs, by modifying a bijection found by P. Podbrdsky [A bijective proof of an identity for noncrossing graphs, Discrete Math. 260 (2003) 249-253]. We also prove a new identity between the number of acyclic non-crossing graphs with it vertices and k edges (isolated vertices allowed and no multiple edges allowed), and the number of non-crossing connected graphs with it edges and k vertices (Multiple edges allowed and no isolated vertices allowed). (C) 2007 Elsevier B.V. All rights reserved.
暂无评论