Upper triangular operator matrices with the single-valued extension property

If A=(Aij)_1?i,j?n∈B(X) is an upper triangular Banach space operator such that AiiAij=AijAjj for all 1?i?j?n, then A has SVEP or satisfies (Dunford's) condition (C) or (Bishop's) property (β) or (the decomposition) property (δ) if and only if Aii, 1?i?n, has the corresponding property.     

Group actions and Helly's theorem

We describe a connection between the combinatorics of generators for certain groups and the combinatorics of Helly's 1913 theorem on convex sets. We use this connection to prove fixed point theorems for actions of these groups on nonpositively curved metric spaces. These results are encoded in a property that we introduce called “property FAr”, which reduces to Serre's property FA when r=1. The method applies to S-arithmetic groups in higher Q-rank, to simplex reflection groups (including some nonarithmetic ones), and to higher rank Chevalley groups over polynomial and other rings (for example SLn(Z[x₁,…,xd]), n>2).     

A degree sum condition for graphs to be prism hamiltonian

Win, in 1975, and Jackson and Wormald, in 1990, found the best sufficient conditions on the degree sum of a graph to guarantee the properties of “having a k-tree” and “having a k-walk”, respectively. The property of “being prism hamiltonian” is an intermediate property between “having a 2-tree” and “having a 2-walk”. Thus, it is natural to ask what is the best degree sum condition for graphs to be prism hamiltonian. As an answer to this problem, in this paper, we show that a connected graph G of order n with σ₃(G)≥n is prism hamiltonian. The degree sum condition “σ₃(G)≥n” is best possible.     

A multiply intersecting Erd?s-Ko-Rado theorem — The principal case

Let m(n,k,r,t) be the maximum size of satisfying |F₁∩?∩F_r|≥t for all F₁,…,F_r∈F. We prove that for every p∈(0,1) there is some r₀ such that, for all r>r₀ and all t with 1≤t≤⌊(p^1−r−p)/(1−p)⌋−r, there exists n₀ so that if n>n₀ and p=k/n, then . The upper bound for t is tight for fixed p and r.     

Maximal Sidon sets and matroids

A subset X of an abelian group Γ, written additively, is a Sidon set of orderh if whenever {(a_i,m_i):i∈I} and {(b_j,n_j):j∈J} are multisets of size h with elements in X and ∑_i∈Im_ia_i=∑_j∈Jn_jb_j, then {(a_i,m_i):i∈I}={(b_j,n_j):j∈J}. The set X is a generalized Sidon set of order(h,k) if whenever two such multisets have the same sum, then their multiset intersection has size at least k. It is proved that if X is a generalized Sidon set of order (2h−1,h−1), then the maximal Sidon sets of order h contained in X have the same cardinality. Moreover, X is a matroid where the independent subsets of X are the Sidon sets of order h.     

Linear-time certifying algorithms for near-graphical sequences

A sequence 〈d₁,d₂,…,d_n〉 of non-negative integers is graphical if it is the degree sequence of some graph, that is, there exists a graph G on n vertices whose ith vertex has degree d_i, for 1≤i≤n. The notion of a graphical sequence has a natural reformulation and generalization in terms of factors of complete graphs.If H=(V,E) is a graph and g and f are integer-valued functions on the vertex set V, then a (g,f)-factor of H is a subgraph G=(V,F) of H whose degree at each vertex v∈V lies in the interval [g(v),f(v)]. Thus, a (0,1)-factor is just a matching of H and a (1, 1)-factor is a perfect matching of H. If H is complete then a (g,f)-factor realizes a degree sequence that is consistent with the sequence of intervals 〈[g(v₁),f(v₁)],[g(v₂),f(v₂)],…,[g(v_n),f(v_n)]〉.Graphical sequences have been extensively studied and admit several elegant characterizations. We are interested in extending these characterizations to non-graphical sequences by introducing a natural measure of “near-graphical”. We do this in the context of minimally deficient (g,f)-factors of complete graphs. Our main result is a simple linear-time greedy algorithm for constructing minimally deficient (g,f)-factors in complete graphs that generalizes the method of Hakimi and Havel (for constructing (f,f)-factors in complete graphs, when possible). It has the added advantage of producing a certificate of minimum deficiency (through a generalization of the Erdös-Gallai characterization of (f,f)-factors in complete graphs) at no additional cost.     

