Recurrence relations based on minimization and maximization

Explicit and asymptotic solutions are presented to the recurrence M(1) = g(1), M(n + 1) = g(n + 1) + min_{1 ? t ? n}(αM(t) + βM(n + 1 ? t)) for the cases (1) α + β < 1, $\text{log}{}_2\text{α}\text{log}{}_2\text{β}$ is rational, and g(n) = δ_nI. (2) α + β > 1, min(α, β) > 1, $\text{log}{}_2\text{α}\text{log}{}_2\text{β}$ is rational, and (a) g(n) = δ_n1, (b) g(n) = 1. The general form of this recurrence was studied extensively by Fredman and Knuth [J. Math. Anal. Appl.48 (1974), 534–559], who showed, without actually solving the recurrence, that in the above cases $\text{M(n) = Ω(n}{}^{\mathrm{<mtext>1\; +\; </mtext><mtext>1</mtext><mtext>\gamma </mtext>}}\text{)}$, where γ is defined by α^?γ + β^?γ = 1, and that $\text{lim}{}_{\mathrm{n\; \to \; \infty }}\text{M(n)}\text{n}{}^{\mathrm{1\; +\; \gamma }}$ does not exist. Using similar techniques, the recurrence M(1) = g(1), M(n + 1) = g(n + 1) + max_{1 ? t ? n}(αM(t) + βM(n + 1 ? t)) is also investigated for the special case α = β < 1 and g(n) = 1 if n is odd = 0 if n is even.     

On irregular binomial D-modules

We prove that a holonomic binomial D-module M _A (I, β) is regular if and only if certain associated primes of I determined by the parameter vector ${\beta\in \mathbb{C}^d}$ are homogeneous. We further describe the slopes of M _A (I, β) along a coordinate subspace in terms of the known slopes of some related hypergeometric D-modules that also depend on β. When the parameter β is generic, we also compute the dimension of the generic stalk of the irregularity of M _A (I, β) along a coordinate hyperplane and provide some remarks about the construction of its Gevrey solutions.     

Lower bounds on the minimum average distance of binary codes

Let β(n,M) denote the minimum average Hamming distance of a binary code of length n and cardinality M. In this paper we consider lower bounds on β(n,M). All the known lower bounds on β(n,M) are useful when M is at least of size about 2ⁿ⁻¹/n. We derive new lower bounds which give good estimations when size of M is about n. These bounds are obtained using a linear programming approach. In particular, it is proved that lim_n→∞β(n,2n)=5/2. We also give a new recursive inequality for β(n,M).     

LDU decomposition of an extension matrix of the Pascal matrix

Let Ω_m,n(α,β,γ) denote a set of all elements of weighted lattice paths with weight (α,β,γ) in the xy-plane from (0,0) to (m,n) such that a vertical step V=(0,1), a horizontal step H=(1,0), and a diagonal step D=(1,1) are endowed with weights α,β, and γ respectively and let ω(Ω_m,n(α,β,γ)) denote the weight of Ω_m,n(α,β,γ) defined by

     

Toroidal and Klein bottle boundary slopes

Let M be a compact, connected, orientable, irreducible 3-manifold and T₀ an incompressible torus boundary component of M such that the pair (M,T₀) is not cabled. By a result of C. Gordon, if (S,∂S),(T,∂T)⊂(M,T₀) are incompressible punctured tori with boundary slopes at distance Δ=Δ(∂S,∂T), then Δ?8, and the cases where Δ=6,7,8 are very few and classified. We give a simplified proof of this result (or rather, of its reduction process), using an improved estimate for the maximum possible number of mutually parallel negative edges in the graphs of intersection of S and T. We also extend Gordon's result by allowing either S or T to be an essential Klein bottle.     

Bifurcation from stability to instability for a free boundary problem modeling tumor growth by Stokes equation

We consider a free boundary problem modeling tumor growth in fluid-like tissue. The model equations include a diffusion equation for the nutrient concentration, and the Stokes equation with a source which represents the proliferation of tumor cells. The proliferation rate μ and the cell-to-cell adhesiveness γ which keeps the tumor intact are two parameters which characterize the “aggressiveness” of the tumor. For any positive radius R there exists a unique radially symmetric stationary solution with radius r=R. For a sequence μ/γ=Mn(R) there exist symmetry-breaking bifurcation branches of solutions with free boundary r=R+εYn,0(θ)+O(ε²) (n even ?2) for small |ε|, where Yn,0 is the spherical harmonic of mode (n,0). Furthermore, the smallest Mn(R), say Mn_∗(R), is such that n_∗=n_∗(R)→∞ as R→∞. In this paper we prove that the radially symmetric stationary solution with R=RS is linearly stable if μ/γ<N_∗(RS,γ) and linearly unstable if μ/γ>N_∗(RS,γ), where N_∗(RS,γ)?Mn_∗(RS), and we prove that strict inequality holds if γ is small or if γ is large. The biological implications of these results are discussed at the end of the paper.     

