<Emphasis Type="Italic">k</Emphasis>-factors in regular graphs

Plesnik in 1972 proved that an （m - 1）-edge connected m-regular graph of even order has a 1-factor containing any given edge and has another 1-factor excluding any given m - 1 edges. Alder et al. in 1999 showed that if G is a regular （2n ＋ 1）-edge-connected bipartite graph, then G has a 1-factor containing any given edge and excluding any given matching of size n. In this paper we obtain some sufficient conditions related to the edge-connectivity for an n-regular graph to have a k-factor containing a set of edges and （or） excluding a set of edges, where 1 ≤ k ≤n/2. In particular, we generalize Plesnik＇s result and the results obtained by Liu et al. in 1998, and improve Katerinis＇ result obtained 1993. Furthermore, we show that the results in this paper are the best possible.     

Asymptotic formulas for some retricted partition functions

We use Rademacher’s method to obtain asymptotic expressions for some restricted partition functions. For fixed positive integers m > 1 and l, we consider the number p _m (n) of partitions of n into summands not divisible by m, and the number p _m ^l (n) of partitons of n with the further restriction that any integer occurs at most l times as a summand. 2000 Mathematics Subject Classification Primary—11P82; Secondary—11P83     

A splitting theorem for the weighted measure

Let M be an n-dimensional complete noncompact Riemannian manifold, h be a smooth function on M and dμ = e ^h dV be the weighted measure. In this article, we prove that when the spectrum of the weighted Laplacian \triangle_m{\triangle_{\mu}} has a positive lower bound λ₁(M) > 0 and the m(m > n)-dimensional Bakry-émery curvature is bounded from below by -\fracm-1m-2l₁(M){-\frac{m-1}{m-2}\lambda_1(M)}, then M splits isometrically as R × N whenever it has two ends with infinite weighted volume, here N is an (n − 1)-dimensional compact manifold.     

On the respective terms of the derived and the polycentral series of a free lie algabra and an ideal

Let F be a free Lie algebra of rank> 1 and S be an ideal of F. Denote by F_m and F_{n l},…,n_k the terms of the lower central and the polycentral series of F. The aim of this paper is to provide a sufficient condition for the quotient algebra F_{n l},…,n_k/S_{n l},…,n_k to be infinitely generated. The case F_m/S_m was studied in [6] for free groups and in [ 2 ] for free Lie algebras. In this paper the following main theorem is proved : If F = F2 = S, k > 1 and n_i > 1 for i=l,…, k, then F_{n l}…,n_k/S_{n l} is infinitely generated.     

Graphs with prescribed connectivity and line graph connectivity

Chartrand and Stewart have shown that the line graph of an n-connected graph is itself n-connected. This paper shows that for every pair of integers m > n > 1 there is a graph of point connectivity n whose line graph has point connectivity m. The corresponding question for line connectivity is also resolved.     

On the existence of (l,m,n)-spreads

We call a family ofm-flats of Pⁿ (K) an (l, m, n)-spread overK if it is a partition of the family of alll-flats. We prove two non-existence results for (l, m, n)-spreads in the case:K = GF(q) andl > 0.Alla memoria del Professor Giuseppe TalliniThis research was supported in part by M.U.R.S.T.     

Probabilities of Sentences about Very Sparse Random Graphs

We consider random graphs with edge probability βn^?α, where n is the number of vertices of the graph, β > 0 is fixed, and α = 1 or α = (l + 1) /l for some fixed positive integer l. We prove that for every first-order sentence, the probability that the sentence is true for the random graph has an asymptotic limit.     

On the structure of linear graphs

Denote byG(n; m) a graph ofn vertices andm edges. We prove that everyG(n; [n ²/4]+1) contains a circuit ofl edges for every 3 ≦l<c ₂ n, also that everyG(n; [n ²/4]+1) contains ak _e(u _n, u_n) withu _n=[c ₁ logn] (for the definition ofk _e(u _n, u_n) see the introduction). Finally fort>t ₀ everyG(n; [tn ^3/2]) contains a circuit of 2l edges for 2≦l<c ₃ t ². This work was done while the author received support from the National Science Foundation, N.S.F. G.88.     

