On the f- and h-triangle of the barycentric subdivision of a simplicial complex

For a simplicial complex Δ we study the behavior of its f- and h-triangle under the action of barycentric subdivision. In particular we describe the f- and h-triangle of its barycentric subdivision sd(Δ). The same has been done for f- and h-vector of sd(Δ) by F. Brenti, V. Welker (2008). As a consequence we show that if the entries of the h-triangle of Δ are nonnegative, then the entries of the h-triangle of sd(Δ) are also nonnegative. We conclude with a few properties of the h-triangle of sd(Δ).     

Maximizing a lower bound on the computational complexity

We solve a combinatorial problem that arises in determining by a method due to Engeler lower bounds for the computational complexity of algorithmic problems. Denote by G_d the class of permutation groups G of degree d that are iterated wreath products of symmetric groups, i.e. G = S_dh?11?1S_d0 with Π^h?1_i=0d_i = d for some natural number h and some sequence (d₀,…,d_h?1) of natural numbers greater than 1. The problem is to characterize those G = S_dh?11?1S_d0 in G_d on which k(G):=log|G|/max_0≤i≤h?1log(d_i!) assumes its maximum. Our solution consists of two necessary conditions for this, namely that d₀≤d₁≤?≤d_h and that d_h is the largest prime divisor of d. Consequently, if d is a prime power, say d = p^h with p prime, then a necessary and sufficient condition is that d_i = p, 0 ≤ i ≤ h ? 1.     

Root Sublattices and Torus-Restriction of Prehomogeneous Vector Spaces Associated with Dynkin Quivers

For a Dynkin quiver Γ with r vertices, a subset S of the vertices of Γ, and an r-tuple d = (d⁽¹⁾, d⁽²⁾,…, d^(r)) of positive integers, we define a “torus-restricted” representation (G_S, R _d (Γ)) in natural way. Here we put G_S = G₁ × G₂ × … ×G_r, where each G_i is either SL(d⁽ⁱ⁾) or GL(d⁽ⁱ⁾) according to S containing i or not. In this paper, for a prescribed torus-restriction S, we give a necessary and sufficient condition on d that R _d (Γ) has only finitely many G_S-orbits. This can be paraphrased as a condition whether or not d is contained in a certain lattice spanned by positive roots of Γ. We also discuss the prehomogeneity of (G_S, R _d (Γ)).     

Face numbers and the fundamental group

We resolve a conjecture of Kalai asserting that the g ₂-number of any (finite) simplicial complex Δ that represents a normal pseudomanifold of dimension d ≥ 3 is at least as large as \(\left( {\begin{array}{*{20}{c}} {d + 2} \\ 2 \end{array}} \right)m\left( \Delta \right)\), where m(Δ) denotes the minimum number of generators of the fundamental group of Δ. Furthermore, we prove that a weaker bound, \({h_2}\left( \Delta \right) \geqslant \left( {\begin{array}{*{20}{c}} {d + 1} \\ 2 \end{array}} \right)m\left( \Delta \right)\), applies to any d-dimensional pure simplicial poset Δ all of whose faces of co-dimension ≥ 2 have connected links. This generalizes a result of Klee. Finally, for a pure relative simplicial poset Ψ all of whose vertex links satisfy Serre’s condition (S _r ), we establish lower bounds on h ₁(Ψ),...,h _r (Ψ) in terms of the μ-numbers introduced by Bagchi and Datta.     

Job shop scheduling with unit time operations under resource constraints and release dates

We consider the problem of job shop scheduling with m machines and n jobs J_i, each consisting of l_i unit time operations. There are s distinct resources R_h and a quantity q_h available of each one. The execution of the j-th operation of J_i requires the presence of u_ijh units of R_h, 1 ≤i≤n, 1 ≤j≤l_i, and 1 ≤h≤s. In addition, each J_i has a release date r_i, that is J_i cannot start before time r_i. We describe algorithms for finding schedules having minimum length or sum of completion times of the jobs. Let l=max{l_i} and u=|{u_ijh}|. If m, u and l are fixed, then both algorithms terminate within polynomial time.     