The Independence Number for De Bruijn networks and Kautz networks

Let D be a directed graph; the (l,ω)-Independence Number of graph D, denoted by α_l,ω(D), is an important performance parameter for interconnection networks. De Bruijn networks and Kautz networks, denoted by B(d,n) and K(d,n) respectively, are versatile and efficient topological structures of interconnection networks. For l=1,2,…,n, this paper shows that α_l,d−1(B(d,n))=dⁿ,α_l,d−1(K(d,n))=α_l,d(K(d,n))=dⁿ+dⁿ⁻¹ if d≥3 and n≤d−2. In particular, the paper shows the exact value of the Independence Number for B(d,1) and B(d,2) for any d. For the generalized situation, the paper obtains a lower bound α_l,d−1(B(d,n))≥d² if n≥3 and d≥5.     

Riesz transforms and conjugacy for Laguerre function expansions of Hermite type

Riesz transforms and conjugate Poisson integrals for multi-dimensional Laguerre function expansions of Hermite type with index α are defined and investigated. It is proved that for any multi-index α=(α₁,…,αd) such that αi?−1/2, αi∉(−1/2,1/2), the appropriately defined Riesz transforms , j=1,2,…,d, are Calderón-Zygmund operators, hence their mapping properties follow from a general theory. Similar mapping results are obtained in one dimension, without excluding α∈(−1/2,1/2), by means of a local Calderón-Zygmund theory and weighted Hardy's inequalities. The conjugate Poisson integrals are shown to satisfy a system of Cauchy-Riemann type equations and to recover the Riesz-Laguerre transforms on the boundary. The two specific values of α, (−1/2,…,−1/2) and (1/2,…,1/2), are distinguished since then a connection with Riesz transforms for multi-dimensional Hermite function expansions is established.     

Graphic sequences with a realization containing a generalized friendship graph

Gould, Jacobson and Lehel [R.J. Gould, M.S. Jacobson, J. Lehel, Potentially G-graphical degree sequences, in: Y. Alavi, et al. (Eds.), Combinatorics, Graph Theory and Algorithms, vol. I, New Issues Press, Kalamazoo, MI, 1999, pp. 451-460] considered a variation of the classical Turán-type extremal problems as follows: for any simple graph H, determine the smallest even integer σ(H,n) such that every n-term graphic sequence π=(d₁,d₂,…,d_n) with term sum σ(π)=d₁+d₂+?+d_n≥σ(H,n) has a realization G containing H as a subgraph. Let F_t,r,k denote the generalized friendship graph on kt−kr+r vertices, that is, the graph of k copies of K_t meeting in a common r set, where K_t is the complete graph on t vertices and 0≤r≤t. In this paper, we determine σ(F_t,r,k,n) for k≥2, t≥3, 1≤r≤t−2 and n sufficiently large.     

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 .     

Least and most colored bases

Consider a matroid M=(E,B), where B denotes the family of bases of M, and assign a color c(e) to every element e∈E (the same color can go to more than one element). The palette of a subset F of E, denoted by c(F), is the image of F under c. Assume also that colors have prices (in the form of a function π(?), where ? is the label of a color), and define the chromatic price as: π(F)=∑_?∈c(F)π(?). We consider the following problem: find a base B∈B such that π(B) is minimum. We show that the greedy algorithm delivers a lnr(M)-approximation of the unknown optimal value, where r(M) is the rank of matroid M. By means of a reduction from SETCOVER, we prove that the lnr(M) ratio cannot be further improved, even in the special case of partition matroids, unless . The results apply to the special case where M is a graphic matroid and where the prices π(?) are restricted to be all equal. This special case was previously known as the minimum label spanning tree (MLST) problem. For the MLST, our results improve over the ln(n-1)+1 ratio achieved by Wan, Chen and Xu in 2002. Inspired by the generality of our results, we study the approximability of coloring problems with different objective function π(F), where F is a common independent set on matroids M₁,…,M_k and, more generally, to independent systems characterized by the k-for-1 property.     

Nonlinear dissipative wave equations with space-time dependent potential

