Cycles of given color patterns

In 2-edge-colored graphs, we define an (s, t)-cycle to be a cyle of length s + t, in which s consecutive edges are in one color and the remaining t edges are in the other color. Here we investigate the existence of (s, t)-cycles, in a 2-edge-colored complete graph K^c_n on n vertices. In particular, in the first result we give a complete characterization for the existence of (s, t)-cycles in K^c_n with n relatively large with respect to max({s, t}). We also study cycles of length 4 for all possible values of s and t. Then, we show that K^c_n contains an (s, t)-hamiltonian cycle unless it is isomorphic to a specified graph. This extends a result of A. Gyárfás [Journal of Graph Theory, 7 (1983), 131–135]. Finally, we give some sufficient conditions for the existence of (s, 1)-cycles, (inverted sans serif aye) s ϵ {2, 3,…, n − 2}. © 1996 John Wiley & Sons, Inc.     

On the chromaticity of complete multipartite graphs with certain edges added

Let P(G,λ) be the chromatic polynomial of a graph G. A graph G is chromatically unique if for any graph H, P(H,λ)=P(G,λ) implies H is isomorphic to G. For integers k≥0, t≥2, denote by K((t−1)×p,p+k) the complete t-partite graph that has t−1 partite sets of size p and one partite set of size p+k. Let K(s,t,p,k) be the set of graphs obtained from K((t−1)×p,p+k) by adding a set S of s edges to the partite set of size p+k such that 〈S〉 is bipartite. If s=1, denote the only graph in K(s,t,p,k) by K⁺((t−1)×p,p+k). In this paper, we shall prove that for k=0,1 and p+k≥s+2, each graph G∈K(s,t,p,k) is chromatically unique if and only if 〈S〉 is a chromatically unique graph that has no cut-vertex. As a direct consequence, the graph K⁺((t−1)×p,p+k) is chromatically unique for k=0,1 and p+k≥3.     

Identity orientation of complete bipartite graphs

An identity orientation of a graph G=(V,E) is an orientation of some of the edges of E such that the resulting partially oriented graph has no automorphism other than the identity. We show that the complete bipartite graph K_s,t, with st, does not have an identity orientation if t3^s-log₃(s-1). We also show that if (r+1)(r+2)2s then K_s,3^s-r does have an identity orientation. These results improve the previous bounds obtained by Harary and Jacobson (Discuss. Math. - Graph Theory 21 (2001) 158). We use these results to determine exactly the values of t for which an identity orientation of K_s,t exists for 2s17.     

Kolmogorov and linear widths of classes of <Emphasis Type="Italic">s</Emphasis>-monotone integrable functions

Let s ∈ ℕ and let Δ ₊ ^s be the set of functions x: I ↦ ℝ on a finite interval I such that the divided differences [x; t ₀, ..., t _s ] of order s of these functions are nonnegative for all collections of s + 1 different points t ₀, ..., t _s ∈ I. For the classes Δ ₊ ^s B _p : = Δ ₊ ^s ∩ B _p , where B _p is the unit ball in L _p , we determine the orders of Kolmogorov and linear widths in the spaces _Lq for 1 ≤ q > p ≤ ∞. __________ Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 57, No. 12, pp. 1633–1652, December, 2005.     

Monochromatic Hamiltonian t‐tight Berge‐cycles in hypergraphs

In any r‐uniform hypergraph for 2 ≤ t ≤ r we define an r‐uniform t‐tight Berge‐cycle of length ?, denoted by C_?^{(r, t)}, as a sequence of distinct vertices v₁, v₂, … , v_?, such that for each set (v_i, v_{i + 1}, … , v_{i + t ? 1}) of t consecutive vertices on the cycle, there is an edge E_i of that contains these t vertices and the edges E_i are all distinct for i, 1 ≤ i ≤ ?, where ? + j ≡ j. For t = 2 we get the classical Berge‐cycle and for t = r we get the so‐called tight cycle. In this note we formulate the following conjecture. For any fixed 2 ≤ c, t ≤ r satisfying c + t ≤ r + 1 and sufficiently large n, if we color the edges of K_n^(r), the complete r‐uniform hypergraph on n vertices, with c colors, then there is a monochromatic Hamiltonian t‐tight Berge‐cycle. We prove some partial results about this conjecture and we show that if true the conjecture is best possible. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 34–44, 2008     

On a nonconvolution Volterra resolvent

