Anti‐periodic solutions for evolution equations with mappings in the class (S+)

In this paper, we study the existence of anti‐periodic solutions for the first order evolution equation in a Hilbert space H, where G : H → ? is an even function such that ?G is a mapping of class (S₊) and f : ? → ? satisfies f(t + T) = –f(t) for any t ∈ ? with f(·) ∈ L²(0, T; H). (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Alternating and Sporadic Simple Groups are Determined by Their Character Degrees

Let G be a finite group. Denote by Irr(G) the set of all irreducible complex characters of G. Let cd(G) be the set of all irreducible complex character degrees of G forgetting multiplicities, that is, cd(G) = {χ(1) : χ ∈ Irr(G)} and let cd ^*(G) be the set of all irreducible complex character degrees of G counting multiplicities. Let H be an alternating group of degree at least 5, a sporadic simple group or the Tits group. In this paper, we will show that if G is a non-abelian simple group and cd(G) í cd(H)cd(G)\subseteq cd(H) then G must be isomorphic to H. As a consequence, we show that if G is a finite group with cd^*(G) í cd^*(H)cd^*(G)\subseteq cd^*(H) then G is isomorphic to H. This gives a positive answer to Question 11.8 (a) in (Unsolved problems in group theory: the Kourovka notebook, 16th edn) for alternating groups, sporadic simple groups or the Tits group.     

Weak Cayley Table Groups II: Alternating Groups and Finite Coxeter Groups

A weak Cayley table isomorphism is a bijection φ: G → H of groups such that φ(xy) ～ φ(x)φ(y) for all x, y ∈ G. Here ～denotes conjugacy. When G = H the set of all weak Cayley table isomorphisms φ: G → G forms a group 𝒲(G) that contains the automorphism group Aut(G) and the inverse map I: G → G, x → x ^?1. Let 𝒲₀(G) = ?Aut(G), I? ≤ 𝒲(G) and say that G has trivial weak Cayley table group if 𝒲(G) = 𝒲₀(G). We show that all finite irreducible Coxeter groups (except possibly E ₈) have trivial weak Cayley table group, as well as most alternating groups. We also consider some sporadic simple groups.     

Orthogonal factorizations of digraphs

Let G be a digraph with vertex set V(G) and arc set E(G) and let g = (g ⁻, g ⁺) and ƒ = (ƒ ⁻, ƒ ⁺) be pairs of positive integer-valued functions defined on V(G) such that g ⁻(x) ⩽ ƒ ⁻(x) and g ⁺(x) ⩽ ƒ ⁺(x) for each x ∈ V(G). A (g, ƒ)-factor of G is a spanning subdigraph H of G such that g ⁻(x) ⩽ id _H (x) ⩽ ƒ ⁻(x) and g ⁺(x) ⩽ od _H (x) ⩽ ƒ ⁺(x) for each x ∈ V(H); a (g, ƒ)-factorization of G is a partition of E(G) into arc-disjoint (g, ƒ)-factors. Let = {F ₁, F ₂,…, F _m} and H be a factorization and a subdigraph of G, respectively. is called k-orthogonal to H if each F _i , 1 ⩽ i ⩽ m, has exactly k arcs in common with H. In this paper it is proved that every (mg+m−1,mƒ−m+1)-digraph has a (g, f)-factorization k-orthogonal to any given subdigraph with km arcs if k ⩽ min{g ⁻(x), g ⁺(x)} for any x ∈ V(G) and that every (mg, mf)-digraph has a (g, f)-factorization orthogonal to any given directed m-star if 0 ⩽ g(x) ⩽ f(x) for any x ∈ V(G). The results in this paper are in some sense best possible.      

A note on the bichromatic numbers of graphs

For a pair of integers k, l≥0, a graph G is (k, l)‐colorable if its vertices can be partitioned into at most k independent sets and at most l cliques. The bichromatic number χ^b(G) of G is the least integer r such that for all k, l with k+l=r, G is (k, l)‐colorable. The concept of bichromatic numbers simultaneously generalizes the chromatic number χ(G) and the clique covering number θ(G), and is important in studying the speed of hereditary properties and edit distances of graphs. It is easy to see that for every graph G the bichromatic number χ^b(G) is bounded above by χ(G)+θ(G)?1. In this article, we characterize all graphs G for which the upper bound is attained, i.e., χ^b(G)=χ(G)+θ(G)?1. It turns out that all these graphs are cographs and in fact they are the critical graphs with respect to the (k, l)‐colorability of cographs. More specifically, we show that a cograph H is not (k, l)‐colorable if and only if H contains an induced subgraph G with χ(G)=k+1, θ(G)=l+1 and χ^b(G)=k+l+1. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 263–269, 2010     

Nonnegative functions in weighted hardy spaces

Let W be a nonnegative summable function whose logarithm is also summable with respect to the Lebesgue measure on the unit circle. For 0?<?p?<?∞ , H^p (W) denotes a weighted Hardy space on the unit circle. When W?≡?1, H ^p(W) is the usual Hardy space H^p . We are interested in H^p ( W)₊ the set of all nonnegative functions in H^p ( W). If p?≥?1/2, H^p ₊ consists of constant functions. However H^p ( W)₊ contains a nonconstant nonnegative function for some weight W. In this paper, if p?≥?1/2 we determine W and describe H^p ( W)₊ when the linear span of H^p ( W)₊ is of finite dimension. Moreover we show that the linear span of H^p (W)₊ is of infinite dimension for arbitrary weight W when 0?<?p?<?1/2.     

The minimum degree of Ramsey‐minimal graphs

We write H → G if every 2‐coloring of the edges of graph H contains a monochromatic copy of graph G. A graph H is G‐minimal if H → G, but for every proper subgraph H′ of H, H′ ? G. We define s(G) to be the minimum s such that there exists a G‐minimal graph with a vertex of degree s. We prove that s(K_k) = (k ? 1)² and s(K_a,b) = 2 min(a,b) ? 1. We also pose several related open problems. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 167–177, 2007     

Periods in missing lengths of rainbow cycles

A cycle in an edge‐colored graph is said to be rainbow if no two of its edges have the same color. For a complete, infinite, edge‐colored graph G, define Then ??(G) is a monoid with respect to the operation n°m=n+ m?2, and thus there is a least positive integer π(G), the period of ??(G), such that ??(G) contains the arithmetic progression {N+ kπ(G)|k?0} for some sufficiently large N. Given that n∈??(G), what can be said about π(G)? Alexeev showed that π(G)=1 when n?3 is odd, and conjectured that π(G) always divides 4. We prove Alexeev's conjecture: Let p(n)=1 when n is odd, p(n)=2 when n is divisible by four, and p(n)=4 otherwise. If 2<n∈??(G) then π(G) is a divisor of p(n). Moreover, ??(G) contains the arithmetic progression {N+ kp(n)|k?0} for some N=O(n²). The key observations are: If 2<n=2k∈??(G) then 3n?8∈??(G). If 16≠n=4k∈??(G) then 3n?10∈??(G). The main result cannot be improved since for every k>0 there are G, H such that 4k∈??(G), π(G)=2, and 4k+ 2∈??(H), π(H)=4. © 2009 Wiley Periodicals, Inc. J Graph Theory     

Pan-H-Linked Graphs

Let H be a multigraph, possibly containing loops. An H-subdivision is any simple graph obtained by replacing the edges of H with paths of arbitrary length. Let H be an arbitrary multigraph of order k, size m, n ₀(H) isolated vertices and n ₁(H) vertices of degree one. In Gould and Whalen (Graphs Comb. 23:165–182, 2007) it was shown that if G is a simple graph of order n containing an H-subdivision H{\mathcal{H}} and d(G) 3 \fracn+m-k+n₁(H)+2n₀(H)2{\delta(G) \ge \frac{n+m-k+n_1(H)+2n_0(H)}{2}}, then G contains a spanning H-subdivision with the same ground set as H{\mathcal{H}} . As a corollary to this result, the authors were able to obtain Dirac’s famed theorem on hamiltonian graphs; namely that if G is a graph of order n ≥ 3 with d(G) 3 \fracn2{\delta(G)\ge\frac{n}{2}} , then G is hamiltonian. Bondy (J. Comb. Theory Ser. B 11:80–84, 1971) extended Dirac’s theorem by showing that if G satisfied the condition d(G) 3 \fracn2{\delta(G) \ge \frac{n}{2}} then G was either pancyclic or a complete bipartite graph. In this paper, we extend the result from Gould and Whalen (Graphs Comb. 23:165–182, 2007) in a similar manner. An H-subdivision H{\mathcal{H}} in G is 1-extendible if there exists an H-subdivision H^*{\mathcal{H}^{*}} with the same ground set as H{\mathcal{H}} and |H^*| = |H| + 1{|\mathcal{H}^{*}| = |\mathcal{H}| + 1} . If every H-subdivision in G is 1-extendible, then G is pan-H-linked. We demonstrate that if H is sufficiently dense and G is a graph of large enough order n such that d(G) 3 \fracn+m-k+n₁(H)+2n₀(H)2{\delta(G) \ge \frac{n+m-k+n_1(H)+2n_0(H)}{2}} , then G is pan-H-linked. This result is sharp.     

Weak factorizations of operators in the group von Neumann algebras of certain amenable groups and applications

Let G be a compact group whose local weight b(G) has uncountable cofinality. Let H be an amenable locally compact group and A(G × H) be the Fourier algebra of G × H. We prove that the group von Neumann algebra VN(G × H) = A(G × H)^* has the weak uniform A(G × H)^** factorization property of level b(G). As a corollary we show that A(G × H) is strongly Arens irregular, and the topological centre of UC ₂(G × H)^* is equal to the Fourier–Stieltjes algebra B(G × H).     

Multiderivations of Coxeter arrangements

Let V be an ℓ-dimensional Euclidean space. Let G⊂O(V) be a finite irreducible orthogonal reflection group. Let ? be the corresponding Coxeter arrangement. Let S be the algebra of polynomial functions on V. For H∈? choose α _H ∈V ^* such that H=ker(α _H ). For each nonnegative integer m, define the derivation module D ^(m) (?)={θ∈Der _S |θ(α _H )∈Sα ^m _H }. The module is known to be a free S-module of rank ℓ by K. Saito (1975) for m=1 and L. Solomon-H. Terao (1998) for m=2. The main result of this paper is that this is the case for all m. Moreover we explicitly construct a basis for D ^(m) (?). Their degrees are all equal to mh/2 (when m is even) or are equal to ((m−1)h/2)+m _i (1≤i≤ℓ) (when m is odd). Here m ₁≤···≤m _ℓ are the exponents of G and h=m _ℓ+1 is the Coxeter number. The construction heavily uses the primitive derivation D which plays a central role in the theory of flat generators by K. Saito (or equivalently the Frobenius manifold structure for the orbit space of G). Some new results concerning the primitive derivation D are obtained in the course of proof of the main result. Oblatum 27-XI-2001 & 4-XII-2001?Published online: 18 February 2002     

The chromatic number of the product of two 4-chromatic graphs is 4

For any graphG and numbern≧1 two functionsf, g fromV(G) into {1, 2, ...,n} are adjacent if for all edges (a, b) ofG, f(a) ≠g(b). The graph of all such functions is the colouring graph ℒ(G) ofG. We establish first that χ(G)=n+1 implies χ(ℒ(G))=n iff χ(G ×H)=n+1 for all graphsH with χ(H)≧n+1. Then we will prove that indeed for all 4-chromatic graphsG χ(ℒ(G))=3 which establishes Hedetniemi’s [3] conjecture for 4-chromatic graphs. This research was supported by NSERC grant A7213     

On point-halfspace graphs

The following definition is motivated by the study of circle orders and their connections to graphs. A graphs G is called a point-halfspace graph (in R ^k) provided one can assign to each vertex v ? (G) a point p _v R ^k and to each edge e ? E(G) a closed halfspace H_e ? R ^k so that v is incident with e if and only if p _v ? H_e. Let H ^k denote the set of point-halfspace graphs (in R ^k). We give complete forbidden subgraph and structural characterizations of the classes H ^k for every k. Surprisingly, these classes are closed under taking minors and we give forbidden minor characterizations as well. © 1996 John Wiley & Sons, Inc.     

Stability of semilinear ill-posed problems with a prescribed energy bound

In the present paper we discuss the stability of semilinear problems of the form A^αu + G^α(u) = ? under assumption of an a priori bound for an energy functional E^α(u) ? E, where α is a parameter in a metric space M. Following [11] the problem A^αu + G^α(u) = ?, E^α(u) ? E is called stable in a Hilbert space H at a point α ? M if for any ??H, E, ? > 0 there exists δ > 0 such that for any functions u^α1, u^α2 satisfying A^αju^αj + G^αj(u^αj) = ?^αj, E^αj(u^αj) ? E, j = 1,2 we have ‖u^α1 ? u^α2_H ? ? provided ρ_M(α_j, α) ? δ, ‖?^αj ? ?‖_H ? δ, j = 1,2. In the present paper we obtain stability conditions for the problem A^αu + G^α(u) = ?, E^α(u) ? E.     

Power cocentralizing generalized derivations on prime rings

Let R be a prime ring, U the Utumi quotient ring of R, C = Z(U) the extended centroid of R, L a non-central Lie ideal of R, H and G non-zero generalized derivations of R. Suppose that there exists an integer n ≥ 1 such that (H(u)u − uG(u)) ⁿ = 0, for all u ∈ L, then one of the following holds: (1) there exists c ∈ U such that H(x) = xc, G(x) = cx; (2) R satisfies the standard identity s ₄ and char (R) = 2; (3) R satisfies s ₄ and there exist a, b, c ∈ U, such that H(x) = ax+xc, G(x) = cx+xb and (a − b) ⁿ = 0.     

Balloons,cut‐edges,matchings, and total domination in regular graphs of odd degree

A balloon in a graph G is a maximal 2‐edge‐connected subgraph incident to exactly one cut‐edge of G. Let b(G) be the number of balloons, let c(G) be the number of cut‐edges, and let α′(G) be the maximum size of a matching. Let ${\mathcal{F}}_{{{n}},{{r}}}A balloon in a graph G is a maximal 2‐edge‐connected subgraph incident to exactly one cut‐edge of G. Let b(G) be the number of balloons, let c(G) be the number of cut‐edges, and let α′(G) be the maximum size of a matching. Let ${\mathcal{F}}_{{{n}},{{r}}}$ be the family of connected (2r+1)‐regular graphs with n vertices, and let ${{b}}={{max}}\{{{b}}({{G}}): {{G}}\in {\mathcal{F}}_{{{n}},{{r}}}\}$. For ${{G}}\in{\mathcal{F}}_{{{n}},{{r}}}$, we prove the sharp inequalities c(G)?[r(n?2)?2]/(2r²+2r?1)?1 and α′(G)?n/2?rb/(2r+1). Using b?[(2r?1)n+2]/(4r²+4r?2), we obtain a simple proof of the bound proved by Henning and Yeo. For each of these bounds and each r, the approach using balloons allows us to determine the infinite family where equality holds. For the total domination number γ_t(G) of a cubic graph, we prove γ_t(G)?n/2?b(G)/2 (except that γ_t(G) may be n/2?1 when b(G)=3 and the balloons cover all but one vertex). With α′(G)?n/2?b(G)/3 for cubic graphs, this improves the known inequality γ_t(G)?α′(G). © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 116–131, 2010     

On the dimension of trees

It is proved that for trees (and forests) G one has dimG?3 log⁺₂∣G∣(where dim G, the dimension of G, is the minimum k such that G is embeddable into a product of k complete graphs; ∣G∣ is the size of G). Moreover, if m(G) is the quotient of G obtained by identifying the points with coinciding neighbour sets, one has, for forests G, log⁺₂ ∣m(G)∣ ? 1 ? dimG ? 3 log⁺₂m(G>) + 1. Also, for the bipartite dimension bid G (arising from embeddings into P^k₃) one has bid G ? 8 log⁺₂ ∣G ∣.     

On the Heterochromatic Number of Hypergraphs Associated to Geometric Graphs and to Matroids

The heterochromatic number h _c (H) of a non-empty hypergraph H is the smallest integer k such that for every colouring of the vertices of H with exactly k colours, there is a hyperedge of H all of whose vertices have different colours. We denote by ν(H) the number of vertices of H and by τ(H) the size of the smallest set containing at least two vertices of each hyperedge of H. For a complete geometric graph G with n ≥ 3 vertices let H = H(G) be the hypergraph whose vertices are the edges of G and whose hyperedges are the edge sets of plane spanning trees of G. We prove that if G has at most one interior vertex, then h _c (H) = ν(H) ? τ(H) + 2. We also show that h _c (H) = ν(H) ? τ(H) + 2 whenever H is a hypergraph with vertex set and hyperedge set given by the ground set and the bases of a matroid, respectively.     

Hamilton cycles and closed trails in iterated line graphs

Let G be an undirected connected graph that is not a path. We define h(G) (respectively, s(G)) to be the least integer m such that the iterated line graph L^m(G) has a Hamiltonian cycle (respectively, a spanning closed trail). To obtain upper bounds on h(G) and s(G), we characterize the least integer m such that L^m(G) has a connected subgraph H, in which each edge of H is in a 3-cycle and V(H) contains all vertices of degree not 2 in L^m(G). We characterize the graphs G such that h(G) — 1 (respectively, s(G)) is greater than the radius of G.