We study the long time behavior of solutions for damped wave equations with absorption. These equations are generally accepted as models of wave propagation in heterogeneous media with space-time dependent friction a(t,x)u_t and nonlinear absorption |u|^p−1u (Ikawa (2000) [17]). We consider 1<p<(n+2)/(n−2) and separable a(t,x)=λ(x)η(t) with λ(x)∼(1+|x|)^−α and η(t)∼(1+t)^−β satisfying conditions (A1) or (A2) which are given. The main results are precise decay estimates for the energy, L² and L^p+1 norms of solutions. We also observe the following behavior: if α∈[0,1), β∈(−1,1) and 0<α+β<1, there are three different regions for the decay of solutions depending on p; if α∈(−∞,0) and β∈(−1,1), there are only two different regions for the decay of the solutions depending on p.     

Solutions of non-periodic super-quadratic Dirac equations

This paper is concerned with solutions to the Dirac equation: −i∑αkk_∂u+aβu+M(x)u=Ru(x,u). Here M(x) is a general potential and R(x,u) is a self-coupling which is super-quadratic in u at infinity. We use variational methods to study this problem. By virtue of some auxiliary system related to the “limit equation” of the Dirac equation, we construct linking levels of the variational functional ΦM such that the minimax value cM based on the linking structure of ΦM satisfies , where is the least energy of the “limit equation”. Thus we can show the c(C)-condition holds true for all and consequently obtain one least energy solution to the Dirac equation.     

A distance-labelling problem for hypercubes

Let i₁≥i₂≥i₃≥1 be integers. An L(i₁,i₂,i₃)-labelling of a graph G=(V,E) is a mapping ?:V→{0,1,2,…} such that |?(u)−?(v)|≥i_t for any u,v∈V with d(u,v)=t, t=1,2,3, where d(u,v) is the distance in G between u and v. The integer ?(v) is called the label assigned to v under ?, and the difference between the largest and the smallest labels is called the span of ?. The problem of finding the minimum span, λ_i1,i2,i3(G), over all L(i₁,i₂,i₃)-labellings of G arose from channel assignment in cellular communication systems, and the related problem of finding the minimum number of labels used in an L(i₁,i₂,i₃)-labelling was originated from recent studies on the scalability of optical networks. In this paper we study the L(i₁,i₂,i₃)-labelling problem for hypercubes Q_d (d≥3) and obtain upper and lower bounds on λ_i1,i2,i3(Q_d) for any (i₁,i₂,i₃).     

Frame cellular automata: Configurations, generating sets and related matroids

We introduce a frame cellular automaton as a broad generalization of an earlier study on quasigroup-defined cellular automata. It consists of a triple (F,R,E_F) where, for a given finite set X of cells, the frame F is a family of subsets of X (called elementary frames, denoted S_i, i=1,…,n), which is a cover of X. A matching configuration is a map which attributes to each cell a state in a finite set G under restriction of a set of local rules R={R_i∣i=1,…n}, where R_i holds in the elementary frame S_i and is determined by an (|S_i|-1)-ary quasigroup over G. The frame associated map E_F models how a matching configuration can be grown iteratively from a certain initial cell-set. General properties of frames and related matroids are investigated. A generating set S⊂X is a set of cells such that there is a bijection between the collection of matching configurations and G^S. It is shown that for certain frames, the algebraically defined generating sets are bases of a related geometric-combinatorially defined matroid.     

Bounds on isoperimetric values of trees

Let G=(V,E) be a finite, simple and undirected graph. For S⊆V, let δ(S,G)={(u,v)∈E:u∈S and v∈V−S} be the edge boundary of S. Given an integer i, 1≤i≤|V|, let the edge isoperimetric value of G at i be defined as b_e(i,G)=min_S⊆V;|S|=i|δ(S,G)|. The edge isoperimetric peak of G is defined as b_e(G)=max_1≤j≤|V|b_e(j,G). Let b_v(G) denote the vertex isoperimetric peak defined in a corresponding way. The problem of determining a lower bound for the vertex isoperimetric peak in complete t-ary trees was recently considered in [Y. Otachi, K. Yamazaki, A lower bound for the vertex boundary-width of complete k-ary trees, Discrete Mathematics, in press (doi:10.1016/j.disc.2007.05.014)]. In this paper we provide bounds which improve those in the above cited paper. Our results can be generalized to arbitrary (rooted) trees.The depth d of a tree is the number of nodes on the longest path starting from the root and ending at a leaf. In this paper we show that for a complete binary tree of depth d (denoted as ), and where c₁, c₂ are constants. For a complete t-ary tree of depth d (denoted as ) and d≥clogt where c is a constant, we show that and where c₁, c₂ are constants. At the heart of our proof we have the following theorem which works for an arbitrary rooted tree and not just for a complete t-ary tree. Let T=(V,E,r) be a finite, connected and rooted tree — the root being the vertex r. Define a weight function w:V→N where the weight w(u) of a vertex u is the number of its successors (including itself) and let the weight index η(T) be defined as the number of distinct weights in the tree, i.e η(T)=|{w(u):u∈V}|. For a positive integer k, let ?(k)=|{i∈N:1≤i≤|V|,b_e(i,G)≤k}|. We show that .     

