A characterization of P4‐indifference graphs

A graph is a P₄‐indifference graph if it admits a linear ordering ≺ on its vertices such that every chordless path with vertices a, b, c, d and edges ab, bc, cd has either a ≺ b ≺ c ≺ d or d ≺ c ≺ b ≺ a. P₄‐indifference graphs generalize indifference graphs and are perfectly orderable. We give a characterization of P₄‐indifference graphs by forbidden induced subgraphs. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 155‐162, 1999     

Co‐existence of Poisson and non‐Poisson processes in ordered parallel multilane pedestrian traffic

We show that non‐Poisson and Poisson processes can coexist in ordered parallel multilane pedestrian traffic, in the presence of lane switching which asymmetrically benefits the switchers and nonswitchers. Pedestrians join at the tail end of a queue and transact at the opposite front end. Their aim is to complete a transaction within the shortest possible time, and they can transfer to a shorter queue with probability p_s. Traffic is described by the utilization parameter U = λ〈t_s〉/N, where λ is the average rate of pedestrians entering the system, 〈t_s〉 is the average transaction time, and N is the number of lanes. Using an agent‐based model, we investigate the dependence of the average completion time 〈t_c〉 with variable K = 1 + (1 ? U)^?1 for different N and 〈t_s〉 values. In the absence of switching (p_s = 0), we found that 〈t_c〉 ∝ K^τ, where τ ≈ 1 regardless of N and 〈t_s〉. Lane switching (p_s = 1) reduces 〈t_c〉 for a given K, but its characteristic dependence with K differs for nonswitchers and switchers in the same traffic system. For the nonswitchers, 〈t_c〉 ∝ K^τ, where τ < 1. At low K values, switchers have a larger 〈t_c〉 that also increases more rapidly with K. At large K, the increase rates become equal for both. For nonswitchers, the possible t_c values obey an exponentially decaying probability density function p(t_c). The switchers on the other hand, are described by a fat‐tailed p(t_c) implying that a few are penalized with t_c values that are considerably longer than any of those experienced by nonswitchers. © 2006 Wiley Periodicals, Inc. Complexity 11: 35–42, 2006     

On critical Fujita exponents for heat equations with nonlinear flux conditions on the boundary

We consider nonnegative solutions of initial-boundary value problems for parabolic equationsu _t=u_xx, u_t=(u^m)_xxand (m>1) forx>0,t>0 with nonlinear boundary conditions−u _x=u^p,−(u ^m)_x=u^pand forx=0,t>0, wherep>0. The initial function is assumed to be bounded, smooth and to have, in the latter two cases, compact support. We prove that for each problem there exist positive critical valuesp ₀,p_c(withp ₀<p_c)such that forp∃(0,p ₀],all solutions are global while forp∃(p₀,p_c] any solutionu≢0 blows up in a finite time and forp>p _csmall data solutions exist globally in time while large data solutions are nonglobal. We havep _c=2,p _c=m+1 andp _c=2m for each problem, whilep ₀=1,p ₀=1/2(m+1) andp ₀=2m/(m+1) respectively. This work was done during visits of the first author to Iowa State University and the Institute for Mathematics and its Applications at the University of Minnesota. The second author was supported in part by NSF Grant DMS-9102210.     

Birth control for giants

The standard Erdős-Rényi model of random graphs begins with n isolated vertices, and at each round a random edge is added. Parametrizing n/2 rounds as one time unit, a phase transition occurs at time t = 1 when a giant component (one of size constant times n) first appears. Under the influence of statistical mechanics, the investigation of related phase transitions has become an important topic in random graph theory. We define a broad class of graph evolutions in which at each round one chooses one of two random edges {v ₁, v ₂}, {v ₃, v ₄} to add to the graph. The selection is made by examining the sizes of the components of the four vertices. We consider the susceptibility S(t) at time t, being the expected component size of a uniformly chosen vertex. The expected change in S(t) is found which produces in the limit a differential equation for S(t). There is a critical time t _c so that S(t) → ∞ as t approaches t _c from below. We show that the discrete random process asymptotically follows the differential equation for all subcritical t < t _c . Employing classic results of Cramér on branching processes we show that the component sizes of the graph in the subcritical regime have an exponential tail. In particular, the largest component is only logarithmic in size. In the supercritical regime t > t _c we show the existence of a giant component, so that t = t _c may be fairly considered a phase transition. Computer aided solutions to the possible differential equations for susceptibility allow us to establish lower and upper bounds on the extent to which we can either delay or accelerate the birth of the giant component. Research supported by the Australian Research Council, the Canada Research Chairs Program and NSERC. Research partly carried out while the author was at the Department of Mathematics and Statistics, University of Melbourne.     

