On 2‐factors of a bipartite graph

In this article, we consider the following problem: Given a bipartite graph G and a positive integer k, when does G have a 2‐factor with exactly k components? We will prove that if G = (V₁, V₂, E) is a bipartite graph with |V₁| = |V₂| = n ≥ 2k + 1 and δ (G) ≥ ⌈n/2⌉ + 1, then G contains a 2‐factor with exactly k components. We conjecture that if G = (V₁, V₂; E) is a bipartite graph such that |V₁| = |V₂| = n ≥ 2 and δ (G) ≥ ⌈n/2⌉ + 1, then, for any bipartite graph H = (U₁, U₂; F) with |U₁| ≤ n, |U₂| ≤ n and Δ (H) ≤ 2, G contains a subgraph isomorphic to H. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 101–106, 1999     

Some remarks on universal graphs

LetΓ be a class of countable graphs, and let ℱ(Γ) denote the class of all countable graphs that do not contain any subgraph isomorphic to a member ofΓ. Furthermore, letTΓ andHΓ denote the class of all subdivisions of graphs inΓ and the class of all graphs contracting to a member ofΓ, respectively. As the main result of this paper it is decided which of the classes ℱ(TK ⁿ ) and ℱ(HK ⁿ ),n≦ℵ₀, contain a universal element. In fact, for ℱ(TK ⁴)=ℱ(HK ⁴) a strongly universal graph is constructed, whereas for 5≦n≦ℵ₀ the classes ℱ(TK ⁿ ) and ℱ(HK ⁿ ) have no universal elements. Dedicated to Klaus Wagner on his 75^th birthday     

Affinely equivalent complete flat manifolds

Let E _Aff(Γ,G, m) be the set of affine equivalence classes of m-dimensional complete flat manifolds with a fixed fundamental group Γ and a fixed holonomy group G. Let n be the dimension of a closed flat manifold whose fundamental group is isomorphic to Γ. We describe E _Aff(Γ,G, m) in terms of equivalence classes of pairs (ε, ρ), consisting of epimorphisms of Γ onto G and representations of G in ℝ ^m-n . As an application we give some estimates of card E _Aff(Γ,G, m).     

On Vertex-Disjoint Complete Bipartite Subgraphs in a Bipartite Graph

 We show that, if G=(X,Y;E) is a bipartite graph with |X|=|Y|=4s and δ(G)≥4s−3 for any integer s≥2, then G contains four vertex-disjoint copies of K _s,s. This constitutes a partial answer to a conjecture in [4]. Received: March 27, 1996 Revised: March 7, 1997     

Packing cycles with modularity constraints

We prove that for all positive integers k, there exists an integer N =N(k) such that the following holds. Let G be a graph and let Γ an abelian group with no element of order two. Let γ: E(G)→Γ be a function from the edges of G to the elements of Γ. A non-zero cycle is a cycle C such that Σ _e∈E(C) γ(e) ≠ 0 where 0 is the identity element of Γ. Then G either contains k vertex disjoint non-zero cycles or there exists a set X ⊆ V (G) with |X| ≤N(k) such that G−X contains no non-zero cycle.     

Principal bundles whose restrictions to a curve are isomorphic

Let X be a normal projective variety defined over an algebraically closed field k. Let |O _X (1)| be a very ample invertible sheaf on X. Let G be an affine algebraic group defined over k. Let E _G and F _G be two principal G-bundles on X. Then there exists an integer n > > 0 (depending on E _G and F _G ) such that if the restrictions of E _G and F _G to a curve C ∈ |O _X (n)| are isomorphic, then they are isomorphic on all of X.     

On Enomoto’s problems in a bipartite graph

In this paper, we obtain the following result: Let k, n ₁ and n ₂ be three positive integers, and let G = (V ₁,V ₂;E) be a bipartite graph with |V1| = n ₁ and |V ₂| = n ₂ such that n ₁ ⩾ 2k + 1, n ₂ ⩾ 2k + 1 and |n ₁ − n ₂| ⩽ 1. If d(x) + d(y) ⩾ 2k + 2 for every x ∈ V ₁ and y ∈ V ₂ with xy $ \notin $ \notin E(G), then G contains k independent cycles. This result is a response to Enomoto’s problems on independent cycles in a bipartite graph.     

On weakly τ-quasinormal subgroups of finite groups

