Nonrepetitive colorings of trees

A coloring of the vertices of a graph G is nonrepetitive if no path in G forms a sequence consisting of two identical blocks. The minimum number of colors needed is the Thue chromatic number, denoted by π(G). A famous theorem of Thue asserts that π(P)=3 for any path P with at least four vertices. In this paper we study the Thue chromatic number of trees. In view of the fact that π(T) is bounded by 4 in this class we aim to describe the 4-chromatic trees. In particular, we study the 4-critical trees which are minimal with respect to this property. Though there are many trees T with π(T)=4 we show that any of them has a sufficiently large subdivision H such that π(H)=3. The proof relies on Thue sequences with additional properties involving palindromic words. We also investigate nonrepetitive edge colorings of trees. By a similar argument we prove that any tree has a subdivision which can be edge-colored by at most Δ+1 colors without repetitions on paths.     

Breaking the rhythm on graphs

We study graph colorings avoiding periodic sequences with large number of blocks on paths. The main problem is to decide, for a given class of graphs F, if there are absolute constants t,k such that any graph from the class has a t-coloring with no k identical blocks in a row appearing on a path. The minimum t for which there is some k with this property is called the rhythm threshold of F, denoted by t(F). For instance, we show that the rhythm threshold of graphs of maximum degree at most d is between (d+1)/2 and d+1. We give several general conditions for finiteness of t(F), as well as some connections to existing chromatic parameters. The question whether the rhythm threshold is finite for planar graphs remains open.     

Dyck paths and restricted permutations

This paper is devoted to characterize permutations with forbidden patterns by using canonical reduced decompositions, which leads to bijections between Dyck paths and S_n(321) and S_n(231), respectively. We also discuss permutations in S_n avoiding two patterns, one of length 3 and the other of length k. These permutations produce a kind of discrete continuity between the Motzkin and the Catalan numbers.     

Counting involutory, unimodal, and alternating signed permutations

In this work we count the number of involutory, unimodal, and alternating elements of the group of signed permutations B_n, and the group of even-signed permutations D_n. Recurrence relations, generating functions, and explicit formulas of the enumerating sequences are given.     

On multiple pattern avoiding set partitions

We study classes of set partitions determined by the avoidance of multiple patterns, applying a natural notion of partition containment that has been introduced by Sagan. We say that two sets S and T of patterns are equivalent if for each n the number of partitions of size n avoiding all the members of S is the same as the number of those that avoid all the members of T.     

On limit theorem for the eigenvalues of product of two random matrices

The existence of limiting spectral distribution (LSD) of the product of two random matrices is proved. One of the random matrices is a sample covariance matrix and the other is an arbitrary Hermitian matrix. Specially, the density function of LSD of S_nW_n is established, where S_n is a sample covariance matrix and W_n is Wigner matrix.     

The inverse inertia problem for graphs: Cut vertices, trees, and a counterexample

Let G be an undirected graph on n vertices and let S(G) be the set of all real symmetric n×n matrices whose nonzero off-diagonal entries occur in exactly the positions corresponding to the edges of G. The inverse inertia problem for G asks which inertias can be attained by a matrix in S(G). We give a complete answer to this question for trees in terms of a new family of graph parameters, the maximal disconnection numbers of a graph. We also give a formula for the inertia set of a graph with a cut vertex in terms of inertia sets of proper subgraphs. Finally, we give an example of a graph that is not inertia-balanced, which settles an open problem from the October 2006 AIM Workshop on Spectra of Families of Matrices described by Graphs, Digraphs and Sign Patterns. We also determine some restrictions on the inertia set of any graph.     

Multiplicative versions of Klyachko’s theorem in finite factors

Let A and B be invertible positive elements in a II₁-factor A, and let μ_s(·) be the singular number on A. We prove that

exp_∫Klogμ_s(AB)ds?exp_∫Ilogμ_s(A)ds·exp_∫Jlogμ_s(B)ds,     

The prime dicompletion of a di-uniformity on a plain texture

Working within a plain texture (S,S), the authors construct a completion of a dicovering uniformity υ on (S,S) in terms of prime S-filters. In case υ is separated, a separated completion is then obtained using the T₀-quotient, and it is shown that this construction produces a reflector. For a totally bounded di-uniformity it is verified that these constructions lead to dicompactifications of the uniform ditopology. A condition is given under which complementation is preserved on passing to these completions, and an example on the real texture (R,R,ρ) is presented.     

Hajós Theorem For Colorings Of Edge-Weighted Graphs

Hajós theorem states that every graph with chromatic number at least k can be obtained from the complete graph K _k by a sequence of simple operations such that every intermediate graph also has chromatic number at least k. Here, Hajós theorem is extended in three slightly different ways to colorings and circular colorings of edge-weighted graphs. These extensions shed some new light on the Hajós theorem and show that colorings of edge-weighted graphs are most natural extension of usual graph colorings.* Supported in part by the Ministry of Education, Science and Sport of Slovenia, Research Program P0–0507–0101.     

Riffle shuffles,cycles, and descents

We derive closed form expressions and limiting formulae for a variety of functions of a permutation resulting from repeated riffle shuffles. The results allow new formulae and approximations for the number of permutations inS _n with given cycle type and number of descents. The theorems are derived from a bijection discovered by Gessel. A self-contained proof of Gessel's result is given.     

Conjectured statistics for the q,t-Catalan numbers