Under fairly weak assumptions, the solutions of the system of Volterra equations x(t) = ∝₀^ta(t, s) x(s) ds + f(t), t > 0, can be written in the form x(t) = f(t) + ∝₀^tr(t, s) f(s) ds, t > 0, where r is the resolvent of a, i.e., the solution of the equation r(t, s) = a(t, s) + ∝₀^ta(t, v) r(v, s)dv, 0 < s < t. Conditions on a are given which imply that the resolvent operator f ∝₀^tr(t, s) f(s) ds maps a weighted L¹ space continuously into another weighted L¹ space, and a weighted L^∞ space into another weighted L^∞ space. Our main theorem is used to study the asymptotic behavior of two differential delay equations.     

On Ramsey‐type positional games

Let K denote the graph obtained from the complete graph K_s+t by deleting the edges of some K_t‐subgraph. We prove that for each fixed s and sufficiently large t, every graph with chromatic number s+t has a K minor. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 343–350, 2010     

Defective choosability of graphs with no edge‐plus‐independent‐set minor

It is proved that, if s ≥ 2, a graph that does not have K₂ + K _s = K₁ + K_{1, s} as a minor is (s, 1)*‐choosable. This completes the proof that such a graph is (s + 1 ? d,d)*‐choosable whenever 0 ≤ d ≤ s ?1 © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 51–56, 2004     

Asymptotic Behavior of Poisson Kernels on NA Groups

On a Lie group S = NA, that is a split extension of a nilpotent Lie group N by a one-parameter group of automorphisms A, a probability measure μ is considered and treated as a distribution according to which transformations s ∈ S acting on N = S/A are sampled. Under natural conditions, formulated some over thirty years ago, there is a μ-invariant measure m on N. Properties of m have been intensively studied by a number of authors. The present article deals with the situation when μ(A) = ?(s _t  ∈ A), where ?⁺ ? t → s _t  ∈ S is the diffusion on S generated by a second order subelliptic, hypoelliptic, left-invariant operator on S. In this article the most general operators of this kind are considered. Precise asymptotic for m at infinity and for the Green function of the operator are given. To achieve this goal a pseudodifferential calculus for operators with coefficients of finite smoothness is formulated and applied.     

Ruled surfaces of Weingarten type in Minkowski 3-space

In this paper, we study ruled Weingarten surfaces M : x (s, t) = α(s) + tβ (s) in Minkowski 3-space on which there is a nontrivial functional relation between a pair of elements of the set {K, K_II, H, H_II}, where K is the Gaussian curvature, K_II is the second Gaussian curvature, H is the mean curvature, and H_II is the second mean curvature. We also study ruled linear Weingarten surfaces in Minkowski 3-space such that the linear combination aK_II + bH + cH_II + dK is constant along each ruling for some constants a, b, c, d with a² + b² + c² ≠ 0.     

Continuous k‐to‐1 functions between complete graphs whose orders are of a different parity

A function between graphs is k‐to‐1 if each point in the codomain has precisely k pre‐images in the domain. Given two graphs, G and H, and an integer k≥1, and considering G and H as subsets of ?³, there may or may not be a k‐to‐1 continuous function (i.e. a k‐to‐1 map in the usual topological sense) from G onto H. In this paper we consider graphs G and H whose order is of a different parity and determine the even and odd values of k for which there exists a k‐to‐1 map from G onto H. We first consider k‐to‐1 maps from K_2r onto K_2s+1 and prove that for 1≤r≤s, (r, s)≠(1, 1), there is a continuous k‐to‐1 map for k even if and only if k≥2s and for k odd if and only if k≥?s?_o (where ?s?_o indicates the next odd integer greater than or equal to s). We then consider k‐to‐1 maps from K_2s+1 onto K_2s. We show that for 1≤r<s, such a map exists for even values of k if and only if k≥2s. We also prove that whatever the values of r and s are, no such k‐to‐1 map exists for odd values of k. To conclude, we give all triples (n, k, m) for which there is a k‐to‐1 map from K_n onto K_m in the case when n≤m. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 35–60, 2010.     

Properly colored subgraphs and rainbow subgraphs in edge‐colorings with local constraints

We consider a canonical Ramsey type problem. An edge‐coloring of a graph is called m‐good if each color appears at most m times at each vertex. Fixing a graph G and a positive integer m, let f(m, G) denote the smallest n such that every m‐good edge‐coloring of K_n yields a properly edge‐colored copy of G, and let g(m, G) denote the smallest n such that every m‐good edge‐coloring of K_n yields a rainbow copy of G. We give bounds on f(m, G) and g(m, G). For complete graphs G = K_t, we have c₁mt²/ln t ≤ f(m, K_t) ≤ c₂mt², and cmt³/ln t ≤ g(m, K_t) ≤ cmt³/ln t, where c₁, c₂, c, c are absolute constants. We also give bounds on f(m, G) and g(m, G) for general graphs G in terms of degrees in G. In particular, we show that for fixed m and d, and all sufficiently large n compared to m and d, f(m, G) = n for all graphs G with n vertices and maximum degree at most d. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2003     

