Star-critical Ramsey numbers

The graph Ramsey numberR(G,H) is the smallest integer r such that every 2-coloring of the edges of K_r contains either a red copy of G or a blue copy of H. We find the largest star that can be removed from K_r such that the underlying graph is still forced to have a red G or a blue H. Thus, we introduce the star-critical Ramsey numberr_∗(G,H) as the smallest integer k such that every 2-coloring of the edges of K_r−K_1,r−1−k contains either a red copy of G or a blue copy of H. We find the star-critical Ramsey number for trees versus complete graphs, multiple copies of K₂ and K₃, and paths versus a 4-cycle. In addition to finding the star-critical Ramsey numbers, the critical graphs are classified for R(T_n,K_m), R(nK₂,mK₂) and R(P_n,C₄).     

Bipartite rainbow numbers of matchings

Given two graphs G and H, let f(G,H) denote the maximum number c for which there is a way to color the edges of G with c colors such that every subgraph H of G has at least two edges of the same color. Equivalently, any edge-coloring of G with at least rb(G,H)=f(G,H)+1 colors contains a rainbow copy of H, where a rainbow subgraph of an edge-colored graph is such that no two edges of it have the same color. The number rb(G,H) is called the rainbow number ofHwith respect toG, and simply called the bipartite rainbow number ofH if G is the complete bipartite graph K_m,n. Erd?s, Simonovits and Sós showed that rb(K_n,K₃)=n. In 2004, Schiermeyer determined the rainbow numbers rb(K_n,K_k) for all n≥k≥4, and the rainbow numbers rb(K_n,kK₂) for all k≥2 and n≥3k+3. In this paper we will determine the rainbow numbers rb(K_m,n,kK₂) for all k≥1.     

On ideals in the bidual of the Fourier algebra and related algebras

Let G be a compact nonmetrizable topological group whose local weight b(G) has uncountable cofinality. Let H be an amenable locally compact group, A(G×H) the Fourier algebra of G×H, and UC₂(G×H) the space of uniformly continuous functionals in VN(G×H)=A^∗(G×H). We use weak factorization of operators in the group von Neumann algebra VN(G×H) to prove that there exist at least ²b(G)² left ideals of dimensions at least ²b(G)² in A(G×H)^∗∗ and in UC₂^∗(G×H). We show that every nontrivial right ideal in A(G×H)^∗∗ and in UC₂^∗(G×H) has dimension at least ²b(G)².     

Spectral bounds for the clique and independence numbers of graphs

We obtain a sequence k₁(G) ≤ k₂(G) ≤ … ≤ k_n(G) of lower bounds for the clique number (size of the largest clique) of a graph G of n vertices. The bounds involve the spectrum of the adjacency matrix of G. The bound k₁(G) is explicit and improves earlier known theorems. The bound k₂(G) is also explicit, and is shown to improve on the bound from Brooks' theorem even for regular graphs. The bounds k₃,…, k_r are polynomial-time computable, where r is the number of positive eigenvalues of G.     

On regular bipartite-preserving supergraphs

For a graphG with chromatic numberχ(G) ? 2 and maximum degree Δ(G), there exists anr-regular graphH, for everyr ? Δ(G), such thatG is an induced subgraph ofH and_χ(H) =_χ (G). In the case whereG is bipartite, the minimum order of such a graphH is determined.     

Generators and commutators in finite groups; abstract quotients of compact groups

The first part of the paper establishes results about products of commutators in a d-generator finite group G, for example: if H?G=??g ₁,??,g _r ?? then every element of the subgroup [H,G] is a product of f(r) factors of the form $[h_{1},g_{1}][h_{1}^{\prime},g_{1}^{-1}]\ldots\lbrack h_{r},g_{r}][h_{r}^{\prime },g_{r}^{-1}]$ with $h_{1},h_{1}^{\prime},\ldots,\allowbreak h_{r},h_{r}^{\prime }\in H$ . Under certain conditions on H, a similar conclusion holds with the significantly weaker hypothesis that G=H??g ₁,??,g _r ??, where f(r) is replaced by f ₁(d,r). The results are applied in the second part of the paper to the study of normal subgroups in finitely generated profinite groups, and in more general compact groups. Results include the characterization of (topologically) finitely generated compact groups which have a countably infinite image, and of those which have a virtually dense normal subgroup of infinite index. As a corollary it is deduced that a compact group cannot have a finitely generated infinite abstract quotient.     

On profinite groups in which commutators are covered by finitely many subgroups

