The Cℓ‐free process

The ‐free process starts with the empty graph on n vertices and adds edges chosen uniformly at random, one at a time, subject to the condition that no copy of is created. For every we show that, with high probability as , the maximum degree is , which confirms a conjecture of Bohman and Keevash and improves on bounds of Osthus and Taraz. Combined with previous results this implies that the ‐free process typically terminates with edges, which answers a question of Erd?s, Suen and Winkler. This is the first result that determines the final number of edges of the more general H‐free process for a non‐trivial class of graphs H. We also verify a conjecture of Osthus and Taraz concerning the average degree, and obtain a new lower bound on the independence number. Our proof combines the differential equation method with a tool that might be of independent interest: we establish a rigorous way to ‘transfer’ certain decreasing properties from the binomial random graph to the H‐free process. © 2014 Wiley Periodicals, Inc. Random Struct. Alg. 44, 490–526, 2014     

Triangle‐free subgraphs in the triangle‐free process

Consider the triangle‐free process, which is defined as follows. Start with G(0), an empty graph on n vertices. Given G(i ‐ 1), let G(i) = G(i ‐ 1) ∪{g(i)}, where g(i) is an edge that is chosen uniformly at random from the set of edges that are not in G(i ? 1) and can be added to G(i ‐ 1) without creating a triangle. The process ends once a maximal triangle‐free graph has been created. Let H be a fixed triangle‐free graph and let X_H(i) count the number of copies of H in G(i). We give an asymptotically sharp estimate for ??(X_H(i)), for every \begin{align*}1 \ll i \le 2^{-5} n^{3/2} \sqrt{\ln n}\end{align*}, at the limit as n →∞. Moreover, we provide conditions that guarantee that a.a.s. X_H(i) = 0, and that X_H(i) is concentrated around its mean.© 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

The Bohman‐Frieze process near criticality

The Erd?s‐Rényi process begins with an empty graph on n vertices, with edges added randomly one at a time to the graph. A classical result of Erd?s and Rényi states that the Erd?s‐Rényi process undergoes a phase transition, which takes place when the number of edges reaches n/2 (we say at time 1) and a giant component emerges. Since this seminal work of Erd?s and Rényi, various random graph models have been introduced and studied. In this paper we study the Bohman‐Frieze process, a simple modification of the Erd?s‐Rényi process. The Bohman‐Frieze process also begins with an empty graph on n vertices. At each step two random edges are presented, and if the first edge would join two isolated vertices, it is added to a graph; otherwise the second edge is added. We present several new results on the phase transition of the Bohman‐Frieze process. We show that it has a qualitatively similar phase transition to the Erd?s‐Rényi process in terms of the size and structure of the components near the critical point. We prove that all components at time t_c ? ? (that is, when the number of edges are (t_c ? ?)n/2) are trees or unicyclic components and that the largest component is of size Ω(?^‐2log n). Further, at t_c + ?, all components apart from the giant component are trees or unicyclic and the size of the second‐largest component is Θ(?^‐2log n). Each of these results corresponds to an analogous well‐known result for the Erd?s‐Rényi process. Our proof techniques include combinatorial arguments, the differential equation method for random processes, and the singularity analysis of the moment generating function for the susceptibility, which satisfies a quasi‐linear partial differential equation. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

List coloring triangle‐free hypergraphs

A triangle in a hypergraph is a collection of distinct vertices u, v, w and distinct edges e, f, g with , and . Johansson [Tech. report (1996)] proved that every triangle‐free graph with maximum degree Δ has list chromatic number . Frieze and Mubayi (Electron J Comb 15 (2008), 27) proved that every linear (meaning that every two edges share at most one vertex) triangle‐free triple system with maximum degree Δ has chromatic number . The restriction to linear triple systems was crucial to their proof. We provide a common generalization of both these results for rank 3 hypergraphs (edges have size 2 or 3). Our result removes the linear restriction from 8 , while reducing to the (best possible) result [Johansson, Tech. report (1996)] for graphs. In addition, our result provides a positive answer to a restricted version of a question of Ajtai Erd?s, Komlós, and Szemerédi (combinatorica 1 (1981), 313–317) concerning sparse 3‐uniform hypergraphs. As an application, we prove that if is the collection of 3‐uniform triangles, then the Ramsey number satisfies for some positive constants a and b. The upper bound makes progress towards the recent conjecture of Kostochka, Mubayi, and Verstraëte (J Comb Theory Ser A 120 (2013), 1491–1507) that where C₃ is the linear triangle. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 487–519, 2015     