The Relaxed Edge-Coloring Game and <Emphasis Type="Italic">k</Emphasis>-Degenerate Graphs

The (r, d)-relaxed edge-coloring game is a two-player game using r colors played on the edge set of a graph G. We consider this game on forests and more generally, on k-degenerate graphs. If F is a forest with Δ(F)=Δ, then the first player, Alice, has a winning strategy for this game with r=Δ?j and d≥2j+2 for 0≤j≤Δ?1. This both improves and generalizes the result for trees in Dunn, C. (Discret. Math. 307, 1767–1775, 2007). More broadly, we generalize the main result in Dunn, C. (Discret. Math. 307, 1767–1775, 2007) by showing that if G is k-degenerate with Δ(G)=Δ and j∈[Δ+k?1], then there exists a function h(k,j) such that Alice has a winning strategy for this game with r=Δ+k?j and d≥h(k,j).     

Hamiltonian threshold graphs

The vertices of a threshold graph G are partitioned into a clique K and an independent set I so that the neighborhoods of the vertices of I are totally ordered by inclusion. The question of whether G is hamiltonian is reduced to the case that K and I have the same size, say r, in which case the edges of K do not affect the answer and may be dropped from G, yielding a bipartite graph B. Let d₁≤d₂≤…≤d_r and e₁≤e₂≤…≤e_r be the degrees in B of the vertices of I and K, respectively. For each q = 0, 1,…,r−1, denote by S_q the following system of inequalities: d_j⩾j + 1, j = 1,2,…,q, e_j⩾j + 1, j = 1, 2,…, r−1−1. Then the following conditions are equivalent:

• 1.(1) B is hamiltonian,
• 2.(2) S_q holds for some q = 0, 1,…, r−1,
• 3.(3) S_q holds for each q = 0, 1,…, r−1.

     

A Characterization of the Hamming Graphs and the Dual Polar Graphs by Completely Regular Subgraphs

In this paper we study a distance-regular graph Γ of diameter d ≥? 3 which satisfies the following two conditions: (a) For any integer i with 1 ≤? i ≤? d ? 1 and for any pair of vertices at distance i in Γ there exists a strongly closed subgraph of diameter i containing them; (b) There exists a strongly closed subgraph Δ which is completely regular in Γ. It is known that if Δ has diameter 1, then Γ is a regular near polygon. We prove that if a strongly closed subgraph Δ of diameter j with 2 ≤? j ≤? d ? 1 is completely regular of covering radius d ? j in Γ, then Γ is either a Hamming graph or a dual polar graph.     

Prime interchange graphs of classes of matrices of zeros and ones

Let R = (r₁,…, r_m) and S = (s₁,…, s_n) be nonnegative integral vectors, and let $\text{U}$(R, S) denote the class of all m × n matrices of 0's and 1's having row sum vector R and column sum vector S. An invariant position of $\text{U}$(R, S) is a position whose entry is the same for all matrices in $\text{U}$(R, S). The interchange graph G(R, S) is the graph where the vertices are the matrices in $\text{U}$(R, S) and where two matrices are joined by an edge provided they differ by an interchange. We prove that when 1 ≤ r_i ≤ n ? 1 (i = 1,…, m) and 1 ≤ s_j ≤ m ? 1 (j = 1,…, n), G(R, S) is prime if and only if $\text{U}$(R, S) has no invariant positions.     

Quasigroups defining Eulerian paths in complete graphs

This paper provides a graph theoretical contribution to the solution of a problem that was so far dealt with purely combinatorial methods: For which values of r does a P-quasigroup exist which defines an Eulerian path in the complete graph K_{2r + 1}? We start with a nearly linear factor F₀ whose edges are all of different “lengths” and obtain a rotative partition of K_{2r + 1} into nearly linear factors. At every vertex V_h, the 2r edges adjacent to V_h are thus partitioned into r transitions. Successive transitions so defined by F₀ are associated to edges of F₀ forming a sequence of the form (?i₀, i₁), (?i₁, i₂), (?i₂, i₃),…. If S is any closed path made up of these successive transitions, then S is described cyclically by a transition sequence of edges of F₀ of the form: I(S) = {(?i₀, i₁), (?i₁, i₂),…, (?i_t?1, i₀)}, used cyclically m times; S is Eulerian if and only if m = 2r + 1 and t = r. In particular, if t = r and G.C.D. (Σ_{j = 1}^ri_j, 2r + 1) = 1, then I(S) describes an Eulerian path. A numerical example is given, which solves the given problem whenever 2r + 10 (mod 7). Incidentally, Kotzig has shown that the problem has no solution when r = 2.     

