Graham’s pebbling conjecture on product of thorn graphs of complete graphs

The pebbling number of a graph G, f(G), is the least n such that, no matter how n pebbles are placed on the vertices of G, we can move a pebble to any vertex by a sequence of pebbling moves, each move taking two pebbles off one vertex and placing one on an adjacent vertex. Let p₁,p₂,…,p_n be positive integers and G be such a graph, V(G)=n. The thorn graph of the graph G, with parameters p₁,p₂,…,p_n, is obtained by attaching p_i new vertices of degree 1 to the vertex u_i of the graph G, i=1,2,…,n. Graham conjectured that for any connected graphs G and H, f(G×H)≤f(G)f(H). We show that Graham’s conjecture holds true for a thorn graph of the complete graph with every by a graph with the two-pebbling property. As a corollary, Graham’s conjecture holds when G and H are the thorn graphs of the complete graphs with every .     

Endomorphisms of the shift dynamical system, discrete derivatives, and applications

All continuous endomorphisms f_∞ of the shift dynamical system S on the 2-adic integers Z₂ are induced by some , where n is a positive integer, B_n is the set of n-blocks over {0, 1}, and f_∞(x)=y₀y₁y₂… where for all i∈N, y_i=f(x_ix_i+1…x_i+n−1). Define D:Z₂→Z₂ to be the endomorphism of S induced by the map {(00,0),(01,1),(10,1),(11,0)} and V:Z₂→Z₂ by V(x)=−1−x. We prove that D, V°D, S, and V°S are conjugate to S and are the only continuous endomorphisms of S whose parity vector function is solenoidal. We investigate the properties of D as a dynamical system, and use D to construct a conjugacy from the 3x+1 function T:Z₂→Z₂ to a parity-neutral dynamical system. We also construct a conjugacy R from D to T. We apply these results to establish that, in order to prove the 3x+1 conjecture, it suffices to show that for any m∈Z⁺, there exists some n∈N such that R⁻¹(m) has binary representation of the form or .     

The Conley conjecture for Hamiltonian systems on the cotangent bundle and its analogue for Lagrangian systems

In this paper, the Conley conjecture, which was recently proved by Franks and Handel [J. Franks, M. Handel, Periodic points of Hamiltonian surface diffeomorphism, Geom. Topol. 7 (2003) 713-756] (for surfaces of positive genus), Hingston [N. Hingston, Subharmonic solutions of Hamiltonian equations on tori, Ann. Math., in press] (for tori) and Ginzburg [V.L. Ginzburg, The Conley conjecture, arXiv: math.SG/0610956v1] (for closed symplectically aspherical manifolds), is proved for C¹-Hamiltonian systems on the cotangent bundle of a C³-smooth compact manifold M without boundary, of a time 1-periodic C²-smooth Hamiltonian H:R×T^*M→R which is strongly convex and has quadratic growth on the fibers. Namely, we show that such a Hamiltonian system has an infinite sequence of contractible integral periodic solutions such that any one of them cannot be obtained from others by iterations. If H also satisfies H(−t,q,−p)=H(t,q,p) for any (t,q,p)∈R×T^*M, it is shown that the time-1-map of the Hamiltonian system (if exists) has infinitely many periodic points siting in the zero section of T^*M. If M is C⁵-smooth and dimM>1, H is of C⁴ class and independent of time t, then for any τ>0 the corresponding system has an infinite sequence of contractible periodic solutions of periods of integral multiple of τ such that any one of them cannot be obtained from others by iterations or rotations. These results are obtained by proving similar results for the Lagrangian system of the Fenchel transform of H, L:R×TM→R, which is proved to be strongly convex and to have quadratic growth in the velocities yet.     

Leading coefficients of Kazhdan–Lusztig polynomials for Deodhar elements

We show that the leading coefficient of the Kazhdan–Lusztig polynomial P _x,w (q) known as μ(x,w) is always either 0 or 1 when w is a Deodhar element of a finite Weyl group. The Deodhar elements have previously been characterized using pattern avoidance in Billey and Warrington (J. Algebraic Combin. 13(2):111–136, [2001]) and Billey and Jones (Ann. Comb. [2008], to appear). In type A, these elements are precisely the 321-hexagon avoiding permutations. Using Deodhar’s algorithm (Deodhar in Geom. Dedicata 63(1):95–119, [1990]), we provide some combinatorial criteria to determine when μ(x,w)=1 for such permutations w. The author received support from NSF grants DMS-9983797 and DMS-0636297.     

On Hua-Tuan’s conjecture

Let G be a finite group and |G| = pn, p be a prime. For 0 m n, sm(G) denotes the number of subgroups of of order pm of G. Loo-Keng Hua and Hsio-Fu Tuan have ever conjectured: for an arbitrary finite p-group G, if p > 2, then sm(G) ≡ 1, 1 + p, 1 + p + p2 or 1 + p + 2p2 (mod p3). In this paper, we investigate the conjecture, and give some p-groups in which the conjecture holds and some examples in which the conjecture does not hold.     

A variation of a conjecture due to Erdös and Sós

Erdoes and Soes conjectured in 1963 that every graph G on n vertices with edge number e（G） 〉 1/2（k - 1）n contains every tree T with k edges as a subgraph. In this paper, we consider a variation of the above conjecture, that is, for n 〉 9/ 2k^2 ＋ 37/2＋ 14 and every graph G on n vertices with e（G） 〉 1/2 （k- 1）n, we prove that there exists a graph G＇ on n vertices having the same degree sequence as G and containing every tree T with k edges as a subgraph.     

On the Brown–Shields conjecture for cyclicity in the Dirichlet space

Let be the Dirichlet space, namely the space of holomorphic functions on the unit disk whose derivative is square-integrable. We establish a new sufficient condition for a function to be cyclic, i.e. for to be dense in . This allows us to prove a special case of the conjecture of Brown and Shields that a function is cyclic in iff it is outer and its zero set (defined appropriately) is of capacity zero.     

A note on the strength and minimum color sum of bipartite graphs

The strength of a graph G is the smallest integer s such that there exists a minimum sum coloring of G using integers {1,…,s}, only. For bipartite graphs of maximum degree Δ we show the following simple bound: s≤⌈Δ/2⌉+1. As a consequence, there exists a quadratic time algorithm for determining the strength and minimum color sum of bipartite graphs of maximum degree Δ≤4.     

Restricted set addition: The exceptional case of the Erd?s-Heilbronn conjecture

Let A≠B be nonempty subsets of the group of integers modulo a prime p. If p?|A|+|B|−2, then at least |A|+|B|−2 different residue classes can be represented as a+b, where a∈A, b∈B and a≠b. This result complements the solution of a problem of Erd?s and Heilbronn obtained by Alon, Nathanson, and Ruzsa.     

On Fraïssé’s conjecture for linear orders of finite Hausdorff rank

We prove that the maximal order type of the wqo of linear orders of finite Hausdorff rank under embeddability is φ₂(0), the first fixed point of the ε-function. We then show that Fraïssé’s conjecture restricted to linear orders of finite Hausdorff rank is provable in  +“φ₂(0) is well-ordered” and, over , implies  +“φ₂(0) is well-ordered”.