The degree sequences and spectra of scale‐free random graphs

We investigate the degree sequences of scale‐free random graphs. We obtain a formula for the limiting proportion of vertices with degree d, confirming non‐rigorous arguments of Dorogovtsev, Mendes, and Samukhin ( 14 ). We also consider a generalization of the model with more randomization, proving similar results. Finally, we use our results on the degree sequence to show that for certain values of parameters localized eigenfunctions of the adjacency matrix can be found. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Levels of a scale‐free tree

Consider the random graph model of Barabási and Albert, where we add a new vertex in every step and connect it to some old vertices with probabilities proportional to their degrees. If we connect it to only one of the old vertices the graph will be a tree. These graphs have been shown to have power law degree distributions, the same as observed in some large real‐world networks. We show that the degree distribution is the same on every sufficiently high level of the tree. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

A greedy algorithm for finding a large 2‐matching on a random cubic graph

A 2‐matching of a graph G is a spanning subgraph with maximum degree two. The size of a 2‐matching U is the number of edges in U and this is at least where n is the number of vertices of G and κ denotes the number of components. In this article, we analyze the performance of a greedy algorithm 2greedy for finding a large 2‐matching on a random 3‐regular graph. We prove that with high probability, the algorithm outputs a 2‐matching U with .     

H1‐Galerkin expanded mixed finite element methods for nonlinear pseudo‐parabolic integro‐differential equations

H¹‐Galerkin mixed finite element method combined with expanded mixed element method is discussed for nonlinear pseudo‐parabolic integro‐differential equations. We conduct theoretical analysis to study the existence and uniqueness of numerical solutions to the discrete scheme. A priori error estimates are derived for the unknown function, gradient function, and flux. Numerical example is presented to illustrate the effectiveness of the proposed scheme. © 2012 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2013     

The element‐free Galerkin method for a quasistatic contact problem with the Tresca friction in elastic materials

This paper is proposed for the error estimates of the element‐free Galerkin method for a quasistatic contact problem with the Tresca friction. The penalty method is used to impose the clamped boundary conditions. The duality algorithm is also given to deal with the non‐differentiable term in the quasistatic contact problem with the Tresca friction. The error estimates indicate that the convergence order is dependent on the nodal spacing, the time step, the largest degree of basis functions in the moving least‐squares approximation, and the penalty factor. Numerical examples demonstrate the effectiveness of the element‐free Galerkin method and verify the theoretical analysis.     

P‐moment stability under small Gauss type random excitation of stochastic system

In this paper, the stochastic stability under small Gauss type random excitation is investigated theoretically and numerically. When p is larger than 0, the p‐moment stability theorem of stochastic models is proved by Lyapunov method, Ito isometry formula, matrix theory and so on. Then the application of p‐moment such as k‐order moment of the origin and k‐order moment of the center is introduced and analyzed. Finally, p‐moment stability of the power system is verified through the simulation example of a one machine and infinite bus system. Copyright © 2016 John Wiley & Sons, Ltd.     

Clique‐coloring some classes of odd‐hole‐free graphs

We consider the problem of clique‐coloring, that is coloring the vertices of a given graph such that no maximal clique of size at least 2 is monocolored. Whereas we do not know any odd‐hole‐free graph that is not 3‐clique‐colorable, the existence of a constant C such that any perfect graph is C‐clique‐colorable is an open problem. In this paper we solve this problem for some subclasses of odd‐hole‐free graphs: those that are diamond‐free and those that are bull‐free. We also prove the NP‐completeness of 2‐clique‐coloring K₄‐free perfect graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 233–249, 2006     