A dimension series for multivariate splines

For a polyhedral subdivision Δ of a region in Euclideand-space, we consider the vector spaceC _k ^r (Δ) consisting of allC ^r piecewise polynomial functions over Δ of degree at mostk. We consider the formal power series ∑ _k≥0 dim_? C _k ^r (Δ)λ^k and show, under mild conditions on Δ, that this always has the formP(λ)/(1?λ) ^d+1, whereP(λ) is a polynomial in λ with integral coefficients which satisfiesP(0)=1,P(1)=f _d (Δ), andP′(1)=(r+1)f _d?1 ⁰ (Δ). We discuss how the polynomialP(λ) and bases for the spacesC _k ^r (Δ) can be effectively calculated by use of Gröbner basis techniques of computational commutative algebra. A further application is given to the theory of hyperplane arrangements.     

Equidistribution of Hecke Eigenforms on the Arithmetic Surface Γ0(N)\H

Given the orthonormal basis of Hecke eigenforms in S_2k(Γ(1)), Luo established an associated probability measure dμ_k on the modular surface Γ(1)\H that tends weakly to the invariant measure on Γ(1)\H. We generalize his result to the arithmetic surface Γ₀(N)\H where N?1 is square-free     

On the generalized lower bound conjecture for polytopes and spheres

In 1971, McMullen and Walkup posed the following conjecture, which is called the generalized lower bound conjecture: If P is a simplicial d-polytope then its h-vector (h ₀, h ₁, …, h _d ) satisfies $ {h_0}\leq {h_1}\leq \ldots \leq {h_{{\left\lfloor {{d \left/ {2} \right.}} \right\rfloor }}} $ . Moreover, if h _r?1 = h _r for some $ r\leq \frac{1}{2}d $ then P can be triangulated without introducing simplices of dimension ≤d ? r. The first part of the conjecture was solved by Stanley in 1980 using the hard Lefschetz theorem for projective toric varieties. In this paper, we give a proof of the remaining part of the conjecture. In addition, we generalize this result to a certain class of simplicial spheres, namely those admitting the weak Lefschetz property.     

On Erdos' ten-point problem

Around 1994, Erdoset al. abstracted from their work the following problem: “Given ten pointsA _ij, 1≤i≤j≤5, on a plane and no three of them being collinear, if there are five pointsA _k, 1≤k≤5, on the plane, including points at infinity, with at least two points distinct, such thatA _i, A_j, A_ij are collinear, where 1≤i≤j≤5, is it true that there are only finitely many suchA _k's?” Erdoset al. obtained the result that generally there are at most 49 groups of suchA _k's. In this paper, using Clifford algebra and Wu's method, we obtain the results that generally there are at most 6 such groups ofA _k's.     

Solving polynomial optimization problems via the truncated tangency variety and sums of squares

Let f,g_i,i=1,…,l,h_j,j=1,…,m, be polynomials on Rⁿ and S?{x∈Rⁿ∣g_i(x)=0,i=1,…,l,h_j(x)≥0,j=1,…,m}. This paper proposes a method for finding the global infimum of the polynomial f on the semialgebraic set S via sum of squares relaxation over its truncated tangency variety, even in the case where the polynomial f does not attain its infimum on S. Under a constraint qualification condition, it is demonstrated that: (i) The infimum of f on S and on its truncated tangency variety coincide; and (ii) A sums of squares certificate for nonnegativity of f on its truncated tangency variety. These facts imply that we can find a natural sequence of semidefinite programs whose optimal values converge, monotonically increasing to the infimum of f on S.     

