Generalized triangulations and diagonal-free subsets of stack polyominoes

For n?3, let Ω_n be the set of line segments between vertices in a convex n-gon. For j?1, a j-crossing is a set of j distinct and mutually intersecting line segments from Ω_n such that all 2j endpoints are distinct. For k?1, let Δ_n,k be the simplicial complex of subsets of Ω_n not containing any (k+1)-crossing. For example, Δ_n,1 has one maximal set for each triangulation of the n-gon. Dress, Koolen, and Moulton were able to prove that all maximal sets in Δ_n,k have the same number k(2n-2k-1) of line segments. We demonstrate that the number of such maximal sets is counted by a k×k determinant of Catalan numbers. By the work of Desainte-Catherine and Viennot, this determinant is known to count quite a few other objects including fans of non-crossing Dyck paths. We generalize our result to a larger class of simplicial complexes including some of the complexes appearing in the work of Herzog and Trung on determinantal ideals.     

Centers for a 6-parameter family of polynomial vector fields of arbitrary degree

For all non-negative integers n₁,n₂,n₃,j₁,j₂ and j₃ with nk+jk>1 for k=1,2,3, (nk,jk)≠(nl,jl) if k≠l, j₃=n₃−1 and jk≠nk−1 for k=1,2, we study the center variety of the 6-parameter family of real planar polynomial vector given, in complex notation, by , where z=x+iy and A,B,C∈C\{0}.     

The complex of non-crossing diagonals of a polygon

Given a convex n-gon P in R² with vertices in general position, it is well known that the simplicial complex θ(P) with vertex set given by diagonals in P and facets given by triangulations of P is the boundary complex of a polytope of dimension n−3. We prove that for any non-convex polygonal region P with n vertices and h+1 boundary components, θ(P) is a ball of dimension n+3h−4. We also provide a new proof that θ(P) is a sphere when P is convex with vertices in general position.     

Some graft transformations and its applications on the distance spectral radius of a graph

Let D(G)=(d_i,j)_n×n denote the distance matrix of a connected graph G with order n, where d_ij is equal to the distance between v_i and v_j in G. The largest eigenvalue of D(G) is called the distance spectral radius of graph G, denoted by ?(G). In this paper, some graft transformations that decrease or increase ?(G) are given. With them, for the graphs with both order n and k pendant vertices, the extremal graphs with the minimum distance spectral radius are completely characterized; the extremal graph with the maximum distance spectral radius is shown to be a dumbbell graph (obtained by attaching some pendant edges to each pendant vertex of a path respectively) when 2≤k≤n−2; for k=1,2,3,n−1, the extremal graphs with the maximum distance spectral radius are completely characterized.     

Multiple partitions, lattice paths and a Burge-Bressoud-type correspondence

A bijection is presented between (1): partitions with conditions f_j+f_j+1≤k−1 and f₁≤i−1, where f_j is the frequency of the part j in the partition, and (2): sets of k−1 ordered partitions (n⁽¹⁾,n⁽²⁾,…,n^(k−1)) such that and , where m_j is the number of parts in n^(j). This bijection entails an elementary and constructive proof of the Andrews multiple-sum enumerating partitions with frequency conditions. A very natural relation between the k−1 ordered partitions and restricted paths is also presented, which reveals our bijection to be a modification of Bressoud’s version of the Burge correspondence.     

Long cycles and paths in distance graphs

For n∈N and D⊆N, the distance graph has vertex set {0,1,…,n−1} and edge set {ij∣0≤i,j≤n−1,|j−i|∈D}. Note that the important and very well-studied circulant graphs coincide with the regular distance graphs.A fundamental result concerning circulant graphs is that for these graphs, a simple greatest common divisor condition, their connectivity, and the existence of a Hamiltonian cycle are all equivalent. Our main result suitably extends this equivalence to distance graphs. We prove that for a finite set D of order at least 2, there is a constant c_D such that the greatest common divisor of the integers in D is 1 if and only if for every n, has a component of order at least n−c_D if and only if for every n≥c_D+3, has a cycle of order at least n−c_D. Furthermore, we discuss some consequences and variants of this result.     

Boolean formulae, hypergraphs and combinatorial topology