Embeddingl p k in subspaces ofL p forp>2

The aim of the present paper is to estimate in a precise manner the integerk=k(p,m,n,∈) so that an arbitrarym-dimensional subspaceX of the spacel _p ⁿ ;p>2, contains an (1+∈)-isomorph ofl _p ^k . The main argument of the proof consists of a probabilistic selection which uses a lemma of Slepian. The same method also shows that any system of normalized functions inL _p ;p≥2, which is equivalent to the unit vector basis ofl _p ⁿ , contains, for any∈>0, a subsystem of sizeh proportional ton, which is (1+∈)-equivalent to the unit vector basis ofl _p ^h . The authors were supported by Grant No. 87-0079 from BSF.     

Equal values of trinomials revisited

A necessary and sufficient condition is given for an equation ax ^m + bx ⁿ + c = dy ^p + ey ^q to have infinitely many rational solutions with a bounded denominator, under the assumption that m > n > 0, p > q > 0, ab ≠ 0 ≠ de and either m > p > 2, or m = p > 2 and n ≥ q. In a previous paper there was an additional assumption (m, n) = (p, q) = 1.     

On the rigidity of super-Grassmannians

The rigidity of the complex super-Grassmannian Gr _m|n,k|l with 0<k<m, 0<l<n, supposing that (k, l) (1,n–1), (m–1, 1), (1,n–2), (m–2, 1), (2,n–1), (m–1, 2), is proved.Partially supported by Erwin Schrödinger International Institute for Mathematical Physics (Vienna, Austria)     

An application of ramsey’s theorem to groups with homogeneous theory

For any integers n >m ≥ 2, we say that a complete theory T is (m, n)-homogeneous if, for each model M of T, two n-tuples [abar],[bbar] in M have the same type if the corresponding m-tuples from [abar] and [bbar] have the same type. It was conjectured by H. Kikyo that, if M is an infinite group, with possibly additional structure, then the theory of M is not (m, n)-homogeneous. We prove a general result on structures with (m, n)-homogeneous theory which implies that, if M is a counterexample to this conjecture, then there exists an integer h such that each abelian subgroup of M has at most h elements. It follows that there exist an integer k such that M ^k = 1, and an integer l such that each finite subgroup of M has at most l elements.     

Graphs omitting sums of complete graphs

For every finite m and n there is a finite set {G₁, …, G_l} of countable (m · K_n)-free graphs such that every countable (m · K_n)-free graph occurs as an induced subgraph of one of the graphs G_l © 1997 John Wiley & Sons, Inc.     

Regularization by Free Additive Convolution, Square and Rectangular Cases

The free convolution \boxplus\boxplus is the binary operation on the set of probability measures on the real line which allows to deduce, from the individual spectral distributions, the spectral distribution of a sum of independent unitarily invariant square random matrices or of a sum of free operators in a non commutative probability space. In the same way, the rectangular free convolution \boxplus_l\boxplus_{\lambda} allows to deduce, from the individual singular distributions, the singular distribution of a sum of independent unitarily invariant rectangular random matrices. In this paper, we consider the regularization properties of these free convolutions on the whole real line. More specifically, we try to find continuous semigroups (μ_t) of probability measures such that μ₀ = δ₀ and such that for all t > 0 and all probability measure n, m_t\boxplusn\nu, \mu_t\boxplus\nu (or, in the rectangular context, m_t\boxplus_ln\mu_t\boxplus_{\lambda}\nu) is absolutely continuous with respect to the Lebesgue measure, with a positive analytic density on the whole real line. In the square case, for \boxplus\boxplus, we prove that in semigroups satisfying this property, no measure can have a finite second moment, and we give a sufficient condition on semigroups to satisfy this property, with examples. In the rectangular case, we prove that in most cases, for μ in a \boxplus_l\boxplus_{\lambda}-continuous semigroup, m\boxplus_ln\mu\boxplus_{\lambda}\nu either has an atom at the origin or doesn’t put any mass in a neighborhood of the origin, and thus the expected property does not hold. However, we give sufficient conditions for analyticity of the density of m\boxplus_ln\mu\boxplus_{\lambda}\nu except on a negligible set of points, as well as existence and continuity of a density everywhere.     