Let G be a finite group and H a subgroup of G. We say that: (1) H is τ-quasinormal in G if H permutes with all Sylow subgroups Q of G such that (|Q|, |H|) = 1 and (|H|, |Q ^G |) ≠ 1; (2) H is weakly τ-quasinormal in G if G has a subnormal subgroup T such that HT = G and T ∩ H ≦ H _τG , where H _τG is the subgroup generated by all those subgroups of H which are τ-quasinormal in G. Our main result here is the following. Let ℱ be a saturated formation containing all supersoluble groups and let X ≦ E be normal subgroups of a group G such that G/E ∈ ℱ. Suppose that every non-cyclic Sylow subgroup P of X has a subgroup D such that 1 < |D| < |P| and every subgroup H of P with order |H| = |D| and every cyclic subgroup of P with order 4 (if |D| = 2 and P is non-Abelian) not having a supersoluble supplement in G is weakly τ-quasinormal in G. If X is either E or F* (E), then G ∈ ℱ.     

Random weighting,asymptotic counting,and inverse isoperimetry

For a family X of k-subsets of the set {1, …, n}, let |X| be the cardinality of X and let Γ(X, μ) be the expected maximum weight of a subset from X when the weights of 1, …, n are chosen independently at random from a symmetric probability distribution μ on ℝ. We consider the inverse isoperimetric problem of finding μ for which Γ(X, μ) gives the best estimate of ln |X|. We prove that the optimal choice of μ is the logistic distribution, in which case Γ(X, μ) provides an asymptotically tight estimate of ln |X| as k ⁻¹ ln |X} grows. Since in many important cases Γ(X, μ) can be easily computed, we obtain computationally efficient approximation algorithms for a variety of counting problems. Given μ, we describe families X of a given cardinality with the minimum value of Γ(X, μ), thus extending and sharpening various isoperimetric inequalities in the Boolean cube. The research of the first author was partially supported by NSF Grants DMS 9734138 and DMS 0400617. The research of the second author was partially supported by ISF Grant 039-7165 and by GIF grant I-2052.     

Gromov hyperbolic cubic graphs

If X is a geodesic metric space and x ₁; x ₂; x ₃ ∈ X, a geodesic triangle T = {x ₁; x ₂; x ₃} is the union of the three geodesics [x ₁ x ₂], [x ₂ x ₃] and [x ₃ x ₁] in X. The space X is δ-hyperbolic (in the Gromov sense) if any side of T is contained in a δ-neighborhood of the union of the two other sides, for every geodesic triangle T in X. We denote by δ(X) the sharp hyperbolicity constant of X, i.e., δ(X) = inf {δ ≥ 0: X is δ-hyperbolic}. We obtain information about the hyperbolicity constant of cubic graphs (graphs with all of their vertices of degree 3), and prove that for any graph G with bounded degree there exists a cubic graph G* such that G is hyperbolic if and only if G* is hyperbolic. Moreover, we prove that for any cubic graph G with n vertices, we have δ(G) ≤ min {3n/16 + 1; n/4}. We characterize the cubic graphs G with δ(G) ≤ 1. Besides, we prove some inequalities involving the hyperbolicity constant and other parameters for cubic graphs.     

An upper bound for the cardinality of ans-distance subset in real euclidean space,II

It is shown that ifX is ans-distance subset inR ^d , then |X|≦( _s ^d+s ). Supported in part by NSF grant MCS7903128 A01. Supported in part by NSF grant MCS.     

On semigroups generated by restrictions of elliptic operators to invariant subspaces

Let A be the closed unbounded operator inL _p(G) that is associated with an elliptic boundary value problem for a bounded domainG. We prove the existence of a spectral projectionE determined by the set Γ = {λ;θ ₁≦argλ≦θ ₂} and show thatAE is the infinitesimal generator of an analytic semigroup provided that the following conditions hold: 1<p<∞; the boundary ϖΓ of Γ is contained in the resolvent setp(A) ofA;π/2≦θ<θ ₂≦3π/2 ; and there exists a constantc such that (I)││(λ-A)^-1││≦c/│λ│ for λ∈ϖΓ. The following consequence is obtained: Suppose that there exist constantsM andc such that λ∈p(A) and estimate (I) holds provided that |λ|≧M and Re λ=0. Then there exist bounded projectionE ⁻ andE ⁺ such thatA is completely reduced by the direct sum decompositionL _p(G)=E⁻L_p (G) ⊕E⁺L_p (G) and each of the operatorsAE ⁻ and—AE ⁺ is the infinitestimal generator of an analytic semigroup.     

Banded perturbations of the unit vector basis in some sequence spaces

Perturbations of the unit vector basis of the formX _n =Σ_|j−n|≦m a _nj e _j wherem is a fixed positive integer are investigated. It is shown that if |a _nj |≦1 and if {x _n } possesses a biorthogonal sequence uniformly bounded inl _p for some 1<=p<∞, then {x _n } is a seminormalized basic sequence in some reflexive Orlicz spacel _N, then {x_n} is equivalent to {e _n} inl _N.     

Deformations of complex structures on Γ/SL 2(C)