Mapping properties for oscillatory integrals in d-dimensions

For aj,bj?1, j=1,2,…,d, we prove that the operator maps into itself for , where , and k(x,y)=φ(x,y)eig(x,y), φ(x,y) satisfies (1.2) (e.g. φ(x,y)=|x−y|^iτ,τ real) and the phase g(x,y)=xa⋅yb. We study operators with more general phases and for these operators we require that aj,bj>1, j=1,2,…,d, or al=bl?1 for some l∈{1,2,…,d}.     

The hardness of approximating the boxicity, cubicity and threshold dimension of a graph

A k-dimensional box is the Cartesian product R₁×R₂×?×R_k where each R_i is a closed interval on the real line. The boxicity of a graph G, denoted as , is the minimum integer k such that G can be represented as the intersection graph of a collection of k-dimensional boxes. A unit cube in k-dimensional space or a k-cube is defined as the Cartesian product R₁×R₂×?×R_k where each R_i is a closed interval on the real line of the form [a_i,a_i+1]. The cubicity of G, denoted as , is the minimum integer k such that G can be represented as the intersection graph of a collection of k-cubes. The threshold dimension of a graph G(V,E) is the smallest integer k such that E can be covered by k threshold spanning subgraphs of G. In this paper we will show that there exists no polynomial-time algorithm for approximating the threshold dimension of a graph on n vertices with a factor of O(n^0.5−?) for any ?>0 unless NP=ZPP. From this result we will show that there exists no polynomial-time algorithm for approximating the boxicity and the cubicity of a graph on n vertices with factor O(n^0.5−?) for any ?>0 unless NP=ZPP. In fact all these hardness results hold even for a highly structured class of graphs, namely the split graphs. We will also show that it is NP-complete to determine whether a given split graph has boxicity at most 3.     

Graphic sequences with a realization containing a complete multipartite subgraph

A nonincreasing sequence of nonnegative integers π=(d₁,d₂,…,d_n) is graphic if there is a (simple) graph G of order n having degree sequence π. In this case, G is said to realizeπ. For a given graph H, a graphic sequence π is potentiallyH-graphic if there is some realization of π containing H as a (weak) subgraph. Let σ(π) denote the sum of the terms of π. For a graph H and n∈Z⁺, σ(H,n) is defined as the smallest even integer m so that every n-term graphic sequence π with σ(π)≥m is potentially H-graphic. Let denote the complete t partite graph such that each partite set has exactly s vertices. We show that and obtain the exact value of σ(K_j+K_s,s,n) for n sufficiently large. Consequently, we obtain the exact value of for n sufficiently large.     

More on “Connected (n, m)-graphs with minimum and maximum zeroth-order general Randi? index”

Let G be a graph and d(u) denote the degree of a vertex u in G. The zeroth-order general Randi? index ⁰R_α(G) of the graph G is defined as ∑_u∈V(G)d(u)^α, where the summation goes over all vertices of G and α is an arbitrary real number. In this paper we correct the proof of the main Theorem 3.5 of the paper by Hu et al. [Y. Hu, X. Li, Y. Shi, T. Xu, Connected (n,m)-graphs with minimum and maximum zeroth-order general Randi? index, Discrete Appl. Math. 155 (8) (2007) 1044-1054] and give a more general Theorem. We finally characterize ¹ for α<0 the connected G(n,m)-graphs with maximum value ⁰R_α(G(n,m)), where G(n,m) is a simple connected graph with n vertices and m edges.