On the existence and nonexistence of global solutions for the porous medium equation with strongly nonlinear sources in a cone

In this paper, we study the initial-boundary value problem of the porous medium equation u _t  = Δu ^m  + V(x)u ^p in a cone D = (0, ∞) × Ω, where V(x) ~ (1 + |x|) ^σ . Let ω ₁ denote the smallest Dirichlet eigenvalue for the Laplace–Beltrami operator on Ω and let l denote the positive root of l ² + (n − 2)l = ω ₁. We prove that if m ≤ p ≤ m + (2 + σ)/(n + l), then the problem has no global nonnegative solutions for any nonnegative u ₀ unless u ₀ = 0; if p > m + (2 + σ)/n, then the problem has global solutions for some u ₀ ≥ 0.     

Binding number and minimum degree for k-factors

In this paper, we study mixed conditions on the binding number and the minimum degree of a graph G that guarantee the existence of a k-factor in G. Among others, we prove that a graph G of order n with δ(G) ? cn and bind(G) > (2 ? 3c)/(1 ? c), where c is any fixed number, has a 2-factor.     

Unique Maximum Matching Algorithms

We consider the problem of testing the uniqueness of maximum matchings, both in the unweighted and in the weighted case. For the unweighted case, we have two results. First, given a graph with n vertices and m edges, we can test whether the graph has a unique perfect matching, and find it if it exists, in O(m log⁴ n) time. This algorithm uses a recent dynamic connectivity algorithm and an old result of Kotzig characterizing unique perfect matchings in terms of bridges. For the special case of planar graphs, we improve the algorithm to run in O(n log n) time. Second, given one perfect matching, we can test for the existence of another in linear time. This algorithm is a modification of Edmonds' blossom-shrinking algorithm implemented using depth-first search. A generalization of Kotzig's theorem proved by Jackson and Whitty allows us to give a modification of the first algorithm that tests whether a given graph has a unique f-factor, and find it if it exists. We also show how to modify the second algorithm to check whether a given f-factor is unique. Both extensions have the same time bounds as their perfect matching counterparts. For the weighted case, we can test in linear time whether a maximum-weight matching is unique, given the output from Edmonds' algorithm for computing such a matching. The method is an extension of our algorithm for the unweighted case.     

Very tight embeddings of subspaces ofLp, 1 =p< 2, intolp n

We prove that for 1 p < r < 2, every n-dimensional subspace E of L _r, in particular l _r ⁿ , well-embeds into l _p ^m for some m (1 + $$\epsilon$$)n, where well depends on p, r, and the arbitrary $$\epsilon$$ > 0, but not on n.     

An improved algorithm for finding saddlepoints of two-person zero-sum games

It is well-known that one can sort (order)n real numbers in at mostF ₀(n) =nl – 2 ^l + 1 steps (comparisons), wherel = [log₂ n]. We snow how to find the strict saddlepoint or prove its absence in anm byn matrix,m n, in at mostF ₀(m)+F ₀(m+1)+n+m – 3 + (n–m) [log₂(m+1)] steps.     

Threshold Visual Cryptography Schemes with Specified Whiteness Levels of Reconstructed Pixels

In 1994, Naor and Shamir introduced an unconditionally secure method for encoding black and white images. This method, known as a threshold visual cryptography scheme (VCS), has the benefit of requiring no cryptographic computation on the part of the decoders. In a -VCS, a share, in the form of a transparency, is given to ">n users. Any ">k users can recover the secret simply by stacking transparencies, but ">k-1 users can gain no information about the secret whatsoever.In this paper, we first explore the issue of contrast, by demonstrating that the current definitions are inadequate, and by providing an alternative definition. This new definition motivates an examination of minimizing pixel expansion subject to fixing the VCS parameters ">h and ">l. New bounds on pixel expansion are introduced, and connections between these bounds are examined. The best bound presented is tighter than any previous bound. An analysis of connections between (2, ">n) schemes and designs such as BIBD's, PBD's, and (">r, )-designs is performed. Also, an integer linear program is provided whose solution exactly determines the minimum pixel expansion of a (2, ">n)-VCS with specified ">h and >l.