Packing dimension and Ahlfors regularity of porous sets in metric spaces

Let X be a metric measure space with an s-regular measure μ. We prove that if A ì X{A\subset X} is r{\varrho} -porous, then dim_p(A) ￡ s-cr^s{{\rm {dim}_p}(A)\le s-c\varrho^s} where dim_p is the packing dimension and c is a positive constant which depends on s and the structure constants of μ. This is an analogue of a well known asymptotically sharp result in Euclidean spaces. We illustrate by an example that the corresponding result is not valid if μ is a doubling measure. However, in the doubling case we find a fixed N ì X{N\subset X} with μ(N) = 0 such that dim_p(A) ￡ dim_p(X)-c(log\tfrac1r)^-1r^t{{\rm {dim}_p}(A)\le{\rm {dim}_p}(X)-c(\log \tfrac1\varrho)^{-1}\varrho^t} for all r{\varrho} -porous sets A ì X\ N{A \subset X{\setminus} N} . Here c and t are constants which depend on the structure constant of μ. Finally, we characterize uniformly porous sets in complete s-regular metric spaces in terms of regular sets by verifying that A is uniformly porous if and only if there is t < s and a t-regular set F such that A ì F{A\subset F} .     

A Fujita-type global existence—global non-existence theorem for a system of reaction diffusion equations with differing diffusivities

In this paper we condiser non-negative solutions of the initial value problem in ?^N for the system where 0 ? δ ? 1 and pq > 0. We prove the following conditions. Suppose min(p,q)≥1 but pq1.

• (a) If δ = 0 then u=v=0 is the only non-negative global solution of the system.
• (b) If δ>0, non-negative non-globle solutions always exist for suitable initial values.
• (c) If 0<?1 and max(α, β) ≥ N/2, where qα = β + 1, pβ = α + 1, then the conclusion of (a) holds.
• (d) If N > 2, 0 < δ ? 1 and max (α β) < (N - 2)/2, then global, non-trivial non-negative solutions exist which belong to L^∞(?^N×[0, ∞]) and satisfy 0 < u(X, t) ? c∣x∣^?2α and 0 < v(X, t) ? c ∣x∣^?2bT for large ∣x∣ for all t > 0, where c depends only upon the initial data.
• (e) Suppose 0 > δ 1 and max (α, β) < N/2. If N> = 1,2 or N > 2 and max (p, q)? N/(N-2), then global, non-trivial solutions exist which, after makinng the standard ‘hot spot’ change of variables, belong to the weighted Hilbert space H¹ (K) where K(x) ? exp(¼∣x∣²). They decay like e^{[max(α,β)-(N/2)+ε]t} for every ε > 0. These solutions are classical solutions for t > 0.
• (f) If max (α, β) < N/2, then threre are global non-tivial solutions which satisfy, in the hot spot variables where where 0 < ε = ε(u₀, v₀) < (N/2)?;max(α, β). Suppose min(p, q) ? 1.
• (g) If pq ≥ 1, all non-negative solutions are global. Suppose min(p, q) < 1.
• (h) If pg > 1 and δ = 0, than all non-trivial non-negative maximal solutions are non-global.
• (i) If 0 < δ ? 1, pq > 1 and max(α,β)≥ N/2 all non-trivial non-negative maximal solutions are non-global.
• (j) If 0 < δ ≥ 1, pq > 1 and max(α,β) < N/2, there are both global and non-negative solutions.

We also indicate some extensions of these results to moe general systems and to othere geometries.     

Construction of Williamson type matrices

Recent advances in the construction of Hadamard matrices have depeaded on the existence of Baumert-Hall arrays and four (1, ?1) matrices A B C Dof order m which are of Williamson type, that is they pair-wise satisfy

i) MN^T = NM^T , ∈ {A B C D} and

ii) AA^T + BB^T + CC^T + DD^T = 4mI_m .

It is shown that Williamson type matrices exist for the orders m = s(4 ? 1)m = s(4s + 3) for s∈ {1, 3, 5, …, 25} and also for m = 93. This gives Williamson matrices for several new orders including 33, 95,189.

These results mean there are Hadamard matrices of order

i) 4s(4s ?1)t, 20s(4s ? 1)t,s ∈ {1, 3, 5, …, 25};