For a family of group words w we show that if G is a profinite group in which all w-values are contained in a union of finitely many subgroups with a prescribed property, then the verbal subgroup w(G) has the same property as well. In particular, we show this in the case where the subgroups are periodic or of finite rank. If G contains finitely many subgroups G ₁, G ₂, . . . , G _s of finite exponent e whose union contains all γ _k -values in G, it is shown that γ _k (G) has finite (e, k, s)-bounded exponent. If G contains finitely many subgroups G ₁, G ₂, . . . , G _s of finite rank r whose union contains all γ _k -values, it is shown that γ _k (G) has finite (k, r, s)-bounded rank.     

The connected Ramsey number

A graph G is totally connected if both G and ? (its complement) are connected. The connected Ramsey number r_c(F, H) is the smallest integer k ? 4 so that if G is a totally connected graph of order k then either F ? G or H ? ?. We show that if neither of F nor H contains a bridge, then r_c = r(F, H), the usual generalized Ramsey number of F and H. We compute r_c (P_mP_m), the connected Ramsey number for paths.     

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.     

Diameter-girth sufficient conditions for optimal extraconnectivity in graphs

For a connected graph G, the rth extraconnectivity κ_r(G) is defined as the minimum cardinality of a cutset X such that all remaining components after the deletion of the vertices of X have at least r+1 vertices. The standard connectivity and superconnectivity correspond to κ₀(G) and κ₁(G), respectively. The minimum r-tree degree of G, denoted by ξ_r(G), is the minimum cardinality of N(T) taken over all trees T⊆G of order |V(T)|=r+1, N(T) being the set of vertices not in T that are neighbors of some vertex of T. When r=1, any such considered tree is just an edge of G. Then, ξ₁(G) is equal to the so-called minimum edge-degree of G, defined as ξ(G)=min{d(u)+d(v)-2:uv∈E(G)}, where d(u) stands for the degree of vertex u. A graph G is said to be optimally r-extraconnected, for short κ_r-optimal, if κ_r(G)?ξ_r(G). In this paper, we present some sufficient conditions that guarantee κ_r(G)?ξ_r(G) for r?2. These results improve some previous related ones, and can be seen as a complement of some others which were obtained by the authors for r=1.     

Ramsey-goodness—and otherwise

A celebrated result of Chvátal, Rödl, Szemerédi and Trotter states (in slightly weakened form) that, for every natural number Δ, there is a constant r _Δ such that, for any connected n-vertex graph G with maximum degree Δ, the Ramsey number R(G,G) is at most r _Δ n, provided n is sufficiently large. In 1987, Burr made a strong conjecture implying that one may take r _Δ = Δ. However, Graham, Rödl and Ruciński showed, by taking G to be a suitable expander graph, that necessarily r _Δ > 2 ^cΔ for some constant c>0. We show that the use of expanders is essential: if we impose the additional restriction that the bandwidth of G be at most some function β(n)=o(n), then R(G,G)≤(2χ(G)+4)n≤(2Δ+6)n, i.e., r _Δ =2Δ+6 suffices. On the other hand, we show that Burr’s conjecture itself fails even for P _n ^k , the kth power of a path P _n . Brandt showed that for any c, if Δ is sufficiently large, there are connected n-vertex graphs G with Δ(G)≤Δ but R(G,K ₃) > cn. We show that, given Δ and H, there are β>0 and n ₀ such that, if G is a connected graph on n≥n ₀ vertices with maximum degree at most Δ and bandwidth at most β _n , then we have R(G,H)=(χ(H)?1)(n?1)+σ(H), where σ(H) is the smallest size of any part in any χ(H)-partition of H. We also show that the same conclusion holds without any restriction on the maximum degree of G if the bandwidth of G is at most ?(H) log n=log logn.     

Constructing and classifying neighborhood anti-Sperner graphs

For a simple graph G let N_G(u) be the (open) neighborhood of vertex u∈V(G). Then G is neighborhood anti-Sperner (NAS) if for every u there is a v∈V(G)?{u} with N_G(u)⊆N_G(v). And a graph H is neighborhood distinct (ND) if every neighborhood is distinct, i.e., if N_H(u)≠N_H(v) when u≠v, for all u and v∈V(H).In Porter and Yucas [T.D. Porter, J.L. Yucas. Graphs whose vertex-neighborhoods are anti-sperner, Bulletin of the Institute of Combinatorics and its Applications 44 (2005) 69-77] a characterization of regular NAS graphs was given: ‘each regular NAS graph can be obtained from a host graph by replacing vertices by null graphs of appropriate sizes, and then joining these null graphs in a prescribed manner’. We extend this characterization to all NAS graphs, and give algorithms to construct all NAS graphs from host ND graphs. Then we find and classify all connected r-regular NAS graphs for r=0,1,…,6.     

On the finite prime spectrum minimal groups