LetG be a connected complex semisimple Lie group. Let Γ be a cocompact lattice inG. In this paper, we show that whenG isSL ₂(C), nontrivial deformations of the canonical complex structure onX exist if and only if the first Betti number of the lattice Γ is non-zero. It may be remarked that for a wide class of arithmetic groups Γ, one can find a subgroup Γ′ of finite index in Γ, such that Γ′/[Γ′,Γ′] is finite (it is a conjecture of Thurston that this is true for all cocompact lattices inSL(2, C)). We also show thatG acts trivially on the coherent cohomology groupsH ⁱ(Γ/G, O) for anyi≥0.     

On Independent Cycles in a Bipartite Graph

 Let G=(V ₁,V ₂;E) be a bipartite graph with 2k≤m=|V ₁|≤|V ₂|=n, where k is a positive integer. We show that if the number of edges of G is at least (2k−1)(n−1)+m, then G contains k vertex-disjoint cycles, unless e(G)=(2k−1)(n−1)+m and G belongs to a known class of graphs. Received: December 9, 1998 Final version received: June 2, 1999     

An ergodic theorem on Banach lattices

E is a Banach lattice that is weakly sequentially complete and has a weak unitu. TLf _n=ϕ means that the infimum of |f _n−ϕ| andu converges strongly to zero.T is a positive contraction operator onE andA _n=(1/n)(I+T+...+T ⁿ⁻¹). Without an additional assumption onE, the “truncated limit” TLA _nf need not exist forf inE. This limit exists for eachf ifE satisfies the following additional assumption (C): For everyf inE ₊ and for every numberα>0, there is a numberβ=β(f, α) such that ifg is inE ₊, ‖g‖≦1, 0≦f′≦f and ‖f′‖>α then ‖f′+g‖≧‖g‖+β. Research of this author is partially supported by NSERC Grant A3974. Research of this author is partially supported by NSF Grant 8301619.     

Remarks on the descriptive metric characterization of singular sets of analytic functions

This work presents two remarks on the structure of singular boundary sets of functions analytic in the unit diskD: |z|<1. The first remark concerns the conversion of the Plessner theorem. We prove that three pairwise disjoint subsetsE ₁,E ₂, andE ₃ of the unit circle Γ: |z|=1, = Γ, are the setsI(ƒ) of all Plessner points,F(ƒ) of all Fatou points, andE(ƒ) of all exceptional boundary points, respectively, for a function ƒ holomorphic inD if and only ifE ₁ is aG _δ-set andE ₃ is a -set of linear measure zero. In the second part of the paper it is shown that for any -subsetE of the unit circle Γ with a zero logarithmic capacity there exists a one-sheeted function onD whose angular limits do not exist at the points ofE and do exist at all the other points of Γ. Translated fromMatematicheskie Zametki, Vol. 63, No. 1, pp. 56–61, January, 1998.     

The symmetric (2k,k)‐graphs

A noncomplete graph G is called an (n, k)‐graph if it is n‐connected and G − X is not (n − |X| + 1)‐connected for any X ⊆ V(G) with |X| ≤ k. Mader conjectured that for k ≥ 3 the graph K_{2k + 2} − (1‐factor) is the unique (2k, k)‐graph. We settle this conjecture for strongly regular graphs, for edge transitive graphs, and for vertex transitive graphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 36: 35–51, 2001     

Finiteness properties of chevalley groups overFq[t]

LetG be a simple Chevalley group of rankn and Γ=G( ). Then the finiteness length of Γ shall be determined by studying the action of Γ on the Bruhat-Tits buildingX ofG . This is always possible provided that certain subcomplexes of the links of simplices inX are spherical. As a consequence, one obtains that Γ is of typeF _n−1 but not of typeFP _n ifG is of typeA _n, B_n, C_n orD _n andq≥2²ⁿ⁻¹.     

Computation of Topological Indices of Some Graphs

Let G=(V,E) be a simple connected graph with vertex set V and edge set E. The Wiener index of G is defined by W(G)=∑_{x,y}⊆V d(x,y), where d(x,y) is the length of the shortest path from x to y. The Szeged index of G is defined by Sz(G)=∑ _e=uv∈E n _u (e|G)n _v (e|G), where n _u (e|G) (resp. n _v (e|G)) is the number of vertices of G closer to u (resp. v) than v (resp. u). The Padmakar–Ivan index of G is defined by PI(G)=∑ _e=uv∈E [n _eu (e|G)+n _ev (e|G)], where n _eu (e|G) (resp. n _ev (e|G)) is the number of edges of G closer to u (resp. v) than v (resp. u). In this paper we find the above indices for various graphs using the group of automorphisms of G. This is an efficient method of finding these indices especially when the automorphism group of G has a few orbits on V or E. We also find the Wiener indices of a few graphs which frequently arise in mathematical chemistry using inductive methods.