ii) 4s(4:s + 3)t, 20s(4s + 3)t s ∈ {1, 3, 5, …, 25};

iii) 4.93t, 20.93t

for

t ∈ {1, 3, 5, … , 61} ∪ {1 + 2 ^a 10 ^b 26 ^c a b c nonnegative integers}, which are new infinite families.

Also, it is shown by considering eight-Williamson-type matrices, that there exist Hadamard matrices of order 4(p + 1)(2p + l)r and 4(p + l)(2p + 5)r when p ≡ 1 (mod 4) is a prime power, 8ris the order of a Plotkin array, and, in the second case 2p + 6 is the order of a symmetric Hadamard matrix. These classes are new.     

On oscillation of a Volterra integral equation with delay

The purpose of this paper is to obtain sufficient conditions for oscillation of all solutions of the equation x(t) = f(t) + ∝_a^t K(t, s, x(s), x(g(s))) ds to study the behaviour of its oscillatory solutions in a dependence on the distance between their consecutive zeros and to establish a theorem for localization of the zeros of its solutions.     

The Vlasov‐Poisson‐Boltzmann system near Maxwellians

The dynamics of dilute electrons can be modeled by the Vlasov‐Poisson‐Boltz‐mann system, where electrons interact with themselves through collisions and with their self‐consistent electric field. It is shown that any smooth, periodic initial perturbation of a given global Maxwellian that preserves the same mass, momentum, and total energy (including both kinetic and electric energy), leads to a unique global‐in‐time classical solution. The construction of global solutions is based on an energy method with a new estimate of dissipation from the collision: ∫₀^t〈Lf(s), f(s)〉ds is positive definite for solution f(t,x,v) with small amplitude to the Vlasov‐Poisson‐Boltzmann system (1.4). © 2002 Wiley Periodicals, Inc.     

Large Kr‐free subgraphs in Ks‐free graphs and some other Ramsey‐type problems

In this paper we present three Ramsey‐type results, which we derive from a simple and yet powerful lemma, proved using probabilistic arguments. Let 3 ≤ r < s be fixed integers and let G be a graph on n vertices not containing a complete graph K_s on s vertices. More than 40 years ago Erd?s and Rogers posed the problem of estimating the maximum size of a subset of G without a copy of the complete graph K_r. Our first result provides a new lower bound for this problem, which improves previous results of various researchers. It also allows us to solve some special cases of a closely related question posed by Erd?s. For two graphs G and H, the Ramsey number R(G, H) is the minimum integer N such that any red‐blue coloring of the edges of the complete graph K_N, contains either a red copy of G or a blue copy of H. The book with n pages is the graph B_n consisting of n triangles sharing one edge. Here we study the book‐complete graph Ramsey numbers and show that R(B_n, K_n) ≤ O(n³/log^3/2n), improving the bound of Li and Rousseau. Finally, motivated by a question of Erd?s, Hajnal, Simonovits, Sós, and Szemerédi, we obtain for all 0 < δ < 2/3 an estimate on the number of edges in a K₄‐free graph of order n which has no independent set of size n^1‐δ. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

Properly Edge-Coloured Subgraphs in Colourings of Bounded Degree

The smallest n such that every colouring of the edges of K _n must contain a monochromatic star K _1,s+1 or a properly edge-coloured K _t is denoted by f (s, t). Its existence is guaranteed by the Erdős–Rado Canonical Ramsey theorem and its value for large t was discussed by Alon, Jiang, Miller and Pritikin (Random Struct. Algorithms 23:409–433, 2003). In this note we primarily consider small values of t. We give the exact value of f (s, 3) for all s ≥ 1 and the exact value of f (2, 4), as well as reducing the known upper bounds for f (s, 4) and f (s, t) in general.     

Subvarieties of the matrix variety of second order

LetR _s be the subalgebra ofM ₂(K[t]/(t ^s )) generated bye ₁₁,e ₂₂,te ₁₂ andte ₂₁, whereK is a field of characteristic 0,K[t] is the polynomial algebra in one variablet and (t ^s ) is the principal ideal inK[t], generated byt ^s . The main result of this paper is that we have described theT-idealT(R _s ). Besides the two matrix polynomial identities — the standart identityS ₄ and the identity of Hall, thisT-ideal is generated by one more explicitly given identity. The algebrasR _s are interesting due to the fact that the proper identities of any subvarietyu of the variety ℳ=varM ₂(K), generated by the matrix algebraM ₂(K) of second order overK, asymptoticaly coincide with the proper identities of someR _s . Partially supported by Grant MM605/96 of the Bulgarian Foundation for Scientific Research.