An analysis of a class of algorithms for S-box construction

We analyze a very general class of algorithms for constructingm-bit invertible S-boxes called bit-by-bit methods. The method builds an S-box one entry at a time, and has been proposed by Adams and Tavares [2] and Forre [11] to construct S-boxes that satisfy certain cryptographic properties such as nonlinearity and the strict avalanche criterion. We prove, both theoretically and empirically, that the bit-by-bit method is infeasible form>6. The author is currently employed by the Distributed System Technology Center (DSTC), Brisbane, Australia. Correspondence should be sent to ISRC, QUT Gardens Point, 2 George Street, GPO Box 2434, Brisbane, Queensland 4001, Australia.     

Fix-Mahonian Calculus, II: Further statistics

Using classical transformations on the symmetric group and two transformations constructed in Fix-Mahonian Calculus I, we show that several multivariable statistics are equidistributed either with the triplet (fix, des, maj), or the pair (fix, maj), where “fix,” “des” and “maj” denote the number of fixed points, the number of descents and the major index, respectively.     

Laurent polynomials and Eulerian numbers

Duistermaat and van der Kallen show that there is no nontrivial complex Laurent polynomial all of whose powers have a zero constant term. Inspired by this, Sturmfels poses two questions: Do the constant terms of a generic Laurent polynomial form a regular sequence? If so, then what is the degree of the associated zero-dimensional ideal? In this note, we prove that the Eulerian numbers provide the answer to the second question. The proof involves reinterpreting the problem in terms of toric geometry.     

The structure of alternative tableaux

In this paper we study alternative tableaux introduced by Viennot [X. Viennot, Alternative tableaux, permutations and partially asymmetric exclusion process, talk in Cambridge, 2008]. These tableaux are in simple bijection with permutation tableaux, defined previously by Postnikov [A. Postnikov, Total positivity, Grassmannians, and networks, arXiv:math/0609764v1 [math.CO], 2006].We exhibit a simple recursive structure for alternative tableaux, from which we can easily deduce a number of enumerative results. We also give bijections between these tableaux and certain classes of labeled trees. Finally, we exhibit a bijection with permutations, and relate it to some other bijections that already appeared in the literature.     

Schur positivity and log-concavity related to longest increasing subsequences

Chen proposed a conjecture on the log-concavity of the generating function for the symmetric group with respect to the length of longest increasing subsequences of permutations. Motivated by Chen’s log-concavity conjecture, Bóna, Lackner and Sagan further studied similar problems by restricting the whole symmetric group to certain of its subsets. They obtained the log-concavity of the corresponding generating functions for these subsets by using the hook-length formula. In this paper, we generalize and prove their results by establishing the Schur positivity of certain symmetric functions. This also enables us to propose a new approach to Chen’s original conjecture.     

An Erd?s-Ko-Rado theorem for partial permutations

Let [n] denote the set of positive integers {1,2,…,n}. An r-partial permutation of [n] is a pair (A,f) where A⊆[n], |A|=r and f:A→[n] is an injective map. A set A of r-partial permutations is intersecting if for any (A,f), (B,g)∈A, there exists x∈A∩B such that f(x)=g(x). We prove that for any intersecting family A of r-partial permutations, we have .It seems rather hard to characterize the case of equality. For 8?r?n-3, we show that equality holds if and only if there exist x₀ and ε₀ such that A consists of all (A,f) for which x₀∈A and f(x₀)=ε₀.     

ECO:a methodology for the enumeration of combinatorial objects

In this Paper, we illustrate a method (called the ECO method) for enumerating some classes of combinatorial objects. The basic idea of this method is the following: by means of an operator that performs a "local expansion" on the objects, we give some recursive constructions of these classes. We use these constructions to deduce some new funtional equations verified by classes' generating functions. By solving the functional equations, we enumerate the combinatorial objects according to various parameters. We show some applications of the method referring to some classical combinatorial objects, such as: trees, paths, polyminoes and permutations     

Sum rules in multiphoton coincidence rates

We show that sums of carefully chosen coincidence rates in a multiphoton interferometry experiment can be simplified by replacing the original unitary scattering matrix with a coset matrix containing 0s. The number and placement of these 0s reduces the complexity of each term in the sum without affecting the original sum of rates. In particular, the evaluation of sums of modulus squared of permanents is shown to turn in some cases into a sum of modulus squared of determinants. The sums of rates are shown to be equivalent to the removal of some optical elements in the interferometer.