Scale‐free graphs of increasing degree

We study a scale‐free random graph process in which the number of edges added at each step increases. This differs from the standard model in which a fixed number, m, of edges are added at each step. Let f(t) be the number of edges added at step t. In the standard scale‐free model, f(t) = m constant, whereas in this paper we consider f(t) = [t^c],c > 0. Such a graph process, in which the number of edges grows non‐linearly with the number of vertices is said to have accelerating growth. We analyze both an undirected and a directed process. The power law of the degree sequence of these processes exhibits widely differing behavior. For the undirected process, the terminal vertex of each edge is chosen by preferential attachment based on vertex degree. When f(t) = m constant, this is the standard scale‐free model, and the power law of the degree sequence is 3. When f(t) = [t^c],c < 1, the degree sequence of the process exhibits a power law with parameter x = (3 ? c)/(1 ? c). As c → 0, x → 3, which gives a value of x = 3, as in standard scale‐free model. Thus no more slowly growing monotone function f(t) alters the power law of this model away from x = 3. When c = 1, so that f(t) = t, the expected degree of all vertices is t, the vertex degree is concentrated, and the degree sequence does not have a power law. For the directed process, the terminal vertex is chosen proportional to in‐degree plus an additive constant, to allow the selection of vertices of in‐degree zero. For this process when f(t) = m is constant, the power law of the degree sequence is x = 2 + 1/m. When f(t) = [t^c], c > 0, the power law becomes x = 1 + 1/(1 + c), which naturally extends the power law to [1,2]. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 38, 396–421, 2011     

Exhaustive generation of k‐critical ‐free graphs

We describe an algorithm for generating all k‐critical ‐free graphs, based on a method of Hoàng et al. (A graph G is k‐critical H‐free if G is H‐free, k‐chromatic, and every H‐free proper subgraph of G is ‐colorable). Using this algorithm, we prove that there are only finitely many 4‐critical ‐free graphs, for both and . We also show that there are only finitely many 4‐critical ‐free graphs. For each of these cases we also give the complete lists of critical graphs and vertex‐critical graphs. These results generalize previous work by Hell and Huang, and yield certifying algorithms for the 3‐colorability problem in the respective classes. In addition, we prove a number of characterizations for 4‐critical H‐free graphs when H is disconnected. Moreover, we prove that for every t, the class of 4‐critical planar ‐free graphs is finite. We also determine all 52 4‐critical planar P₇‐free graphs. We also prove that every P₁₁‐free graph of girth at least five is 3‐colorable, and show that this is best possible by determining the smallest 4‐chromatic P₁₂‐free graph of girth at least five. Moreover, we show that every P₁₄‐free graph of girth at least six and every P₁₇‐free graph of girth at least seven is 3‐colorable. This strengthens results of Golovach et al.     

Claw‐free circular‐perfect graphs

The circular chromatic number of a graph is a well‐studied refinement of the chromatic number. Circular‐perfect graphs form a superclass of perfect graphs defined by means of this more general coloring concept. This article studies claw‐free circular‐perfect graphs. First, we prove that if G is a connected claw‐free circular‐perfect graph with χ(G)>ω(G), then min{α(G), ω(G)}=2. We use this result to design a polynomial time algorithm that computes the circular chromatic number of claw‐free circular‐perfect graphs. A consequence of the strong perfect graph theorem is that minimal imperfect graphs G have min{α(G), ω(G)}=2. In contrast to this result, it is shown in Z. Pan and X. Zhu [European J Combin 29(4) (2008), 1055–1063] that minimal circular‐imperfect graphs G can have arbitrarily large independence number and arbitrarily large clique number. In this article, we prove that claw‐free minimal circular‐imperfect graphs G have min{α(G), ω(G)}≤3. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 163–172, 2010     

