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}}$.     

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.     

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.     

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     

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.     

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.     

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.     

Enumerating the orientable 2‐cell imbeddings of complete bipartite graphs

A formula is developed for the number of congruence classes of 2‐cell imbeddings of complete bipartite graphs in closed orientable surfaces. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 77–90, 1999     

Pattern avoidance in binary trees

This paper considers the enumeration of trees avoiding a contiguous pattern. We provide an algorithm for computing the generating function that counts n-leaf binary trees avoiding a given binary tree pattern t. Equipped with this counting mechanism, we study the analogue of Wilf equivalence in which two tree patterns are equivalent if the respective n-leaf trees that avoid them are equinumerous. We investigate the equivalence classes combinatorially. Toward establishing bijective proofs of tree pattern equivalence, we develop a general method of restructuring trees that conjecturally succeeds to produce an explicit bijection for each pair of equivalent tree patterns.     

Orthogonal on the circle rational functions with fixed poles II

The paper is devoted to the algebraic properties of rational functions which are orthogonal on the unit circle and have fixed poles.     

代数图论中的几个新结论

本文中我们证明几个关于克希霍夫矩阵的新定理.在这些定理下,代数图论中Temperly,Kelmans,以及Fiedler提出的一些早期定理成为直接的推论.     

Generalized Waiting Time Problems Associated with Pattern in Polya's Urn Scheme

Let X ₁, X ₂, ... be a sequence obtained by Polya's urn scheme. We consider a waiting time problem for the first occurrence of a pattern in the sequence X ₁, X ₂, ... , which is generalized by a notion score. The main part of our results is derived by the method of generalized probability generating functions. In Polya's urn scheme, the system of equations is composed of the infinite conditional probability generating functions, which can not be solved. Then, we present a new methodology to obtain the truncated probability generating function in a series up to an arbitrary order from the system of infinite equations. Numerical examples are also given in order to illustrate the feasibility of our results. Our results in this paper are not only new but also a first attempt to treat the system of infinite equations.