图的彩虹连通数与最小度和

令G是一个阶为n且最小度为δ的连通图. 当δ很小而n很大时, 现有的依据于最小度参数的彩虹边连通数和彩虹点连通数的上界都很大, 它们是n的线性函数. 本文中, 我们用另一种参数,即k个独立点的最小度和σ_k来代替δ, 从而在很大程度上改进了彩虹边连通数和彩虹点连通数的上界. 本文证明了如果G有k个独立点, 那么rc(GG)≤3kn/(σk+k)+6k-3. 同时也证明了下面的结果, 如果σ_k≤7k或σ_k≥8k, 那么rvc(G)≤(4k+2k²)n/(σ_k+k)+5k; 如果7k<σ_k<8k, 那么rvc(G)≤(38k/9+2k²)n/(σ_k+k)+5k.文中也给出了例子说明我们的界比现有的界更好, 即我们的界为rc(G)≤9k-3和rvc(G)≤9k+2k²或rvc(G)≤83k/9+2k², 这意味着当δ很小而σ_k很大时, 我们的界是一个常数, 而现有的界却是n的线性函数.     

Class of tight bounds on the Q‐function with closed‐form upper bound on relative error

In this paper, we propose a novel class of parametric bounds on the Q‐function, which are lower bounds for 1 ≤ a < 3 and x > x_t = (a (a‐1) / (3‐a))^1/2, and upper bound for a = 3. We prove that the lower and upper bounds on the Q‐function can have the same analytical form that is asymptotically equal, which is a unique feature of our class of tight bounds. For the novel class of bounds and for each particular bound from this class, we derive the beneficial closed‐form expression for the upper bound on the relative error. By comparing the bound tightness for moderate and large argument values not only numerically, but also analytically, we demonstrate that our bounds are tighter compared with the previously reported bounds of similar analytical form complexity.     

Code constructions and existence bounds for relative generalized Hamming weight

The relative generalized Hamming weight (RGHW) of a linear code C and a subcode C ¹ is an extension of generalized Hamming weight. The concept was firstly used to protect messages from an adversary in the wiretap channel of type II with illegitimate parties. It was also applied to the wiretap network II for secrecy control of network coding and to trellis-based decoding algorithms for complexity estimation. For RGHW, bounds and code constructions are two related issues. Upper bounds on RGHW show the possible optimality for the applications, and code constructions meeting upper bounds are for designing optimal schemes. In this article, we show indirect and direct code constructions for known upper bounds on RGHW. When upper bounds are not tight or constructions are hard to find, we provide two asymptotically equivalent existence bounds about good code pairs for designing suboptimal schemes. Particularly, most code pairs (C, C ¹) are good when the length n of C is sufficiently large, the dimension k of C is proportional to n and other parameters are fixed. Moreover, the first existence bound yields an implicit lower bound on RGHW, and the asymptotic form of this existence bound generalizes the usual asymptotic Gilbert–Varshamov bound.     

On the number of rational points on a strictly convex curve

Let γ be a bounded convex curve on the plane. Then #(γ ∩ (?/n)²) = o(n ^2/3). This strengthens the classical result due to Jarník [J] (the upper bound cn ^2/3) and disproves the conjecture on the existence of a so-called universal Jarník curve.     

On the complexity of growth of the number of distinct fuzzy switching functions

