Simple permutations and algebraic generating functions

A simple permutation is one that never maps a nontrivial contiguous set of indices contiguously. Given a set of permutations that is closed under taking subpermutations and contains only finitely many simple permutations, we provide a framework for enumerating subsets that are restricted by properties belonging to a finite “query-complete set.” Such properties include being even, being an alternating permutation, and avoiding a given generalised (blocked or barred) pattern. We show that the generating functions for these subsets are always algebraic, thereby generalising recent results of Albert and Atkinson. We also apply these techniques to the enumeration of involutions and cyclic closures.     

Constructing new differentially 4-uniform permutations from the inverse function

Two new families of differentially 4-uniform permutations over ${\mathbb{F}}_{2^{2m}}$ are constructed by modifying the values of the inverse function on some subfield of ${\mathbb{F}}_{2^{2m}}$ and by applying affine transformations on the function. The resulted 4-uniform permutations have high nonlinearity and algebraic degree. A family of differentially 6-uniform permutations with high nonlinearity and algebraic degree is also constructed by making the modification on an affine subspace of ${\mathbb{F}}_{2^{2m}}$.     

Low differentially uniform permutations from the Dobbertin APN function over F2n

Substitution boxes (S-boxes) play a central role in block ciphers. In substitution-permutation networks, the S-boxes should be permutation functions over ${\mathbb{F}}_{2^n}$ to realize the invertibility of the encryption. More importantly, the S-boxes should have low differential uniformity, high nonlinearity, and high algebraic degree in order to resist differential attacks, linear attacks, and higher order differential attacks, respectively. In this paper, we construct new classes of differentially 4 and 6-uniform permutations by modifying the image of the Dobbertin APN function $x^d$ with $d=2^{4k}+2^{3k}+2^{2k}+2^k-1$ over a subfield of ${\mathbb{F}}_{2^n}$. In addition, the algebraic degree and the lower bound of the nonlinearity of the constructed functions are given.     

A note on APN permutations in even dimension

APN permutations in even dimension are vectorial Boolean functions that play a special role in the design of block ciphers. We study their properties, providing some general results and some applications to the low-dimension cases. In particular, we prove that none of their components can be quadratic. For an APN vectorial Boolean function (in even dimension) with all cubic components we prove the existence of a component having a large number of balanced derivatives. Using these restrictions, we obtain the first theoretical proof of the non-existence of APN permutations in dimension 4. Moreover, we derive some constraints on APN permutations in dimension 6.     

Constructing new differentially 4-uniform permutations from known ones

In this paper we study a new construction of differentially 4-uniform permutations from known ones and the inverse function. We focus on constructing methods of [20]. We split a finite field into its subfield and remainder, and, we choose known differentially 4-uniform permutations over the subfield and the inverse function over the entire field. As a result, we obtain two families of differentially 4-uniform permutations.     

Investigations of c-differential uniformity of permutations with Carlitz rank 3

The c-differential uniformity is recently proposed to reflect resistance against some variants of differential attack. Finding functions with low c-differential uniformity is attracting attention from many researchers. For even characteristic, it is known that permutations of low Carlitz rank have good cryptographic parameters, for example, low differential uniformity, high nonlinearity, etc. In this paper we show that permutations with low Carlitz rank have low c-differential uniformity. We also investigate c-differential uniformity of permutations with Carlitz rank 3 in detail.     

Enumerating Solutions of a System of Linear Inequalities Related to Magic Squares

We enumerate the solutions of a system of a simple homogeneous linear inequalities, motivated by magic squares and their generalizations. We also compute the generating function of these numbers, and prove that it is a rational function. Received March 1, 2005     

Digraphs with Hermitian spectral radius below 2 and their cospectrality with paths

It is well-known that the paths are determined by the spectrum of the adjacency matrix. For digraphs, every digraph whose underlying graph is a tree is cospectral to its underlying graph with respect to the Hermitian adjacency matrix ($H$-cospectral). Thus every (simple) digraph whose underlying graph is isomorphic to $P_n$ is $H$-cospectral to $P_n$. Interestingly, there are others. This paper finds digraphs that are $H$-cospectral with the path graph $P_n$ and whose underlying graphs are nonisomorphic, when $n$ is odd, and finds that such graphs do not exist when $n$ is even. In order to prove this result, all digraphs whose Hermitian spectral radius is smaller than 2 are determined.     

Odd length for even hyperoctahedral groups and signed generating functions

We define a new statistic on the even hyperoctahedral groups which is a natural analogue of the odd length statistic recently defined and studied on Coxeter groups of types $A$ and $B$. We compute the signed (by length) generating function of this statistic over the whole group and over its maximal and some other quotients and show that it always factors nicely. We also present some conjectures.     

Counting colored planar maps: Algebraicity results

We address the enumeration of properly q-colored planar maps, or more precisely, the enumeration of rooted planar maps M weighted by their chromatic polynomial χM(q) and counted by the number of vertices and faces. We prove that the associated generating function is algebraic when q≠0,4 is of the form 2+2cos(jπ/m), for integers j and m. This includes the two integer values q=2 and q=3. We extend this to planar maps weighted by their Potts polynomial PM(q,ν), which counts all q-colorings (proper or not) by the number of monochromatic edges. We then prove similar results for planar triangulations, thus generalizing some results of Tutte which dealt with their proper q-colorings. In statistical physics terms, the problem we study consists in solving the Potts model on random planar lattices. From a technical viewpoint, this means solving non-linear equations with two “catalytic” variables. To our knowledge, this is the first time such equations are being solved since Tutte?s remarkable solution of properly q-colored triangulations.     

Partially Ordered Generalized Patterns and <Emphasis Type="Italic">k</Emphasis>-ary Words

Recently, Kitaev [9] introduced partially ordered generalized patterns (POGPs) in the symmetric group, which further generalize the generalized permutation patterns introduced by Babson and Steingrímsson [1]. A POGP p is a GP some of whose letters are incomparable. In this paper, we study the generating functions (g.f.) for the number of k-ary words avoiding some POGPs. We give analogues, extend and generalize several known results, as well as get some new results. In particular, we give the g.f. for the entire distribution of the maximum number of non-overlapping occurrences of a pattern p with no dashes (which is allowed to have repetition of letters), provided we know the g.f. for the number of k-ary words that avoid p.AMS Subject Classification: 05A05, 05A15.     

Research problems from the Aveiro Workshop on Graph Spectra

This is a collection of open problems presented at the Aveiro Workshop on Graph Spectra held at the University of Aveiro, Portugal from April 10-12, 2006.     

On the enumeration of certain weighted graphs

We enumerate weighted simple graphs with a natural upper bound condition on the sum of the weight of adjacent vertices. We also compute the generating function of the numbers of these graphs, and prove that it is a rational function. In particular, we show that the generating function for connected bipartite simple graphs is of the form p₁(x)/(1-x)^m+1. For nonbipartite simple graphs, we get a generating function of the form p₂(x)/(1-x)^m+1(1+x)^l. Here m is the number of vertices of the graph, p₁(x) is a symmetric polynomial of degree at most m, p₂(x) is a polynomial of degree at most m+l, and l is a nonnegative integer. In addition, we give computational results for various graphs.