Diameter in ultra‐small scale‐free random graphs

It is well known that many random graphs with infinite variance degrees are ultra‐small. More precisely, for configuration models and preferential attachment models where the proportion of vertices of degree at least k is approximately k^{?(τ ? 1)} with τ ∈ (2,3), typical distances between pairs of vertices in a graph of size n are asymptotic to and , respectively. In this paper, we investigate the behavior of the diameter in such models. We show that the diameter is of order precisely when the minimal forward degree d_fwd of vertices is at least 2. We identify the exact constant, which equals that of the typical distances plus . Interestingly, the proof for both models follows identical steps, even though the models are quite different in nature.     

Complexity of clique‐coloring odd‐hole‐free graphs

In this paper we investigate the problem of clique‐coloring, which consists in coloring the vertices of a graph in such a way that no monochromatic maximal clique appears, and we focus on odd‐hole‐free graphs. On the one hand we do not know any odd‐hole‐free graph that is not 3‐clique‐colorable, but on the other hand it is NP‐hard to decide if they are 2‐clique‐colorable, and we do not know if there exists any bound k₀ such that they are all k₀ ‐clique‐colorable. First we will prove that (odd hole, codiamond)‐free graphs are 2‐clique‐colorable. Then we will demonstrate that the complexity of 2‐clique‐coloring odd‐hole‐free graphs is actually Σ₂ P‐complete. Finally we will study the complexity of deciding whether or not a graph and all its subgraphs are 2‐clique‐colorable. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 139–156, 2009     

Forward-backward stochastic differential equations with Brownian motion and poisson process

1.IntroductionLet(n,Y,{S}tZo,P)beastochasticbasissuchthatAscontainsallp-nullelementsofFand5 =nR .=h,t2o.Wesupposethatthefiltration{R}tZoisgeneratede>0bythefollowingtwOmutuallyindependentProcesses:(i)Ad-dbonsionalstandardBroedanmotion{Bt}tZo;(h)APoissonrandommeasureNonR xZ,whereZCFIisanonemptyopensetequippedwithitsBorelheldB(Z),withcompensatorN(dz,dt)=A(dz)dt,suchthatN(Ax[0,t])=(N--N)(Ax10,t])tZoisamartingaleforallAEB(Z)satisfyingA(A)相似文献   

Claw‐free 3‐connected P11‐free graphs are hamiltonian

We show that every 3‐connected claw‐free graph which contains no induced copy of P₁₁ is hamiltonian. Since there exist non‐hamiltonian 3‐connected claw‐free graphs without induced copies of P₁₂ this result is, in a way, best possible. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 111–121, 2004     

A new Taylor collocation method for nonlinear Fredholm‐Volterra integro‐differential equations

The aim of this article is to present an efficient numerical procedure for solving nonlinear integro‐differential equations. Our method depends mainly on a Taylor expansion approach. This method transforms the integro‐differential equation and the given conditions into the matrix equation which corresponds to a system of nonlinear algebraic equations with unkown Taylor coefficients. The reliability and efficiency of the proposed scheme are demonstrated by some numerical experiments and performed on the computer program written in Maple10. © 2009 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2010     

Finite element approximations to one‐phase nonlinear free boundary problem in groundwater contamination flow

In this article, we consider a single‐phase coupled nonlinear Stefan problem of the water‐head and concentration equations with nonlinear source and permeance terms and a Dirichlet boundary condition depending on the free‐boundary function. The problem is very important in subsurface contaminant transport and remediation, seawater intrusion and control, and many other applications. While a Landau type transformation is introduced to immobilize the free boundary, a transformation for the water‐head and concentration functions is defined to deal with the nonhomogeneous Dirichlet boundary condition, which depends on the free boundary function. An H¹‐finite element method for the problem is then proposed and analyzed. The existence of the approximation solution is established, and error estimates are obtained for both the semi‐discrete schemes and the fully discrete schemes. © 2006 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2006