A phase transition in the random transposition random walk

Our work is motivated by Bourque and Pevzner's (2002) simulation study of the effectiveness of the parsimony method in studying genome rearrangement, and leads to a surprising result about the random transposition walk on the group of permutations on n elements. Consider this walk in continuous time starting at the identity and let D _t be the minimum number of transpositions needed to go back to the identity from the location at time t. D _t undergoes a phase transition: the distance D _{cn /2}∼u(c)n, where u is an explicit function satisfying u(c)=c/2 for c≤1 and u(c)<c/2 for c>1. In addition, we describe the fluctuations of D _{cn /2} about its mean in each of the three regimes (subcritical, critical and supercritical). The techniques used involve viewing the cycles in the random permutation as a coagulation-fragmentation process and relating the behavior to the Erdős-Renyi random graph model.     

Oscillation and Nonoscillation for Second Order Linear Differential Equations

New oscillation and nonoscillation theorems are obtained for the second order linear differential equationu″ + p(t)u = 0, wherep(t) ∈ C[0, ∞) andp(t) ≥ 0. Conditions only about the integrals ofp(t) on every interval [2ⁿt₀, 2^{n + 1}t₀] (n = 1, 2,…) for some fixedt₀ > 0 are used in the results.     

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     

Inequalities for sums of independent geometrical random variables

Summary We give a survey of known results regarding Schur-convexity of probability distribution functions. Then we prove that the functionF(p ₁,...,p_n;t)=P(X₁+...+X_n≤t) is Schur-concave with respect to (p ₁,...,p_n) for every realt, whereX _i are independent geometric random variables with parametersp _i. A generalization to negative binomial random variables is also presented.     

Distance connectivity in graphs and digraphs

Let G = (V, A) be a digraph with diameter D ≠ 1. For a given integer 2 ≤ t ≤ D, the t-distance connectivity κ(t) of G is the minimum cardinality of an x → y separating set over all the pairs of vertices x, y which are at distance d(x, y) ≥ t. The t-distance edge connectivity λ(t) of G is defined similarly. The t-degree of G, δ(t), is the minimum among the out-degrees and in-degrees of all vertices with (out- or -in-) eccentricity at least t. A digraph is said to be maximally distance connected if κ(t) = δ(t) for all values of t. In this paper we give a construction of a digraph having D − 1 positive arbitrary integers c₂ ≤ … ≤ c_D, D > 3, as the values of its t-distance connectivities κ(2) = c₂, …, κ(D) = c_D. Besides, a digraph that shows the independence of the parameters κ(t), λ(t), and δ(t) is constructed. Also we derive some results on the distance connectivities of digraphs, as well as sufficient conditions for a digraph to be maximally distance connected. Similar results for (undirected) graphs are presented. © 1996 John Wiley & Sons, Inc.     

On the ratio of the expected maximum of a martingale and theL p-norm of its last term

For eachp>1, the supremum,S, of the absolute value of a martingale terminating at a random variableX inL _p, satisfiesES≦(Γ(q))^1/q‖X‖_p (q=p(p-1)^-1).The maximum,M, of a mean-zero martingale which starts at zero and terminates atX, satisfiesES≦(Γ(q))^1/q‖X‖_p (q=p(p-1)^-1), whereσ _q is the unique solution of the equationt = ‖Z −t ‖ _q for an exponentially distributed random variableZ with mean 1.σ _p has other characterizations and satisfies lim _p‖ q ^{− 1} σ _q =c withc determined byce ^c+1 = 1. Equalities in (1) and (2) are attainable by appropriate martingales which can be realized as stopped segments of Brownian motion. A presumably new property of the exponential distribution is obtained en route to inequality (2).     