How to determine the maximum genus of a graph

The maximum genus, γ_M(G), of a connected graph G is the largest genus γ(S) for orientable surfaces S in which G has a 2-cell embedding. In this paper, we define a new combinatorial invariant ξ(G), the Betti deficiency of G, to be ξ(C) = min_C?G{ξ(C) 6 ξ(C) = number of odd components of a cotree C of G (by odd component we mean one with an odd number of edges). We formalize a new embedding technique to obtain the formula:

$\text{γ}{}_{\mathrm{M}}\text{(G)=}\text{1}\text{2}\text{(β(G)?ξ(G))}$

where β(G) denotes the Betti number of G.In a further paper, various consequences will be given.     

Eigenvectors and cyclic vectors of bilateral weighted shifts. II: Simply invariant subspaces

Let T be an injective bilateral weighted shift onl ² thought as "multiplication by λ" on a space of formal Laurent series L²(β). (a) If L²(β) is contained in a space of quasi-analytic class of functions, then the point spectrum σ_p(T^?) of T^? contains a circle and the cyclic invariant subspaceM _f of T generated by f is simply invariant (i.e., ∩{(T^k M _f)^?: k ≥ 0}= {0}) for each f in L²(β); (b) If L²(β) contains a non-quasi-analytic class of functions (defined on a circle г) of a certain type related with the weight sequence of T, then there exists f in L²(ß) such thatM _f is a non-trivial doubly invariant subspace (i.e., (TM _f)^? =M _f); furthermore, if г ? σ_p(T^*), then σ_p (T^*) = г and f can be chosen so that σ_p([T∣M _f]^*) = г?{α}, for some α ε г. Several examples show that the gap between operators satisfying (a) and operators satisfying (b) is rather small.     

Betti and Tachibana numbers

The Tachibana numbers t _r (M), the Killing numbers k _r (M), and the planarity numbers p _r (M) are considered as the dimensions of the vector spaces of, respectively, all, coclosed, and closed conformal Killing r-forms with 1 ≤ r ≤ n ? 1 “globally” defined on a compact Riemannian n-manifold (M,g), n >- 2. Their relationship with the Betti numbers b _r (M) is investigated. In particular, it is proved that if b _r (M) = 0, then the corresponding Tachibana number has the form t _r (M) = k _r (M) + p _r (M) for t _r (M) > k _r (M) > 0. In the special case where b ₁(M) = 0 and t ₁(M) > k ₁(M) > 0, the manifold (M,g) is conformally diffeomorphic to the Euclidean sphere.     

Extremal perfect graphs for a bound on the domination number

We examine classes of extremal graphs for the inequality γ(G)?|V|-max{d(v)+β_v(G)}, where γ(G) is the domination number of graph G, d(v) is the degree of vertex v, and β_v(G) is the size of a largest matching in the subgraph of G induced by the non-neighbours of v. This inequality improves on the classical upper bound |V|-maxd(v) due to Claude Berge. We give a characterization of the bipartite graphs and of the chordal graphs that achieve equality in the inequality. The characterization implies that the extremal bipartite graphs can be recognized in polynomial time, while the corresponding problem remains NP-complete for the extremal chordal graphs.     

Dominating direct products of graphs

An upper bound for the domination number of the direct product of graphs is proved. It in particular implies that for any graphs G and H, γ(G×H)?3γ(G)γ(H). Graphs with arbitrarily large domination numbers are constructed for which this bound is attained. Concerning the upper domination number we prove that Γ(G×H)?Γ(G)Γ(H), thus confirming a conjecture from [R. Nowakowski, D.F. Rall, Associative graph products and their independence, domination and coloring numbers, Discuss. Math. Graph Theory 16 (1996) 53-79]. Finally, for paired-domination of direct products we prove that γ_pr(G×H)?γ_pr(G)γ_pr(H) for arbitrary graphs G and H, and also present some infinite families of graphs that attain this bound.     

Mrówka maximal almost disjoint families for uncountable cardinals

We consider generalizations of a well-known class of spaces, called by S. Mrówka, N∪R, where R is an infinite maximal almost disjoint family (MADF) of countable subsets of the natural numbers N. We denote these generalizations by ψ=ψ(κ,R) for κ?ω. Mrówka proved the interesting theorem that there exists an R such that |βψ(ω,R)?ψ(ω,R)|=1. In other words there is a unique free z-ultrafilter p₀ on the space ψ. We extend this result of Mrówka to uncountable cardinals. We show that for κ?c, Mrówka's MADF R can be used to produce a MADF M⊂ω[κ] such that |βψ(κ,M)?ψ(κ,M)|=1. For κ>c, and every M⊂ω[κ], it is always the case that |βψ(κ,M)?ψ(κ,M)|≠1, yet there exists a special free z-ultrafilter p on ψ(κ,M) retaining some of the properties of p₀. In particular both p and p₀ have a clopen local base in βψ (although βψ(κ,M) need not be zero-dimensional). A result for κ>c, that does not apply to p₀, is that for certain κ>c, p is a P-point in βψ.     

On openness and surjectivity of lifted frame homomorphisms

Given a completely regular frame L, let, as usual, βL, λL and υL denote, respectively, the Stone-?ech compactification, the universal Lindelöfication and the Hewitt realcompactification of L. Let γ denote any of the functors β, λ or υ. It is well known that any frame homomorphism h:L→M has a unique “lift” to a frame homomorphism hγ:γL→γM such that σM⋅hγ=h⋅σL, where the σ-maps are effected by join. We find a condition on h such that if h satisfies it, then h is open iff its lift hγ is open. Furthermore, the same condition ensures that hγ is nearly open iff h is nearly open. This latter result is, in fact, a special case of a more general phenomenon. In the last part of the paper we investigate when hυ is surjective. The instances when hβ or hλ is surjective are known. It turns out that the surjectivity of the lifted map hυ:υL→υM captures Blair's notion of υ-embedding in the sense that a subspace S of a Tychonoff space X is υ-embedded iff the lifted map υ(Oi):υ(OX)→υ(OS) is surjective, where i:S→X is the subspace embedding.     

On domination and independent domination numbers of a graph

For a graph G, the definitions of domination number, denoted γ(G), and independent domination number, denoted i(G), are given, and the following results are obtained:Theorem.If G does not have an induced subgraph isomorphic to K_1,3, thenγ(G) = i(G).Corollary 1.For any graph G, γ(L(G))=i(L(G)), where L(G) is the line graph of G. (This extends the result γ(L(T))=i(L(T)), where T is a tree. Hedetniemi and Mitchell, S. E. Conf. Baton Rouge, 1977.)Corollary 2.For any Graph G, γ(M(G))=i(M(G)), where M is the middle graph of G.     

When is the radical associated with a module a torsion?

For an arbitrary R-module M we consider the radical (in the sense of Maranda)G _M, namely, the largest radical among all radicalsG, such thatG(M). We determine necessary and sufficient on M in order for the radicalG(M) to be a torsion. In particular,G(M) is a torsion if and only if M is a pseudo-injective module.     

Oscillatory hyper Hilbert transforms along general curves

We consider the oscillatory hyper Hilbert transform H _γ,α,β f(x) = ∫ ₀ ^∞ f(x - Γ(t))e^it-β t^-(1+α)dt; where Γ(t) = (t, γ(t)) in ?² is a general curve. When γ is convex, we give a simple condition on γ such that H _γ,α,β is bounded on L ² when β > 3α, β > 0: As a corollary, under this condition, we obtain the L ^p -boundedness of H _γ,α,β when 2β/(2β - 3α) < p < 2β/(3α). When Γ is a general nonconvex curve, we give some more complicated conditions on γ such that H _γ,α,β is bounded on L ²: As an application, we construct a class of strictly convex curves along which H _γ,α,β is bounded on L ² only if β > 2α > 0.     

Characterization and representation problems for intersection betweennesses

For a set system M=(M_v)_v∈V indexed by the elements of a finite set V, the intersection betweenness B(M) induced by M consists of all triples (u,v,w)∈V³ with M_u∩M_w⊆M_v. Similarly, the strict intersection betweenness B_s(M) induced by M consists of all triples (u,v,w)∈B(M) such that u, v, and w are pairwise distinct. The notion of a strict intersection betweenness was introduced by Burigana [L. Burigana, Tree representations of betweenness relations defined by intersection and inclusion, Math. Soc. Sci. 185 (2009) 5-36]. We provide axiomatic characterizations of intersection betweennesses and strict intersection betweennesses. Our results yield a simple and efficient algorithm that constructs a representing set system for a given (strict) intersection betweenness. We study graphs whose strict shortest path betweenness is a strict intersection betweenness. Finally, we explain how the algorithmic problem related to Burigana’s notion of a partial tree representation can be solved efficiently using well-known algorithms.