We introduce the distribution function F_n(q,t) of a pair of statistics on Catalan words and conjecture F_n(q,t) equals Garsia and Haiman's q,t-Catalan sequence C_n(q,t), which they defined as a sum of rational functions. We show that F_n,s(q,t), defined as the sum of these statistics restricted to Catalan words ending in s ones, satisfies a recurrence relation. As a corollary we are able to verify that F_n(q,t)=C_n(q,t) when t=1/q. We also show the partial symmetry relation F_n(q,1)=F_n(1,q). By modifying a proof of Haiman of a q-Lagrange inversion formula based on results of Garsia and Gessel, we obtain a q-analogue of the general Lagrange inversion formula which involves Catalan words grouped according to the number of ones at the end of the word.     

Reflexivity defect of spaces of linear operators

For a finite-dimensional linear subspace S⊆L(V,W) and a positive integer k, the k-reflexivity defect of S is defined by rd_k(S)=dim(Ref_k(S)/S), where Ref_k(S) is the k-reflexive closure of S. We study this quantity for two-dimensional spaces of operators and for single generated algebras and their commutants.     

Potentially nilpotent and spectrally arbitrary even cycle sign patterns

An n × n sign pattern S_n is potentially nilpotent if there is a real matrix having sign pattern S_n and characteristic polynomial xⁿ. A new family of sign patterns C_n with a cycle of every even length is introduced and shown to be potentially nilpotent by explicitly determining the entries of a nilpotent matrix with sign pattern C_n. These nilpotent matrices are used together with a Jacobian argument to show that C_n is spectrally arbitrary, i.e., there is a real matrix having sign pattern C_n and characteristic polynomial for any real μ_i. Some results and a conjecture on minimality of these spectrally arbitrary sign patterns are given.     

Twisted inner products and contraction inequalities on spaces of contravariant and covariant tensors

Given positive integers n and p, and a complex finite dimensional vector space V, we let S_n,p(V) denote the set of all functions from V×V×?×V-(n+p copies) to C that are linear and symmetric in the first n positions, and conjugate linear symmetric in the last p positions. Letting κ=min{n,p} we introduce twisted inner products, [·,·]_s,t,1?s,t?κ, on S_n,p(V), and prove the monotonicity condition [F,F]_s,t?[F,F]_u,v is satisfied when s?u?κ,t?v?κ, and F∈S_n,p(V). Using the monotonicity condition, and the Cauchy-Schwartz inequality, we obtain as corollaries many known inequalities involving norms of symmetric multilinear functions, which in turn imply known inequalities involving permanents of positive semidefinite Hermitian matrices. New tensor and permanental inequalities are also presented. Applications to partial differential equations are indicated.     

On the signless Laplacian spectral radius of graphs with cut vertices

In this paper, we show that among all the connected graphs with n vertices and k cut vertices, the maximal signless Laplacian spectral radius is attained uniquely at the graph G_n,k, where G_n,k is obtained from the complete graph K_n-k by attaching paths of almost equal lengths to all vertices of K_n-k. We also give a new proof of the analogous result for the spectral radius of the connected graphs with n vertices and k cut vertices (see [A. Berman, X.-D. Zhang, On the spectral radius of graphs with cut vertices, J. Combin. Theory Ser. B 83 (2001) 233-240]). Finally, we discuss the limit point of the maximal signless Laplacian spectral radius.     

An algebraic structure for Faber polynomials

Let Σ be the set of functions, convergent for all |z|>1, with a Laurent series of the form f(z)=z+∑_n?0a_nz^-n. In this paper, we prove that the set of Faber polynomial sequences over Σ and the set of their normalized kth derivative sequences form groups which are isomorphic to the hitting time subgroup and the Bell^(k) subgroup of the Riordan group, respectively. Further, a relationship between such Faber polynomial sequences and Lucas and Sheffer polynomial sequences is derived.     

A semialgebraic closure for commutative algebra

Let A⊂R be rings containing the rationals. In R let S be a multiplicatively closed subset such that 1∈S and 0∉S, T a preorder of R (a proper subsemiring containing the squares) such that S⊂T and I an A-submodule of R. Define ρ(I) (or ρ_S,T(I)) to be

ρ(I)={a∈R|sa^2m+t∈I^2m for some m∈N,s∈S and t∈T}.     

Construction of determinantal representation of trigonometric polynomials

For a pair of n×n Hermitian matrices H and K, a real ternary homogeneous polynomial defined by F(t,x,y)=det(tI_n+xH+yK) is hyperbolic with respect to (1,0,0). The Fiedler conjecture (or Lax conjecture) is recently affirmed, namely, for any real ternary hyperbolic polynomial F(t,x,y), there exist real symmetric matrices S₁ and S₂ such that F(t,x,y)=det(tI_n+xS₁+yS₂). In this paper, we give a constructive proof of the existence of symmetric matrices for the ternary forms associated with trigonometric polynomials.     

Counting subsets of the random partition and the ‘Brownian Bridge’ process

Let Ω_m be the set of partitions, ω, of a finite m-element set; induce a uniform probability distribution on Ω_m, and define X_ms(ω) as the number of s-element subsets in ω. We alow the existence of an integer-valued function n=n^(m)(t), t?[0, 1], and centering constants b_ms, 0?s? m, such that

$\text{Z}{}^{\mathrm{(m)}}\text{(t)=}\text{∑}\text{s=0}\text{n(m)(t)}\text{(X}{}_{\mathrm{ms}}\text{?b}{}_{\mathrm{ms}}\text{)}\text{√}\text{∑}\text{s=0}\text{m}\text{b}{}_{\mathrm{ms}}$

converges to the ‘Brownian Bridge’ process in terms of its finite-dimensional distributions.