Cp

The spacec _p is the class of operators on a Hilbert space for which thec _p norm |T| _p =[trace(T*T) ^p/2]^1/p is finite. We prove many of the known results concerningc _p in an elementary fashion, together with the result (new for 1<p<2) thatc _p is as uniformly convex a Banach space asl _p. In spite of the remarkable parallel of norm inequalities in the spacesc _p andl _p, we show thatp ≠ 2, noc _p built on an infinite dimensional Hilbert space is equivalent to any subspace of anyl _p orL _p space. The author was supported by National Science Foundation Grant GP-5707.     

Involution codimensions and trace codimensions of matrices are asymptotically equal

We calculate the asymptotic growth oft _n (M _p (F),*) andc _n (M _p (F),*), the trace and ordinary *-codimensions ofp×p matrices with involution. To do this we first calculate the asymptotic growth oft _n and then show thatc _n ⋍t _n . In memory of Shimshon Amitsur, our teacher and our friend Work supported by NSF grant DMS 9303230. The first author would also like to thank Bar-Ilan University and The Hebrew University of Jerusalem for their kind hospitality during his sabbatical year. Work supported by NSF grant DMS 910488     

Exact and explicit analytic solutions of an extended Jabotinsky functional differential equation

A Banach space X will be called extensible if every operator E → X from a subspace E ⊂ X can be extended to an operator X → X. Denote by dens X. The smallest cardinal of a subset of X whose linear span is dense in X, the space X will be called automorphic when for every subspace E ⊂ X every into isomorphism T: E → X for which dens X/E = dens X/TE can be extended to an automorphism X → X. Lindenstrauss and Rosenthal proved that c ₀ is automorphic and conjectured that c ₀ and ℓ₂ are the only separable automorphic spaces. Moreover, they ask about the extensible or automorphic character of c ₀(Γ), for Γ uncountable. That c ₀(Γ) is extensible was proved by Johnson and Zippin, and we prove here that it is automorphic and that, moreover, every automorphic space is extensible while the converse fails. We then study the local structure of extensible spaces, showing in particular that an infinite dimensional extensible space cannot contain uniformly complemented copies of ℓ _n ^p , 1 ≤ p < ∞, p ≠ 2. We derive that infinite dimensional spaces such as L _p (μ), p ≠ 2, C(K) spaces not isomorphic to c ₀ for K metric compact, subspaces of c ₀ which are not isomorphic to c ₀, the Gurarij space, Tsirelson spaces or the Argyros-Deliyanni HI space cannot be automorphic. The work of the first author has been supported in part by project MTM2004-02635     

Random subgraphs of finite graphs: I. The scaling window under the triangle condition

We study random subgraphs of an arbitrary finite connected transitive graph ?? obtained by independently deleting edges with probability 1 ? p. Let V be the number of vertices in ??, and let Ω be their degree. We define the critical threshold p_c = p_c (??, λ) to be the value of p for which the expected cluster size of a fixed vertex attains the value λV^1/3, where λ is fixed and positive. We show that, for any such model, there is a phase transition at p_c analogous to the phase transition for the random graph, provided that a quantity called the triangle diagram is sufficiently small at the threshold p_c. In particular, we show that the largest cluster inside a scaling window of size |p ? p_c| = Θ(Ω^?1V^?1/3) is of size Θ(V^2/3), while, below this scaling window, it is much smaller, of order O(?^?2 log(V?³)), with ? = Ω(p_c ? p). We also obtain an upper bound O(Ω(p ? p_c)V) for the expected size of the largest cluster above the window. In addition, we define and analyze the percolation probability above the window and show that it is of order Θ(Ω(p ? p_c)). Among the models for which the triangle diagram is small enough to allow us to draw these conclusions are the random graph, the n‐cube and certain Hamming cubes, as well as the spread‐out n‐dimensional torus for n > 6. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

