On partitioning two matroids into common independent subsets

Let M₁ and M₂ be two matroids on the same ground set S. We conjecture that if there do not exist disjoint subsets A₁,A₂,…,A_k+1 of S, such that _isp_M1(A_i)≠Ø, and similarly for M₂, then S is partitioned into k sets, each independent in both M₁ and M₂. This is a possible generalization of König's edge-coloring theorem. We prove the conjecture for the case k=2 and for a regular case, in which both matroids have the same rank d, and S consists of k·d elements. Finally, we prove another special case related to a conjecture of Rota.     

The bandwidth sum of join and composition of graphs

Given a graph G, a proper labeling f of G is a one-to-one function . The bandwidth sum of a graph G, denoted by B_s(G), is defined by B_s(G)=min∑_uvE(G)|f(u)-f(v)|, where the minimum is taken for all proper labelings f of G. In this paper, we give some results for the bandwidth sum problem for the join of k graphs G₁,G₂,…,G_k, where each G_i is a path, cycle, complete graph, or union of isolated vertices. We also discuss the bandwidth sum for the composition of two graphs G and H, where G and H are path, cycle, or union of isolated vertices.     

On four color monochromatic sets with nondecreasing diameter

Let m and r be positive integers. Define f(m,r) to be the least positive integer N such that for every coloring of the integers 1,…,N with r colors there exist monochromatic subsets B₁ and B₂ (not necessarily of the same color), each having m elements, such that (a) max(B₁)-min(B₁)max(B₂)-min(B₂), and (b) max(B₁)B₂). We improve previous upper bounds to determine that f(m,4)=12m-9.     

Simple 3-designs of with block size 6

In this paper, we give necessary and sufficient conditions for the existence of a simple 3-(2ⁿ+1,6,λ) design with PSL(2,2ⁿ) as an automorphism group.     

A combinatorial approach to doubly transitive permutation groups

Let G be a doubly but not triply transitive group on a set X. We give an algorithm to construct the orbits of G acting on X×X×X by combining those of its stabilizer H of a point of X If the group H is given first, we compute the orbits of its transitive extension G, if it exists. We apply our algorithm to G=PSL(m,q) and Sp(2m,2), m3, successfully. We go forward to compute the transitive extension of G itself. In our construction we use a superscheme defined by the orbits of H on X×X×X and do not use group elements.     

3-Homogeneous latin trades

Let T be a partial latin square and L be a latin square with TL. We say that T is a latin trade if there exists a partial latin square T^′ with T^′∩T= such that (LT)T^′ is a latin square. A k-homogeneous latin trade is one which intersects each row, each column and each entry either 0 or k times. In this paper, we construct 3-homogeneous latin trades from hexagonal packings of the plane with circles. We show that 3-homogeneous latin trades of size 3 m exist for each m3. This paper discusses existence results for latin trades and provides a glueing construction which is subsequently used to construct all latin trades of finite order greater than three.     

Asymptotic analysis of a perturbation problem

An asymptotic expansion is constructed for the solution of the initial-value problem

when t is restricted to the interval [0,T/ε], where T is any given number. Our analysis is mathematically rigorous; that is, we show that the difference between the true solution u(t,x;ε) and the Nth partial sum of the asymptotic series is bounded by ε^N+1 multiplied by a constant depending on T but not on x and t.     

Ore-type degree condition for heavy paths in weighted graphs

A weighted graph is one in which every edge e is assigned a nonnegative number w(e), called the weight of e. For a vertex v of a weighted graph, d^w(v) is the sum of the weights of the edges incident to v. And the weight of a path is the sum of the weights of the edges belonging to it. In this paper, we give a sufficient condition for a weighted graph to have a heavy path which joins two specified vertices. Let G be a 2-connected weighted graph and let x and y be distinct vertices of G. Suppose that d^w(u)+d^w(v)2d for every pair of non-adjacent vertices u and vV(G) x,y . Then x and y are joined by a path of weight at least d, or they are joined by a Hamilton path. Also, we consider the case when G has some vertices whose weighted degree are not assumed.     

Stability properties of non-negative solutions to a non-autonomous p-Laplacian equation

We study the stability of non-negative stationary solutions of

where Δ_p denotes the p-Laplacian operator defined by Δ_pz = div(z^p−2z); p > 2, Ω is a bounded domain in R^N(N  1) with smooth boundary where [0,1],h:∂Ω→R⁺ with h = 1 when  = 1, λ > 0, and g:Ω×[0,∞)→R is a continuous function. If g(x, u)/u^p−1 be strictly increasing (decreasing), we provide a simple proof to establish that every non-trivial non-negative solution is unstable (stable).     

The total chromatic number of regular graphs of even order and high degree

The total chromatic number χ_T(G) of a graph G is the minimum number of colours needed to colour the edges and the vertices of G so that incident or adjacent elements have distinct colours. We show that if G is a regular graph of even order and , thenχ_T(G)Δ(G)+2.     

