共查询到20条相似文献,搜索用时 15 毫秒
1.
Bla Bollobs Christian Borgs Jennifer T. Chayes Jeong Han Kim David B. Wilson 《Random Structures and Algorithms》2001,18(3):201-256
We consider the random 2‐satisfiability (2‐SAT) problem, in which each instance is a formula that is the conjunction of m clauses of the form x∨y, chosen uniformly at random from among all 2‐clauses on n Boolean variables and their negations. As m and n tend to infinity in the ratio m/n→α, the problem is known to have a phase transition at αc=1, below which the probability that the formula is satisfiable tends to one and above which it tends to zero. We determine the finite‐size scaling about this transition, namely the scaling of the maximal window W(n, δ)=(α?(n,δ), α+(n,δ)) such that the probability of satisfiability is greater than 1?δ for α<α? and is less than δ for α>α+. We show that W(n,δ)=(1?Θ(n?1/3), 1+Θ(n?1/3)), where the constants implicit in Θ depend on δ. We also determine the rates at which the probability of satisfiability approaches one and zero at the boundaries of the window. Namely, for m=(1+ε)n, where ε may depend on n as long as |ε| is sufficiently small and |ε|n1/3 is sufficiently large, we show that the probability of satisfiability decays like exp(?Θ(nε3)) above the window, and goes to one like 1?Θ(n?1|ε|?3 below the window. We prove these results by defining an order parameter for the transition and establishing its scaling behavior in n both inside and outside the window. Using this order parameter, we prove that the 2‐SAT phase transition is continuous with an order parameter critical exponent of 1. We also determine the values of two other critical exponents, showing that the exponents of 2‐SAT are identical to those of the random graph. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 201–256 2001 相似文献
2.
考虑一类一阶常微分方程的周期边值问题,利用Schaefer不动点定理得到了边值问题解存在的一个充分条件,推广了相关文献中已有的结果. 相似文献
3.
4.
We consider 2‐factorizations of complete graphs that possess an automorphism group fixing k?0 vertices and acting sharply transitively on the others. We study the structures of such factorizations and consider the cases in which the group is either abelian or dihedral in some more details. Combining results of the first part of the paper with a result of D. Bryant, J Combin Des, 12 (2004), 147–155, we prove that the class of 2‐factorizations of complete graphs is universal. Namely each finite group is the full automorphism group of a 2‐factorization of the class. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 211‐228, 2009 相似文献
5.
Consider the Bayes problem in which one has to discriminate if the random unknown initial state of a stochastic process is distributed according to either of two preassigned distributions, on the base of the observation of the first‐passage time of the process through 0. For processes whose first‐passage times to state 0 are increasing in the initial state according to the likelihood ratio order, such problem is solved by determining the Bayes decision function and the corresponding Bayes error. The special case of fixed initial values including a family of first‐passage times with proportional reversed hazard functions is then studied. Finally, various applications to birth‐and‐death and to diffusion processes are discussed. Copyright © 2001 John Wiley & Sons, Ltd. 相似文献
6.
本文研究了下列一阶拟线性偏微分方程的广义Cauchy问题:ut+λ(u)ux=0,u|Γ=φ(x),Γ:x=r(σ),t=s(σ).证明了该问题在一定条件下,于上半平面Ω={-∞<x<+∞,t≥0}上存在整体光滑解. 相似文献
7.
Given two 2‐regular graphs F1 and F2, both of order n, the Hamilton‐Waterloo Problem for F1 and F2 asks for a factorization of the complete graph into α1 copies of F1, α2 copies of F2, and a 1‐factor if n is even, for all nonnegative integers α1 and α2 satisfying . We settle the Hamilton‐Waterloo Problem for all bipartite 2‐regular graphs F1 and F2 where F1 can be obtained from F2 by replacing each cycle with a bipartite 2‐regular graph of the same order. 相似文献
8.
We prove that , the complete graph of even order with a 1‐factor duplicated, admits a decomposition into 2‐factors, each a disjoint union of cycles of length if and only if , except possibly when is odd and . In addition, we show that admits a decomposition into 2‐factors, each a disjoint union of cycles of lengths , whenever are all even. 相似文献
9.
In this paper, we study the forward and the backward in time problems for a class of nonlinear diffusion equations with respect to the pseudo‐differential operator. Herein, we investigate the stability of the solution of the forward problem in relationship with parameters of the pseudo‐differential operator and initial data. Besides, as known, the backward in time problem is instability. Hence, we give a method to regularize the solution of the backward problem in the case of the parameters are perturbed. 相似文献
10.
Polychromatic colorings of complete graphs with respect to 1‐, 2‐factors and Hamiltonian cycles 下载免费PDF全文
《Journal of Graph Theory》2018,87(4):660-671
If G is a graph and is a set of subgraphs of G, then an edge‐coloring of G is called ‐polychromatic if every graph from gets all colors present in G. The ‐polychromatic number of G, denoted , is the largest number of colors such that G has an ‐polychromatic coloring. In this article, is determined exactly when G is a complete graph and is the family of all 1‐factors. In addition is found up to an additive constant term when G is a complete graph and is the family of all 2‐factors, or the family of all Hamiltonian cycles. 相似文献
11.
Tommaso Traetta 《组合设计杂志》2010,18(4):237-247
It is known that a necessary condition for the existence of a 1‐rotational 2‐factorization of the complete graph K2n+1 under the action of a group G of order 2n is that the involutions of G are pairwise conjugate. Is this condition also sufficient? The complete answer is still unknown. Adapting the composition technique shown in Buratti and Rinaldi, J Combin Des, 16 (2008), 87–100, we give a positive answer for new classes of groups; for example, the groups G whose involutions lie in the same conjugacy class and having a normal subgroup whose order is the greatest odd divisor of |G|. In particular, every group of order 4t+2 gives a positive answer. Finally, we show that such a composition technique provides 2‐factorizations with a rich group of automorphisms. © 2009 Wiley Periodicals, Inc. J Combin Designs 18: 237–247, 2010 相似文献
12.
13.
《Mathematische Nachrichten》2017,290(2-3):236-247
In this paper we prove an existence result for the following singular elliptic system where Ω is a bounded open set in (), is the p‐laplacian operator, and are suitable Lebesgue functions and , , are positive parameters satisfying suitable assumptions. 相似文献
14.
The k‐out‐of‐n structure is a very popular type of redundancy in fault‐tolerant systems, it has founded wide applications in industrial and military systems during the past several decades. This paper will investigate the residual life length of a k‐out‐of‐n system with independent (not necessarily identical) components, given that the (n?k)th failure has occurred at time t?0. Behaviour of PF2, IFR, DRHR, DMRL, NBU(2) and NBUC classes of life distributions are derived in terms of the monotonicity of the residual life given the time of the (n?k)th failure. Copyright © 2004 John Wiley & Sons, Ltd. 相似文献
15.
We consider k‐factorizations of the complete graph that are 1‐rotational under an assigned group G, namely that admit G as an automorphism group acting sharply transitively on all but one vertex. After proving that the k‐factors of such a factorization are pairwise isomorphic, we focus our attention to the special case of k = 2, a case in which we prove that the involutions of G necessarily form a unique conjugacy class. We completely characterize, in particular, the 2‐factorizations that are 1‐rotational under a dihedral group. Finally, we get infinite new classes of previously unknown solutions to the Oberwolfach problem via some direct and recursive constructions. © 2007 Wiley Periodicals, Inc. J Combin Designs 16: 87–100, 2008 相似文献
16.
It is shown that if F1, F2, …, Ft are bipartite 2‐regular graphs of order n and α1, α2, …, αt are positive integers such that α1 + α2 + ? + αt = (n ? 2)/2, α1≥3 is odd, and αi is even for i = 2, 3, …, t, then there exists a 2‐factorization of Kn ? I in which there are exactly αi 2‐factors isomorphic to Fi for i = 1, 2, …, t. This result completes the solution of the Oberwolfach problem for bipartite 2‐factors. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:22‐37, 2011 相似文献
17.
Michael J. O'Hara 《Numerical Linear Algebra with Applications》2014,21(1):1-12
The problem of symmetric rank‐one approximation of symmetric tensors is important in independent components analysis, also known as blind source separation, as well as polynomial optimization. We derive several perturbative results that are relevant to the well‐posedness of recovering rank‐one structure from approximately‐rank‐one symmetric tensors. We also specialize the analysis of the shifted symmetric higher‐order power method, an algorithm for computing symmetric tensor eigenvectors, to approximately‐rank‐one symmetric tensors. Copyright © 2012 John Wiley & Sons, Ltd. 相似文献
18.
In this article, we propose a tailored finite point method (TFPM) for the numerical solution of a type of fourth‐order singular perturbation problem in two dimensions based on the equation decomposition technique. Our finite point method has been tailored based on the local exponential basis functions. Furthermore, our TFPM satisfies the discrete maximum principle automatically. Our numerical examples show that our method has second order convergence rate in energy norm as $\varepsilon\to0$ . © 2011 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2011 相似文献
19.
Igor I. Skrypnik 《Mathematische Nachrichten》2011,284(16):2101-2122
We investigate the continuity of solutions for general nonlinear parabolic equations with non‐standard growth near a nonsmooth boundary of a cylindrical domain. We prove a sufficient condition for regularity of a boundary point. 相似文献
20.
The paper presents existence results for positive solutions of the differential equations x ″ + μh (x) = 0 and x ″ + μf (t, x) = 0 satisfying the Dirichlet boundary conditions. Here μ is a positive parameter and h and f are singular functions of non‐positone type. Examples are given to illustrate the main results. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim) 相似文献