On a Diophantine Inequality Over Primes (II)

In this short note we prove that if 1 < c < 81/40, c ≠ 2, N is a large real number, then the Diophantine inequality |p₁^c+p₂^c+p₃^c+p₄^c+p₅^c-N| < log^-1 N \vert p_1^c+p_2^c+p_3^c+p_4^c+p_5^c-N\vert < \log^{-1} N is solvable, where p ₁,···,p ₅ are primes.     

Pathwidth of outerplanar graphs

We are interested in the relation between the pathwidth of a biconnected outerplanar graph and the pathwidth of its (geometric) dual. Bodlaender and Fomin [3], after having proved that the pathwidth of every biconnected outerplanar graph is always at most twice the pathwidth of its (geometric) dual plus two, conjectured that there exists a constant c such that the pathwidth of every biconnected outerplanar graph is at most c plus the pathwidth of its dual. They also conjectured that this was actually true with c being one for every biconnected planar graph. Fomin [10] proved that the second conjecture is true for all planar triangulations. First, we construct for each p ≥ 1, a biconnected outerplanar graph of pathwidth 2p + 1 whose (geometric) dual has pathwidth p + 1, thereby disproving both conjectures. Next, we also disprove two other conjectures (one of Bodlaender and Fomin [3], implied by one of Fomin [10]. Finally we prove, in an algorithmic way, that the pathwidth of every biconnected outerplanar graph is at most twice the pathwidth of its (geometric) dual minus one. A tight interval for the studied relation is therefore obtained, and we show that all cases in the interval happen. © 2006 Wiley Periodicals, Inc. J Graph Theory 55: 27–41, 2007     

On Powers of Stieltjes Moment Sequences,I

For a Bernstein function f the sequence s_n=f(1)·...· f(n) is a Stieltjes moment sequence with the property that all powers s_n^c,c>0 are again Stieltjes moment sequences. We prove that is Stieltjes determinate for c≤ 2, but it can be indeterminate for c>2 as is shown by the moment sequence , corresponding to the Bernstein function f(s)=s. Nevertheless there always exists a unique product convolution semigroup such that ρ_c has moments . We apply the indeterminacy of for c>2 to prove that the distribution of the product of p independent identically distributed normal random variables is indeterminate if and only if p≥ 3     

Cycles of given color patterns

In 2-edge-colored graphs, we define an (s, t)-cycle to be a cyle of length s + t, in which s consecutive edges are in one color and the remaining t edges are in the other color. Here we investigate the existence of (s, t)-cycles, in a 2-edge-colored complete graph K^c_n on n vertices. In particular, in the first result we give a complete characterization for the existence of (s, t)-cycles in K^c_n with n relatively large with respect to max({s, t}). We also study cycles of length 4 for all possible values of s and t. Then, we show that K^c_n contains an (s, t)-hamiltonian cycle unless it is isomorphic to a specified graph. This extends a result of A. Gyárfás [Journal of Graph Theory, 7 (1983), 131–135]. Finally, we give some sufficient conditions for the existence of (s, 1)-cycles, (inverted sans serif aye) s ϵ {2, 3,…, n − 2}. © 1996 John Wiley & Sons, Inc.     

On a class of semilinear weakly hyperbolic equations

Abstract  In this paper, we deal with some global existence results for the large data smooth solutions of the Cauchy Problem associated with the semilinear weakly hyperbolic equations

Connected subgraphs with small degree sums in 3‐connected planar graphs

It is well‐known that every planar graph has a vertex of degree at most five. Kotzig proved that every 3‐connected planar graph has an edge xy such that deg(x) + deg (y) ≤ 13. In this article, considering a similar problem for the case of three or more vertices that induce a connected subgraph, we show that, for a given positive integer t, every 3‐connected planar graph G with |V(G)| ≥ t has a connected subgraph H of order t such that Σ_x∈V(H) deg_G(x) ≤ 8t − 1. As a tool for proving this result, we consider decompositions of 3‐connected planar graphs into connected subgraphs of order at least t and at most 2t − 1. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 191–203, 1999