Computing homotopic shortest paths efficiently

We give deterministic and randomized algorithms to find shortest paths homotopic to a given collection Π of disjoint paths that wind amongst n point obstacles in the plane. Our deterministic algorithm runs in time , and the randomized algorithm runs in expected time O(k_out+k_inlogn+n(logn)^1+ε). Here k_in is the number of edges in all the paths of Π, and k_out is the number of edges in the output paths.     

Maximum genus, connectivity and minimal degree of graphs

This paper is devoted to the lower bounds on the maximum genus of graphs. A simple statement of our results in this paper can be expressed in the following form:

Let G be a k-edge-connected graph with minimum degree δ, for each positive integer k(3), there exists a non-decreasing function f(δ) such that the maximum genus γ_M(G) of G satisfies the relation γ_M(G)f(δ)β(G), and furthermore that lim_δ→∞f(δ)=1/2, where β(G)=|E(G)|-|V(G)|+1 is the cycle rank of G.

The result shows that lower bounds of the maximum genus of graphs with any given connectivity become larger and larger as their minimum degree increases, and complements recent results of several authors.     

A new formula for an evaluation of the Tutte polynomial of a matroid

Given a matroid M and its Tutte polynomial T_M(x,y), T_M(0,1) is an invariant of M with various interesting combinatorial and topological interpretations. Being a Tutte–Grothendieck invariant, T_M(0,1) may be computed via deletion–contraction recursions. In this note we derive a new recursion formula for this invariant that involves contractions of M through the circuits containing a fixed element of M.     

Global stability of a rational difference equation

In this paper, we study the global stability of the difference equation , where the parameters a,a_i(0,∞) for i=0,…,k, x_-k,…, x_-1[0,∞) and x₀(0,∞). We prove that the unique positive equilibrium is globally asymptotically stable if and only if it is locally asymptotically. Also we provide sufficient condition for it to be globally asymptotically stable and our results solve the open problem proposed by Kulenović and Ladas (Dynamics of Second Order Rational Difference Equations with Open Problems and Conjectures, Chapman & Hall/CRC, Boca Raton, 2002).     

General preservers of invariant subspace lattices

Let be the space of all bounded linear operators on a Banach space X and let LatA be the lattice of invariant subspaces of the operator . We characterize some maps with one of the following preserving properties: Lat(Φ(A)+Φ(B))=Lat(A+B), or Lat(Φ(A)Φ(B))=Lat(AB), or Lat(Φ(A)Φ(B)+Φ(B)Φ(A))=Lat(AB+BA), or Lat(Φ(A)Φ(B)Φ(A))=Lat(ABA), or Lat([Φ(A),Φ(B)])=Lat([A,B]).     

Chromatic numbers and products

Let f(n) be the smallest number so that there are two n chromatic graphs whose product has chromatic number f(n). Under the assumption that a certain sharper result than one obtained by Duffus et al. [On the chromatic number of the product of graphs, J. Graph Theory 9 (1985) 487–495], and Welzl [Symmetric graphs and interpretations, J. Combin. Theory, Sci. B 37 (1984) 235–244], holds we will prove that f(n)n/2.     

Global existence and blow-up solutions and blow-up estimates for a non-local quasilinear degenerate parabolic system

This paper deals with p-Laplacian systems

with null Dirichlet boundary conditions in a smooth bounded domain ΩR^N, where p,q>1, , and a,b>0 are positive constants. We first get the non-existence result for a related elliptic systems of non-increasing positive solutions. Secondly by using this non-existence result, blow-up estimates for above p-Laplacian systems with the homogeneous Dirichlet boundary value conditions are obtained under Ω=B_R={xR^N:|x|<R}(R>0). Then under appropriate hypotheses, we establish local theory of the solutions and obtain that the solutions either exists globally or blow-up in finite time.     

Uniform asymptotic expansions of the Pollaczek polynomials

Two uniform asymptotic expansions are obtained for the Pollaczek polynomials P_n(cosθ;a,b). One is for , , in terms of elementary functions and in descending powers of . The other is for , in terms of a special function closely related to the modified parabolic cylinder functions, in descending powers of n. This interval contains a turning point and all possible zeros of P_n(cosθ) in θ(0,π/2].     

Mass formula for self-dual codes over Z

We give a mass formula for self-dual codes over Z_p², where p is an odd prime. Using the mass formula, we classify such codes of lengths up to n=8 over the ring Z₉, n=7 over Z₂₅ and n=6 over Z₄₉.     

On oscillatory solutions of certain first order ordinary differential equations

By constructing a class of solutions to the integral inequality for t  t₀ large enough, where 0<A₁a(τ)A₂<+∞ and λ>1, that tend to zero as t→+∞ we address an open problem in the theory of nonlinear oscillations.