Let G be a finite group. The set of all prime divisors of the order of G is called the prime spectrum of G and is denoted by π(G). A group G is called prime spectrum minimal if π(G) ≠ π(H) for any proper subgroup H of G. We prove that every prime spectrum minimal group all of whose nonabelian composition factors are isomorphic to the groups from the set {PSL ₂(7), PSL ₂(11), PSL ₅(2)} is generated by two conjugate elements. Thus, we extend the corresponding result for finite groups with Hall maximal subgroups. Moreover, we study the normal structure of a finite prime spectrum minimal group with a nonabelian composition factor whose order is divisible by exactly three different primes.     

Representations and cohomology for Frobenius-Lusztig kernels

Let U_ζ be the quantum group (Lusztig form) associated to the simple Lie algebra g, with parameter ζ specialized to an ?-th root of unity in a field of characteristic p>0. In this paper we study certain finite-dimensional normal Hopf subalgebras U_ζ(G_r) of U_ζ, called Frobenius-Lusztig kernels, which generalize the Frobenius kernels G_r of an algebraic group G. When r=0, the algebras studied here reduce to the small quantum group introduced by Lusztig. We classify the irreducible U_ζ(G_r)-modules and discuss their characters. We then study the cohomology rings for the Frobenius-Lusztig kernels and for certain nilpotent and Borel subalgebras corresponding to unipotent and Borel subgroups of G. We prove that the cohomology ring for the first Frobenius-Lusztig kernel is finitely-generated when g has type A or D, and that the cohomology rings for the nilpotent and Borel subalgebras are finitely-generated in general.     

Modules over integer group rings of locally soluble groups with minimax restriction

Let ? be the ring of integers, and A be a ?G-module, where A/C _A (G) is not a minimax ?-module, C _G (A) = 1, and G is a locally soluble group. Let L _nm(G) be the system of all subgroups H ?? G such that quotient modules A/C _A (H) are not minimax Z-modules. The author studies ?G-modules A such that L _nm(G) satisfies the minimal condition as an ordered set. It is proved that a locally soluble group G with these conditions is soluble. The structure of the group G is described.     

Some Asymptotic ith Ramsey numbers

Let G be a graph with chromatic number χ(G) and let t(G) be the minimum number of vertices in any color class among all χ(G)-vertex colorings of G. Let H′ be a connected graph and let H be a graph obtained by subdividing (adding extra vertices to) a fixed edge of H′. It is proved that if the order of H is sufficiently large, the ith Ramsey number r_i(G, H) equals $\text{[}\text{((χ(G)?1)(|}\text{H}\text{|?1)+t(G)?1)}\text{i}\text{]+1}$.     

On the existence of two non-neighboring subgraphs in a graph

Does there exist a functionf(r, n) such that each graphG with _Z (G)≧f(r, n) contains either a complete subgraph of orderr or else two non-neighboringn-chromatic subgraphs? It is known thatf(r, 2) exists and we establish the existence off(r, 3). We also give some interesting results about graphs which do not contain two independent edges.     

Weighted L p-Approximation of Derivatives by the Method of Gammaoperators

We consider Gammaoperators G _n on suitable Sobolev type subspaces of L _p(0, ∞) and characterize the global rate of approximation of derivatives f ^(r) through corresponding derivatives (G _n f)^(r) in an appropriate weighted L _p — metric by the rate of Ditzian and Totik’s second order weighted modulus of smoothness.     

On two problems in graph Ramsey theory

We study two classical problems in graph Ramsey theory, that of determining the Ramsey number of bounded-degree graphs and that of estimating the induced Ramsey number for a graph with a given number of vertices. The Ramsey number r(H) of a graph H is the least positive integer N such that every two-coloring of the edges of the complete graph K _N contains a monochromatic copy of H. A famous result of Chváatal, Rödl, Szemerédi and Trotter states that there exists a constant c(Δ) such that r(H) ≤ c(Δ)n for every graph H with n vertices and maximum degree Δ. The important open question is to determine the constant c(Δ). The best results, both due to Graham, Rödl and Ruciński, state that there are positive constants c and c′ such that $2^{c'\Delta } \leqslant c(\Delta ) \leqslant ^{c\Delta \log ^2 \Delta }$ . We improve this upper bound, showing that there is a constant c for which c(Δ) ≤ 2 ^cΔlogΔ . The induced Ramsey number r _ind (H) of a graph H is the least positive integer N for which there exists a graph G on N vertices such that every two-coloring of the edges of G contains an induced monochromatic copy of H. Erd?s conjectured the existence of a constant c such that, for any graph H on n vertices, r _ind (H) ≤ 2 ^cnlogn . We move a step closer to proving this conjecture, showing that r _ind (H) ≤ 2 ^cnlogn . This improves upon an earlier result of Kohayakawa, Prömel and Rödl by a factor of logn in the exponent.