Several attempts have been made to enumerate fuzzy switching (FSF's) and to develop upper and lower bounds for the number of FSF's of n variables in an effort to better understand the properties and the complexity of FSF's. Previous upper bounds are 2⁴ⁿ [9] and 2^{2–3n—2n—1} [7].It has also been shown that the exact numbers of FSF's of n variables for n = 0, 1, 2, 3, and 4 are 2, 6, 8, 84, 43 918 and 160 297 985 276 respectively.This paper will give a brief overview of previous approaches to the problem, study some of the properties of fuzzy switching functions and give improved upper and lower bounds for a general n.     

Uniform approximation of Poisson integrals of functions from the class H ω by de la Vallée Poussin sums

We obtain asymptotic equalities for least upper bounds of deviations in the uniform metric of de la Vallée Poussin sums on the sets C _?? ^q H _?? of Poisson integrals of functions from the class H _?? generated by convex upwards moduli of continuity ??(t) which satisfy the condition ??(t)/t ?? ?? as t ?? 0. As an implication, a solution of the Kolmogorov-Nikol??skii problem for de la Vallée Poussin sums on the sets of Poisson integrals of functions belonging to Lipschitz classes H ^??, 0 < ?? < 1, is obtained.     

New coverings of t-sets with (t + 1)-sets

The minimum number of k-subsets out of a v-set such that each t-set is contained in at least one k-set is denoted by C(v, k, t). In this article, a computer search for finding good such covering designs, leading to new upper bounds on C(v, k, t), is considered. The search is facilitated by predetermining automorphisms of desired covering designs. A stochastic heuristic search (embedded in the general framework of tabu search) is then used to find appropriate sets of orbits. A table of upper bounds on C(v, t + 1, t) for v 28 and t 8 is given, and the new covering designs are listed. © 1999 John Wiley & Sons, Inc. J. Combin Designs 7: 217–226, 1999     

On the total domination number of cross products of graphs

We give lower and upper bounds on the total domination number of the cross product of two graphs, γ_t(G×H). These bounds are in terms of the total domination number and the maximum degree of the factors and are best possible. We further investigate cross products involving paths and cycles. We determine the exact values of γ_t(G×Pn) and γ_t(C_n×C_m) where P_n and C_n denote, respectively, a path and a cycle of length n.     

Heat kernel bounds and desingularizing weights

We study the parabolic operator ∂_t−Δ_x+V(t,x), in d?1, with a potential V=V+−V−,V±?0 assumed to be from a parabolic Kato class, and obtain two-sided Gaussian bounds on the associated heat kernel. The constraints on the Kato norms of V⁺ and V⁻ are completely asymmetric, as they should be. Further improvements to our heat kernel bounds are obtained in the case of time-independent potentials.If V has singularities of the type ±c|x|⁻² with a suitably small constant c, we obtain new lower and (sharp) upper weighted heat kernel bounds. The rate of growth of the weights depends (explicitly) on the constant c. The standard bounds and methods (estimates in L^p-spaces without desingularizing weights) fail for singular potentials.     

Positive solution of singular Dirichlet boundary value problems for second order differential equation system

This paper investigates the existence of positive solutions of singular Dirichlet boundary value problems for second order differential system. A necessary and sufficient condition for the existence of C[0,1]×C[0,1] positive solutions as well as C¹[0,1]×C¹[0,1] positive solutions is given by means of the method of lower and upper solutions and the fixed point theorems. Our nonlinearity fi(t,x₁,x₂) may be singular at x₁=0, x₂=0, t=0 and/or t=1, i=1,2.     

Asymptotic analysis on the normalized <Emphasis Type="Italic">k</Emphasis>-error linear complexity of binary sequences

Linear complexity and k-error linear complexity are the important measures for sequences in stream ciphers. This paper discusses the asymptotic behavior of the normalized k-error linear complexity \({L_{n,k}(\underline{s})/n}\) of random binary sequences \({\underline{s}}\) , which is based on one of Niederreiter’s open problems. For k = n θ, where 0 ≤ θ ≤ 1/2 is a fixed ratio, the lower and upper bounds on accumulation points of \({L_{n,k}(\underline{s})/n}\) are derived, which holds with probability 1. On the other hand, for any fixed k it is shown that \({\lim_{n\rightarrow\infty} L_{n,k}(\underline{s})/n = 1/2}\) holds with probability 1. The asymptotic bounds on the expected value of normalized k-error linear complexity of binary sequences are also presented.     

Asymptotics of the porous media equation via Sobolev inequalities

Let M be a compact Riemannian manifold without boundary. Consider the porous media equation , u(0)=u₀∈L^q, ? being the Laplace-Beltrami operator. Then, if q?2∨(m-1), the associated evolution is L^q-L^∞ regularizing at any time t>0 and the bound ‖u(t)‖_∞?C(u₀)/t^β holds for t<1 for suitable explicit C(u₀),γ. For large t it is shown that, for general initial data, u(t) approaches its time-independent mean with quantitative bounds on the rate of convergence. Similar bounds are valid when the manifold is not compact, but u(t) approaches u≡0 with different asymptotics. The case of manifolds with boundary and homogeneous Dirichlet, or Neumann, boundary conditions, is treated as well. The proof stems from a new connection between logarithmic Sobolev inequalities and the contractivity properties of the nonlinear evolutions considered, and is therefore applicable to a more abstract setting.     

On maximal (k,t)-sets

Summary This investigation was originally motivated by the problem of determining the maximum number of points in finiten-dimensional projective spacePG(n, s) based on the Galois fieldGF(s) of orders=p ^h (wherep andh are positive integers andp is the prime characteristic of the field), such that not of these chosen points are linearly dependent. A set ofk distinct points inPG(n, s), not linearly dependent, is called a (k, t)-set fork ₁ >k. The maximum value ofk is denoted bym _t (n+1, s). The purpose of this paper is to find new upper bounds for some values ofn, s andt. These bounds are of importance in the experimental design and information theory problems.     

On tree census and the giant component in sparse random graphs

For each of the two models of a sparse random graph on n vertices, G(n, # of edges = cn/2) and G(n, Prob (edge) = c/n) define t_n(k) as the total number of tree components of size k (1 ≤ k ≤ n). the random sequence {[t_n(k) - nh(k)]n^?1/2} is shown to be Gaussian in the limit n →∞, with h(k) = k^k?2c^k?1e^?kc/k! and covariance function being dependent upon the model. This general result implies, in particular, that, for c> 1, the size of the giant component is asymptotically Gaussian, with mean nθ(c) and variance n(1 ? T)^?2(1 ? 2Tθ)θ(1 ? θ) for the first model and n(1 ? T)^?2θ(1 ? θ) for the second model. Here Te^?T = ce^?c, T<1, and θ = 1 ? T/c. A close technique allows us to prove that, for c < 1, the independence number of G(n, p = c/n) is asymptotically Gaussian with mean nc^?1(β + β²/2) and variance n[c^?1(β + β²/2) ?c^?2(c + 1)β²], where βe^β = c. It is also proven that almost surely the giant component consists of a giant two-connected core of size about n(1 ? T)β and a “mantle” of trees, and possibly few small unicyclic graphs, each sprouting from its own vertex of the core.     

Analysis of the heat kernel of the Dirichlet-to-Neumann operator

We prove Poisson upper bounds for the kernel _(Kt)t>0${(K_t)}_{t>0}$ of the semigroup generated by the Dirichlet-to-Neumann operator if the underlying domain is bounded and has a C^∞$C^{\infty }$-boundary. We also prove Poisson bounds for _Kz$K_z$ for all z in the right half-plane and for all its derivatives.     

Investigation of solvability of the multidimensional two-phase Stefan and the nonstationary filtration Florin problems for second order parabolic equations in weighted Hölder spaces of functions

Multidimensional two-phase Stefan (k=1) and nonstationary filtration Florin (k=0) problems for second order parabolic equations in the case when the free boundary is a graph of a functionx _n =Ψ _k (x′t),x′∈ ^n?1 ,n≥2,t∈(0,T) are studied. A unique solvability theorem in weighted Hölder spaces of functions with time power weight is proved, coercive estimates for solutions are obtained. Bibliography: 30 titles.     

Families of finite sets in which no set is covered by the union of two others

Let f^k(n) denote the maximum of k-subsets of an n-set satisfying the condition in the title. It is proven that f^{2t ? 1}(n) ? f^2t(n + 1) ? $\text{(}{}_{\mathrm{t}}{}^{\mathrm{n}}\text{)}\text{(}{}_{\mathrm{t}}{}^{\mathrm{2t?1}}\text{)}$ with equalities holding iff there exists a Steiner-system S(t, 2t ? 1, n). The bounds are approximately best possile for k ? 6 and of correct order of magnitude for k >/ 7, as well, even if the corresponding Steiner-systems do not exist.Exponential lower and upper bounds are obtained for the case if we do not put size restrictions on the members of the family (i.e., the nonuniform case).     

Subgraphs of a hypercube containing no small even cycles

We investigate several Ramsey-Turán type problems for subgraphs of a hypercube. We obtain upper and lower bounds for the maximum number of edges in a subgraph of a hypercube containing no four-cycles or more generally, no 2k-cycles C_2k. These extermal results imply, for example, the following Ramsey theorems for hypercubes: A hypercube can always be edge-partitioned into four subgraphs, each of which contains no six-cycle. However, for any integer t, if the n-cube is edge-partitioned into t sub-graphs, then one of the subgraphs must contain an edight-cycle, provided only than n is sufficiently large (depending only on t).     

Star discrepancy estimates for digital (t, m, 2)-nets and digital (t, 2) -sequences over Z2

Summary We prove upper bounds on the star discrepancy of digital (t, m, 2)-nets and (t, 2)-sequences over Z₂. The main tool is a decomposition lemma for digital (t, m, 2)-nets, which states that every digital (t, m, 2)-net is just the union of 2^tdigitally shifted digital (0, m - t, 2)-nets. Using this result we generalize upper bounds on the star discrepancy of digital (0, m, 2) -nets and (0, 2) -sequences.