Stop rule and supremum expectations of i.i.d. random variables: A complete comparison by conjugate duality

A complete comparison is made between the value V(X₁,…, X_n) = sup{EX_t: t is a stop rule for X₁,…,X_n} and E(max_{j ≤ n}X_j) for all uniformly bounded sequences of i.i.d. random variables X₁, …, X_n. Specifically, the set of ordered pairs {(x,y): x = V(X₁, …, X_n) and y = E(max_j≤nX_j) for some i.i.d.r.v.'s X₁,…, X_n taking values in [0, 1]} is precisely the set {(x, y): x≤y≤Γ_n(x); 0 ≤x≤1}, where the upper boundary function Γ_n is given in terms of recursively defined functions. The result yields families of inequalities for the “prophet” problem, relating the motal's value of a game V(X₁, …, X_n) to the prophet's value of the game E(max_j≤nX_j). The proofs utilize conjugate duality theory, probabilistic convexity arguments, and functional equation analysis. Asymptotic analysis of the “prophet” regions and inequalities is also given.     

Multiresolution expansion, approximation order and quasiasymptotic behavior of tempered distributions

Multiresolution analysis of tempered distributions is studied through multiresolution analysis on the corresponding test function spaces Sr(R), r∈N₀. For a function h, which is smooth enough and of appropriate decay, it is shown that the derivatives of its projections to the corresponding spaces Vj, j∈Z, in a regular multiresolution analysis of L²(R), denoted by hj, multiplied by a polynomial weight converge in sup norm, i.e., hj→h in Sr(R) as j→∞. Analogous result for tempered distributions is obtained by duality arguments. The analysis of the approximation order of the projection operator within the framework of the theory of shift-invariant spaces gives a further refinement of the results. The order of approximation is measured with respect to the corresponding space of test functions. As an application, we give Abelian and Tauberian type theorems concerning the quasiasymptotic behavior of a tempered distribution at infinity.     

Non-local Dirichlet forms generated by pseudodifferential operators on compact abelian groups

Let G_i, 1 ≤ i ≤ n, be compact abelian groups and let Γ_i , 1 ≤ i ≤ n, be countable dual groups. We consider G = G₁ ⊕ G₂ ⊕ … ⊕ G_n and Γ = Γ₁ ⊕ Γ₂ ⊕ … ⊕ Γ_n . For 1 ≤ j ≤ n, let a_j be a negative definite function on Γ_j and a (γ) = . For φ ∈ S (G), the set of all generalized trigonometrical polynomials on G, we define , where (γ) = a_j (γ_j) (γ), 1 ≤ j ≤ n. Then is a Dirichlet form with the domain on L² (G). (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

The Stability in W s,p (Γ) Spaces of L 2-Projections on Some Convex Sets

ABSTRACT

For a polygonal open bounded subset of ?², of boundary Γ, we study stability estimates for the projection operator from L ¹(Γ) on a convex set K _h of continuous piecewise affine functions satisfying bound constraints. We establish stability estimates in L ^p (Γ) and in W ^s,p (Γ) for 1 ≤ p ≤ ∞ and 0 < s ≤ 1. This kind of result plays a crucial role in error estimates for the numerical approximation of optimal control problems of partial differential equations with bilateral control constraints.     

The extended gamma class and applications

The gamma class Γ _α (g) consists of positive and measurable functions that satisfy f(x+yg(x))/f(x)→exp(αy). In most cases, the auxiliary function g is Beurling varying, i.e. g(x)/x→0 and g∈Γ₀(g). Taking h=logf, we find that h∈EΓ _α (g,1), where EΓ _α (g,a) is the class of ultimately positive and measurable functions that satisfy (f(x+yg(x))?f(x))/a(x)→αy. In this paper, we discuss local uniform convergence for functions in the classes Γ _α (g) and EΓ _α (g,a). From this we obtain several representation theorems. We also prove some higher order relations for functions in the classes Γ _α (g) and EΓ _α (g,a). Some applications conclude the paper.