With a view toward studying the homotopy type of spaces of Boolean formulae, we introduce a simplicial complex, called the theta complex, associated to any hypergraph, which is the Alexander dual of the more well-known independence complex. In particular, the set of satisfiable formulae in k-conjunctive normal form with ?n variables has the homotopy type of Θ(Cube(n,n−k)), where Cube(n,n−k) is a hypergraph associated to the (n−k)-skeleton of an n-cube. We make partial progress in calculating the homotopy type of theta for these cubical hypergraphs, and we also give calculations and examples for other hypergraphs as well. Indeed studying the theta complex of hypergraphs is an interesting problem in its own right.     

A new perspective on k-triangulations

We connect k-triangulations of a convex n-gon to the theory of Schubert polynomials. We use this connection to prove that the simplicial complex with k-triangulations as facets is a vertex-decomposable triangulated sphere, and we give a new proof of the determinantal formula for the number of k-triangulations.     

The spectra of some trees and bounds for the largest eigenvalue of any tree

Let T be an unweighted tree of k levels such that in each level the vertices have equal degree. Let n_k−j+1 and d_k−j+1 be the number of vertices and the degree of them in the level j. We find the eigenvalues of the adjacency matrix and Laplacian matrix of T for the case of two vertices in level 1 (n_k = 2), including results concerning to their multiplicity. They are the eigenvalues of leading principal submatrices of nonnegative symmetric tridiagonal matrices of order k × k. The codiagonal entries for these matrices are , 2 ? j ? k, while the diagonal entries are 0, …, 0, ±1, in the case of the adjacency matrix, and d₁, d₂, …, d_k−1, d_k ± 1, in the case of the Laplacian matrix. Finally, we use these results to find improved upper bounds for the largest eigenvalue of the adjacency matrix and of the Laplacian matrix of any given tree.     

Two equivalent measures on weighted hypergraphs

Let H=(N,E,w) be a hypergraph with a node set N={0,1,…,n-1}, a hyperedge set E⊆2^N, and real edge-weights w(e) for e∈E. Given a convex n-gon P in the plane with vertices x₀,x₁,…,x_n-1 which are arranged in this order clockwisely, let each node i∈N correspond to the vertex x_i and define the area A_P(H) of H on P by the sum of the weighted areas of convex hulls for all hyperedges in H. For 0?i<j<k?n-1, a convex three-cut C(i,j,k) of N is {{i,…,j-1}, {j,…,k-1}, {k,…,n-1,0,…,i-1}} and its size c_H(i,j,k) in H is defined as the sum of weights of edges e∈E such that e contains at least one node from each of {i,…,j-1}, {j,…,k-1} and {k,…,n-1,0,…,i-1}. We show that the following two conditions are equivalent:

•

A_P(H)?A_P(H^′) for all convex n-gons P.

•

c_H(i,j,k)?c_H^′(i,j,k) for all convex three-cuts C(i,j,k).

From this property, a polynomial time algorithm for determining whether or not given weighted hypergraphs H and H^′ satisfy “A_P(H)?A_P(H^′) for all convex n-gons P” is immediately obtained.     

Homology representations arising from the half cube

