Fast Fourier Transform for Fitness Landscapes

We cast some classes of fitness landscapes as problems of spectral analysis on various Cayley graphs. In particular, landscapes derived from RNA folding are realized on Hamming graphs and analyzed in terms of Walsh transforms; assignment problems are interpreted as functions on the symmetric group and analyzed in terms of the representation theory of S_n. We show that explicit computation of the Walsh/Fourier transforms is feasible for landscapes with up to 10⁸ configurations using fast Fourier transform techniques. We find that the cost function of a linear sum assignment problem involves only the defining representation of the symmetric group, while quadratic assignment problems are superpositions of the representations indexed by the partitions (n), (n−1,1), (n−2,2), and (n−2,1,1). These correspond to the four smallest eigenvalues of the Laplacian of the Cayley graph obtained by using transpositions as the generating set on S_n.     

The walk partition and colorations of a graph

We study the partitions of a graph G with vertices labeled 1,2,…,n. A matrix notation for partitions is devised which reflects a partial order among partitions and provides a matrix characterization (in terms of the adjacency matrix A of G) of a coloration or equitable partition. An especially useful partition is one based on the number of walks issuing from each vertex. This is not generally a coloration (sufficient conditions are given) but nevertheless plays a special role relative to colorations. The spectrum of G, Sp(G), has a “main part”, the set of eigenvalues with an eigenvector not orthogonal to e (the column of 1s). We disprove a conjecture of Harary and Schwenk about the main part of the spectrum and prove an alternate characterization. The walk partition appears here and also in a relation between the main parts of the spectra of G and ?, its complement.     

Computing finest mincut partitions of a graph and application to routing problems

Let G=(V,E,w) be an n-vertex graph with edge weights w>0. We propose an algorithm computing all partitions of V into mincuts of G such that the mincuts in the partitions cannot be partitioned further into mincuts. There are O(n) such finest mincut partitions. A mincut is a non-empty proper subset of V such that the total weight of edges with exactly one end in the subset is minimal. The proposed algorithm exploits the cactus representation of mincuts and has the same time complexity as cactus construction. An application to the exact solution of the general routing problem is described.     

Self-complementary totally symmetric plane partitions

A totally symmetric plane partition of size n is a plane partition whose three-dimensional Ferrers graph is contained in the box X_n = [1, n] × [1, n] × [1, n] and which is mapped to itself under all permutations of the coordinate axes. The complement of the Ferrers graph of such a plane partition (that is, the set of lattice points in the box X_n that do not belong to the Ferrers graph) is again totally symmetric when viewed from the vantage point of the vertex (n + 1, n + 1, n + 1). A totally symmetric plane partition is self-complementary if it is congruent (in the geometrical sense) to its complement. This cannot occur unless n = 2m is even. In this paper we give several conjectures and a few theorems concerning self-complementary totally symmetric plane partitions. In particular we describe evidence which indicates a close relationship with m by m alternating sign matrices. In an earlier paper we described the close connection between m by m alternating sign matrices and descending plane partitions with no parts exceeding m. We are thus left with three classes of objects which are all apparently interrelated. There remain many unsolved problems, the simplest of which is to prove that any two of the objects have the same cardinality.     

Bounding the gap between extremal Laplacian eigenvalues of graphs

Let G be a graph whose Laplacian eigenvalues are 0 = λ₁ ? λ₂ ? ? ? λ_n. We investigate the gap (expressed either as a difference or as a ratio) between the extremal non-trivial Laplacian eigenvalues of a connected graph (that is λ_n and λ₂). This gap is closely related to the average density of cuts in a graph. We focus here on the problem of bounding the gap from below.     

On graphs whose Laplacian matrices have distinct integer eigenvalues

In this paper, we investigate graphs for which the corresponding Laplacian matrix has distinct integer eigenvalues. We define the set S_i,n to be the set of all integers from 0 to n, excluding i. If there exists a graph whose Laplacian matrix has this set as its eigenvalues, we say that this set is Laplacian realizable. We investigate the sets S_i,n that are Laplacian realizable, and the structures of the graphs whose Laplacian matrix has such a set as its eigenvalues. We characterize those i < n such that S_i,n is Laplacian realizable, and show that for certain values of i, the set S_i,n is realized by a unique graph. Finally, we conjecture that S_n,n is not Laplacian realizable for n ≥ 2 and show that the conjecture holds for certain values of n. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Balanced partitions

