The paper bounds the number of tessellations with T-shaped vertices on a fixed set of k lines: tessellations are efficiently encoded, and algorithms retrieve them, proving injectivity. This yields existence of a compl...
详细信息
The paper bounds the number of tessellations with T-shaped vertices on a fixed set of k lines: tessellations are efficiently encoded, and algorithms retrieve them, proving injectivity. This yields existence of a completely random T-tessellation, as defined by Kieu et al. (Spat Stat 6 (2013) 118-138), and of its Gibbsian modifications. The combinatorial bound is sharp, but likely pessimistic in typical cases. (c) 2014 Wiley Periodicals, Inc.
The conjecture that the orbit-counting generating function for totally symmetric plane partitions can be written as an explicit product formula has been stated independently by George Andrews and David Robbins around ...
详细信息
The conjecture that the orbit-counting generating function for totally symmetric plane partitions can be written as an explicit product formula has been stated independently by George Andrews and David Robbins around 1983. We present a proof of this long-standing conjecture.
In causal inference a matching algorithm assigns a subset of control units to each treated unit. Using combinatorial techniques we explore the support of matching algorithms to provide counting results and investigate...
详细信息
In causal inference a matching algorithm assigns a subset of control units to each treated unit. Using combinatorial techniques we explore the support of matching algorithms to provide counting results and investigate the role of the dimension of the covariates' space. (C) 2017 Elsevier B.V. All rights reserved.
We consider the problem #2UNSAT (counting the number of falsifying assignments for two conjunctive forms). Because #2SAT(F) = 2(n) - #2UNSAT(F), results about #2UNSAT can dually be established for solving #2SAT. We es...
详细信息
We consider the problem #2UNSAT (counting the number of falsifying assignments for two conjunctive forms). Because #2SAT(F) = 2(n) - #2UNSAT(F), results about #2UNSAT can dually be established for solving #2SAT. We establish the kind of two conjunctive formulas with a minimum number of falsifying assignment. As a result, we determine the formulas with a maximum number of models among the set of all 2-CF formulas with a same number of variables. We have shown that for any 2-CF F-n with n variables, #UNSAT(F-n) > #SAT(F-n) with the exception of totally dependent formulas. Thus, if #UNSAT(F-n) <= p(n) for a polynomial on n, then #SAT(F-n) <= p(n) too, and then #SAT(F-n) can be computed in polynomial time on the size of the formula.
We find the winning strategy for a class of truncation games played on words. As a consequence of the present author's recent results on some of these games we obtain new formulas for Bernoulli numbers and polynom...
详细信息
We find the winning strategy for a class of truncation games played on words. As a consequence of the present author's recent results on some of these games we obtain new formulas for Bernoulli numbers and polynomials of the second kind and a new combinatorial model for the number of connected permutations of given rank. For connected permutations, the decomposition used to find the winning strategy is shown to be bijectively equivalent to King's decomposition, used to recursively generate a transposition Gray code of the connected permutations. (C) 2010 Elsevier Inc. All rights reserved.
In this paper we explore the asymptotic enumeration of three-dimensional excursions confined to the positive octant. As shown in [29], both the exponential growth and the critical exponent admit universal formulas, re...
详细信息
In this paper we explore the asymptotic enumeration of three-dimensional excursions confined to the positive octant. As shown in [29], both the exponential growth and the critical exponent admit universal formulas, respectively in terms of the inventory of the step set and of the principal Dirichlet eigenvalue of a certain spherical triangle, itself being characterized by the steps of the model. We focus on the critical exponent, and our main objective is to relate combinatorial properties of the step set (structure of the so-called group of the walk, existence of a Hadamard decomposition, existence of differential equations satisfied by the generating functions) to geometric or analytic properties of the associated spherical triangle (remarkable angles, tiling properties, existence of an exceptional closed-form formula for the principal eigenvalue). As in general the eigenvalues of the Dirichlet problem on a spherical triangle are not known in closed form, we also develop a finite-elements method to compute approximate values, typically with ten digits of precision. (C) 2019 Elsevier Inc. All rights reserved.
We present new applications of q-binomials, also known as Gaussian binomial coefficients. Our main theorems determine cardinalities of certain error-correcting codes based on Varshamov-Tenengolts codes and prove a cur...
详细信息
We present new applications of q-binomials, also known as Gaussian binomial coefficients. Our main theorems determine cardinalities of certain error-correcting codes based on Varshamov-Tenengolts codes and prove a curious phenomenon relating to deletion spheres.
Skew Dyck paths are a generalization of ordinary Dyck paths, defined as paths using up steps U = (1, 1), down steps D = (1, -1), and left steps L=(-1, -1), starting and ending on the x-axis, never going below it, and ...
详细信息
Skew Dyck paths are a generalization of ordinary Dyck paths, defined as paths using up steps U = (1, 1), down steps D = (1, -1), and left steps L=(-1, -1), starting and ending on the x-axis, never going below it, and so that up and left steps never overlap. In this paper we study the class of these paths according to their area, extending several results holding for Dyck paths. Then we study the class of superdiagonal bargraphs, which can be naturally defined starting from skew Dyck paths. (C) 2009 Elsevier B.V. All rights reserved.
A subfamily of k-trees, the k-path graphs generalize path graphs in the same way k-trees generalize trees. This paper presents a code for unlabeled k-path graphs. The effect of structural properties of the family on t...
详细信息
A subfamily of k-trees, the k-path graphs generalize path graphs in the same way k-trees generalize trees. This paper presents a code for unlabeled k-path graphs. The effect of structural properties of the family on the code is investigated, leading to the solution of two problems: determining the exact number of unlabeled k-path graphs with n vertices and generating all elements of the family. (c) 2011 Elsevier B.V. All rights reserved.
作者：
Zvonkin, ALaBRI
Université Bordeaux I 351 cours da la Libération F-33405 Talence Cedex France
Physicists working in two-dimensional quantum gravity invented a new method of map enumeration based on computation of Gaussian integrals over the space of Hermitian matrices. This paper explains the basic facts of th...
详细信息
Physicists working in two-dimensional quantum gravity invented a new method of map enumeration based on computation of Gaussian integrals over the space of Hermitian matrices. This paper explains the basic facts of the method and provides an accessible introduction to the subject.
暂无评论