We construct a CW decomposition Cn of the n-dimensional half cube in a manner compatible with its structure as a polytope. For each 3?k?n, the complex Cn has a subcomplex Cn,k, which coincides with the clique complex of the half cube graph if k=4. The homology of Cn,k is concentrated in degree k−1 and furthermore, the (k−1)st Betti number of Cn,k is equal to the (k−2)nd Betti number of the complement of the k-equal real hyperplane arrangement. These Betti numbers, which also appear in theoretical computer science, numerical analysis and engineering, are the coefficients of a certain Pascal-like triangle (Sloane's sequence A119258). The Coxeter groups of type Dn act naturally on the complexes Cn,k, and thus on the associated homology groups.     

Tchebyshev triangulations of stable simplicial complexes

We generalize the notion of the Tchebyshev transform of a graded poset to a triangulation of an arbitrary simplicial complex in such a way that, at the level of the associated F-polynomials j_∑fj−1(j(x−1)/2), the triangulation induces taking the Tchebyshev transform of the first kind. We also present a related multiset of simplicial complexes whose association induces taking the Tchebyshev transform of the second kind. Using the reverse implication of a theorem by Schelin we observe that the Tchebyshev transforms of Schur stable polynomials with real coefficients have interlaced real roots in the interval (−1,1), and present ways to construct simplicial complexes with Schur stable F-polynomials. We show that the order complex of a Boolean algebra is Schur stable. Using and expanding the recently discovered relation between the derivative polynomials for tangent and secant and the Tchebyshev polynomials we prove that the roots of the corresponding pairs of derivative polynomials are all pure imaginary, of modulus at most one, and interlaced.     

Centers with degenerate infinity and their commutators

We study polynomial systems with degeneracy at infinity and a center-focus equilibrium at the origin. We give some general properties related to the existence of polynomial commutators and use these properties in order to characterize uniformly isochronous polynomial centers with polynomial commutator and, also, we show that the commutator of the centers of the analytic systems whose angular speed is constant can be chosen of radial form. Finally, we characterize the systems (−y+P_s+∑_j=kⁿ⁻¹xH_j,x+Q_s+∑_j=kⁿ⁻¹yH_j)^t with polynomial commutator, with P_j,Q_j,H_j and K_j homogeneous polynomials.     

Integers divisible by sums of powers of their prime factors

For each positive integer j, let βj(n):=_∑p|npj. Given a fixed positive integer k, we show that there are infinitely many positive integers n having at least two distinct prime factors and such that βj(n)|n for each j∈{1,2,…,k}.     

Regularity of subelliptic Monge-Ampère equations

In dimension n?3, for k≈|x|^2m that can be written as a sum of squares of smooth functions, we prove that a C² convex solution u to a subelliptic Monge-Ampère equation detD²u=k(x,u,Du) is itself smooth if the elementary (n−1)st symmetric curvature kn−1 of u is positive (the case m?2 uses an additional nondegeneracy condition on the sum of squares). Our proof uses the partial Legendre transform, Calabi's identity for ∑uijσij where σ is the square of the third order derivatives of u, the Campanato method Xu and Zuily use to obtain regularity for systems of sums of squares of Hörmander vector fields, and our earlier work using Guan's subelliptic methods.     

Unitary part of a contraction

For a contraction A on a Hilbert space H, we define the index j(A) (resp., k(A)) as the smallest nonnegative integer j (resp., k) such that ker(I−Aj∗Aj) (resp., ker(I−Ak*Ak)∩ker(I−AkAk∗)) equals the subspace of H on which the unitary part of A acts. We show that if , then j(A)?n (resp., k(A)?⌈n/2⌉), and the equality holds if and only if A is of class Sn (resp., one of the three conditions is true: (1) A is of class Sn, (2) n is even and A is completely nonunitary with ‖An−2‖=1 and ‖An−1‖<1, and (3) n is even and A=U⊕A^′, where U is unitary on a one-dimensional space and A^′ is of class Sn−1).     

Singular sets for curvature equation of order k

We consider the removability of singular sets for the curvature equations of the form Hk[u]=ψ, which is determined by the kth elementary symmetric function, in an n-dimensional domain Ω. We prove that, for 1?k?n−1 and a compact set K whose (n−k)-dimensional Hausdorff measure is zero, any generalized solution to the curvature equation on Ω?K is always extendable to a generalized solution on the whole domain Ω.     

Limit sets of automatic sequences

We show that for every k-automatic sequence there exists a natural number p>0 such that the sequences of the form (k^pn+j)_n?0 with j=0,…,p−1 are scaling sequences for f. Moreover, we demonstrate that every limit set is the union of certain basic limit sets.     

A combinatorial problem involving graphs and matrices

In this paper we discuss a combinatorial problem involving graphs and matrices. Our problem is a matrix analogue of the classical problem of finding a system of distinct representatives (transversal) of a family of sets and relates closely to an extremal problem involving 1-factors and a long standing conjecture in the dimension theory of partially ordered sets. For an integer n ?1, let n denote the n element set {1,2,3,…, n}. Then let A be a k×t matrix. We say that A satisfies property P(n, k) when the following condition is satisfied: For every k-taple (x₁,x₂,…,x_k?n^k there exist k distinct integers j₁,j₂,…,j_k so that x_i= a_ii for i= 1,2,…,k. The minimum value of t for which there exists a k × t matrix A satisfying property P(n,k) is denoted by f(n,k). For each k?1 and n sufficiently large, we give an explicit formula for f(n, k): for each n?1 and k sufficiently large, we use probabilistic methods to provide inequalities for f(n,k).