A famous theorem of Euler asserts that there are as many partitions of n into distinct parts as there are partitions into odd parts. We begin by establishing a less well-known companion result, which states that both of these quantities are equal to the number of partitions of n into even parts along with exactly one triangular part. We then introduce the characteristic of a partition, which is determined in a simple way by the placement of odd parts within the list of all parts. This leads to a refinement of the aforementioned result in the form of a new type of partition identity involving characteristic, distinct parts, even parts, and triangular numbers. Our primary purpose is to present a bijective proof of the central instance of this new type of identity, which concerns balanced partitions—partitions in which odd parts occupy as many even as odd positions within the list of all parts. The bijection is accomplished by means of a construction that converts balanced partitions of 2n into unrestricted partitions of n via a pairing of the squares in the Young tableau.     

Relations among eigenvalues of Sturm-Liouville problems with different types of leading coefficient functions

For any Sturm-Liouville problem with a separable boundary condition and whose leading coefficient function changes sign (exactly once), we first give a geometric characterization of its eigenvalues λn using the eigenvalues of some corresponding problems with a definite leading coefficient function. Consequences of this characterization include simple proofs of the existence of the λn's, their Prüfer angle characterization, and a way for determining their indices from the zeros of their eigenfunctions. Then, interlacing relations among the λn's and the eigenvalues of the corresponding problems are obtained. Using these relations, a simple proof of asymptotic formulas for the λn's is given.     

Connected permutation graphs

A permutation graph is a simple graph associated with a permutation. Let c_n be the number of connected permutation graphs on n vertices. Then the sequence {c_n} satisfies an interesting recurrence relation such that it provides partitions of n! as . We also see that, if uniformly chosen at random, asymptotically almost all permutation graphs are connected.     

Non-P-recursiveness of numbers of matchings or linear chord diagrams with many crossings

The number con_n counts matchings X on {1,2,…,2n}, which are partitions into n two-element blocks, such that the crossing graph of X is connected. Similarly, cro_n counts matchings whose crossing graph has no isolated vertex. (If it has no edge, Catalan numbers arise.) We apply generating functions techniques and prove, using a more generally applicable criterion, that the sequences (con_n) and (cro_n) are not P-recursive. On the other hand, we show that the residues of con_n and cro_n modulo any fixed power of 2 can be determined P-recursively. We consider also the numbers sco_n of symmetric connected matchings. Unfortunately, their generating function satisfies a complicated differential equation which we cannot handle.     

Characterization of n-path graphs and of graphs having nth root

We characterize connected graphs and digraphs having an nth root and so generalize results by A. Mukhopadhyay and D. P. Geller, respectively. We then define the n-path graph of a graph and characterize those graphs which are n-path graphs. This extends recent results by B. Devadas Acharya and M. N. Vartak. The corresponding problem for digraphs is also considered.     

Bisecting sparse random graphs

Consider partitions of the vertex set of a graph G into two sets with sizes differing by at most 1: the bisection width of G is the minimum over all such partitions of the number of “cross edges” between the parts. We are interested in sparse random graphs G_{n, c/n} with edge probability c/n. We show that, if c>ln 4, then the bisection width is Ω(n) with high probability; while if c<ln 4, then it is equal to 0 with high probability. There are corresponding threshold results for partitioning into any fixed number of parts. ©2001 John Wiley & Sons, Inc. Random Struct. Alg., 18, 31–38, 2001     

Eigenvalue assignments and the two largest multiplicities in a Hermitian matrix whose graph is a tree

Among the possible multiplicity lists for the eigenvalues of Hermitian matrices whose graph is a tree we focus upon M₂, the maximum value of the sum of the two largest multiplicities. The corresponding M₁ is already understood. The notion of assignment (of eigenvalues to subtrees) is formalized and applied. Using these ideas, simple upper and lower bounds are given for M₂ (in terms of simple graph theoretic parameters), cases of equality are indicated, and a combinatorial algorithm is given to compute M₂ precisely. In the process, several techniques are developed that likely have more general uses.     

Spectral characterization of some graphs

The lexicographic product (or composition) of a cycle of length r with a totally disconnected graph on n vertices is shown to be a graph characterized by the eigenvalues of its adjacency matrix for all odd r.     

On encodings of spanning trees

Deo and Micikevicius recently gave a new bijection for spanning trees of complete bipartite graphs. In this paper we devise a generalization of Deo and Micikevicius's method, which is also a modification of Olah's method for encoding the spanning trees of any complete multipartite graph K(n₁,…,n_r). We also give a bijection between the spanning trees of a planar graph and those of any of its planar duals. Finally we discuss the possibility of bijections for spanning trees of DeBriujn graphs, cubes, and regular graphs such as the Petersen graph that have integer eigenvalues.     

Approximation of isolated eigenvalues of general singular ordinary differential operators

Let A be a self-adjoint operator defined by a general singular ordinary differential expression τ on an interval (a, b), ? ∞ ≤ a < b ≤ ∞. We show that isolated eigenvalues in any gap of the essential spectrum of A are exactly the limits of eigenvalues of suitably chosen self-adjoint realizations A_n of τ on subintervals (a_n, b_n) of (a, b) with a_n → a, b_n → b. This means that eigenvalues of singular ordinary differential operators can be approximated by eigenvalues of regular operators. In the course of the proof we extend a result, which is well known for quasiregular differential expressions, to the general case: If the spectrum of A is not the whole real line, then the boundary conditions needed to define A can be given using solutions of (τ ? λ)u = 0, where λ is contained in the regularity domain of the minimal operator corresponding to τ.     

Bounds for eigenvalues of certain stochastic matrices

We consider the class of stochastic matrices M generated in the following way from graphs: if G is an undirected connected graph on n vertices with adjacency matrix A, we form M from A by dividing the entries in each row of A by their row sum. Being stochastic, M has the eigenvalue λ=1 and possibly also an eigenvalue λ=-1. We prove that the remaining eigenvalues of M lie in the disk ¦λ¦?1–n^-3, and show by examples that the order of magnitude of this estimate is best possible. In these examples, G has a bar-bell structure, in which n/3 of the vertices are arranged along a line, with n/3 vertices fully interconnected at each end. We also obtain better bounds when either the diameter of G or the maximal degree of a vertex is restricted.     

Sphere-separable partitions of multi-parameter elements

We show the optimality of sphere-separable partitions for problems where n vectors in d-dimensional space are to be partitioned into p categories to minimize a cost function which is dependent in the sum of the vectors in each category; the sum of the squares of their Euclidean norms; and the number of elements in each category. We further show that the number of these partitions is polynomial in n. These results broaden the class of partition problems for which an optimal solution is guaranteed within a prescribed set whose size is polynomially bounded in n. Applications of the results are demonstrated through examples.     

Tverberg’s Theorem and Graph Coloring

The topological Tverberg theorem has been generalized in several directions by setting extra restrictions on the Tverberg partitions. Restricted Tverberg partitions, defined by the idea that certain points cannot be in the same part, are encoded with graphs. When two points are adjacent in the graph, they are not in the same part. If the restrictions are too harsh, then the topological Tverberg theorem fails. The colored Tverberg theorem corresponds to graphs constructed as disjoint unions of small complete graphs. Hell studied the case of paths and cycles. In graph theory these partitions are usually viewed as graph colorings. As explored by Aharoni, Haxell, Meshulam and others there are fundamental connections between several notions of graph colorings and topological combinatorics. For ordinary graph colorings it is enough to require that the number of colors q satisfy q>Δ, where Δ is the maximal degree of the graph. It was proven by the first author using equivariant topology that if q>Δ ² then the topological Tverberg theorem still works. It is conjectured that q>KΔ is also enough for some constant K, and in this paper we prove a fixed-parameter version of that conjecture. The required topological connectivity results are proven with shellability, which also strengthens some previous partial results where the topological connectivity was proven with the nerve lemma.     

Fully-angular polyhex chains with minimal total π-electron energy

By Hückel molecular orbital (HMO) theory, the calculation of the total energy of all π-electrons in conjugated hydrocarbons can be reduced to that of E(G)=|λ₁|+|λ₂|+?+|λn|, where λi are the eigenvalues of the corresponding graph G. Denote by Ψn the set of all fully-angular polyhex chains with n hexagons. In this paper, we show that Hn has the minimum total π-electron energy among chains in Ψn, where Hn is the helicene chain.