bluuebunny/crossref_metadata_2025_split huggingface dataset:
The phase transition in inhomogeneous random graphs
Authors: Bollobás Béla , Janson Svante , Riordan Oliver 
Published: June 2007

AbstractThe “classical” random graph models, in particular G(n,p), are “homogeneous,” in the sense that the degrees (for example) tend to be concentrated around a typical value. Many graphs arising in the real world do not have this property, having, for example, power‐law degree distributions. Thus there has been a lot of recent interest in defining and studying “inhomogeneous” random graph models.One of the most studied properties of these new models is their “robustness”, or, equivalently, the “phase transition” as an edge density parameter is varied. For G(n,p), p = c/n, the phase transition at c = 1 has been a central topic in the study of random graphs for well over 40 years.Many of the new inhomogeneous models are rather complicated; although there are exceptions, in most cases precise questions such as determining exactly the critical point of the phase transition are approachable only when there is independence between the edges. Fortunately, some models studied have this property already, and others can be approximated by models with independence.Here we introduce a very general model of an inhomogeneous random graph with (conditional) independence between the edges, which scales so that the number of edges is linear in the number of vertices. This scaling corresponds to the p = c/n scaling for G(n,p) used to study the phase transition; also, it seems to be a property of many large real‐world graphs. Our model includes as special cases many models previously studied.We show that, under one very weak assumption (that the expected number of edges is “what it should be”), many properties of the model can be determined, in particular the critical point of the phase transition, and the size of the giant component above the transition. We do this by relating our random graphs to branching processes, which are much easier to analyze.We also consider other properties of the model, showing, for example, that when there is a giant component, it is “stable”: for a typical random graph, no matter how we add or delete o(n) edges, the size of the giant component does not change by more than o(n). © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 31, 3–122, 2007
Shrinkage of de Morgan formulae under restriction
Authors: Paterson Michael S. , Zwick Uri 
Published: June 2007

AbstractIt is shown that a random restriction leaving only a fraction ϵ of the input variables unassigned reduces the expected de Morgan formula size of the induced function by a factor ofO(E(5−√2)/2) =O(ϵ1.63). (A de Morgan, or unate, formula is a formula over the basis {∧, ∨, ¬}.) This improves a long‐standing result ofO(ϵ1.5) by Subbotovskaya and a recent improvement toO(ϵ(21−√73)/8) =O(ϵ1.55) by Nisan and Impagliazzo. The New exponent yields an increased lower bound ofn(7−√3)/2−o(1)= Ω(n2.63) for the de Morgan formula size of a function in P defined by Andreev. This is the largest formula size lower bound known, even for functions in NP. © 1993 John Wiley & Sons, Inc.
Long range percolation in stationary point processes
Authors: Burton Robert M. , Meester Ronald W. J. 
Published: June 2007

AbstractWe consider a continuum percolation model in ℝd, d ⩾ 1 in which any two points of a stationary point process are connected with a probability which decays exponentially in the distance between the points. We give sufficient conditions for the (non)‐existence of a phase transition. We also give examples of processes which show that it is impossible to write down a theorem which relates the critical parameter value of a process to its density. Finally, we show that uniqueness of the infinite cluster is still valid in this general setting. © 1993 John Wiley & Sons, Inc.
A probabilistic analysis of a pattern matching problem
Authors: Atallah Mikhail J. , Jacquet Philippe , Szpankowski Wojciech 
Published: June 2007

AbstractThe study and comparison of strings of symbols from a finite or an infinite alphabet is relevant to various areas of science, notably molecular biology, speech recognition, and computer science. In particular, the problem of finding the minimum “distance” between two strings (in general, two blocks of data) is of a practical importance. In this article we investigate the (string) pattern matching problem in a probabilistic framework, namely, it is assumed that both strings form an independent sequences of i.i.d. symbols. Given a text stringaof lengthnand a pattern stringbof lengthm, letMm,nbe the maximum number of matches betweenband allm‐substrings ofa. Our main probabilistic result shows that for a wide range of input parametersin probability (pr.) providedm, n→∞ such that logn=o(m), wherePis the probability of a match between any two symbols of these strings, andTis the probability of a match between two positions in the text string and a given position of the pattern string. We also prove thatMm,n/m→P almost surely(a.s.) for logn=o(m). © 1993 John Wiley & Sons. Inc.
Radius and diameter of random subgraphs of the hypercube
Authors: Kostochka A. V. , Sapozhenko A. A. , Weber K. 
Published: June 2007

AbstractLet Gn = (Vn, En) be the random subgraph of the n‐cube graph Qn produced as follows: Vn is randomly sampled from the vertex set of Qn so that E{x ∈Vn} = pv independently for each vertex x ∈Qn. Then En is randomly sampled from the set of edges induced by Vn in Qn so that P{(x, y) ∈ En} = pe independently for each induced edge (x, y). Let Pv and pe be fixed probabilities such that 0 < p = pvpe ⩽ 1 and mp = [−1 /log2(1 − p)]. We show that for the radius R(Gn) and the diameter D(Gn) of the main component of Gn almost surely the following inequalities hold magnified image. © 1993 John Wiley & Sons, Inc.
Random graphs with monochromatic triangles in every edge coloring
Authors: Rödl Vojtech , Ruciński Andrzej 
Published: June 2007

AbstractWe prove that for every r ⩾ 2 there is C > 0 such that if p Cn−1/2 then almost surely every r‐coloring of the edges of the binomial random graph K(n, p) results in a monochromatic triangle. © 1994 John Wiley & Sons, Inc.
Random walks on colored graphs
Authors: Condon Anne , Hernek Diane 
Published: June 2007

AbstractWe initiate a study of random walks on undirected graphs with colored edges. In our model, a sequence of colors is specified before the walk begins, and it dictates the color of edge to be followed at each step. We give tight upper and lower bounds on the expected cover time of a random walk on an undirected graph with colored edges. We show that, in general, graphs with two colors have exponential expected cover time, and graphs with three or more colors have doubly‐exponential expected cover time. We also give polynomial bounds on the expected cover time in a number of interesting special cases. We described applications of our results to understanding the dominant eigenvectors of products and weighted averages of stochastic matrices, and to problems on time‐inhomogeneous Markov chains. © 1994 John Wiley & Sons, Inc.
Grids in random graphs
Authors: Fernandez de la Vega W. , Manoussakis Y. 
Published: June 2007

AbstractThreshold probabilities for the existence in a random graph on n vertices of a graph isomorphic to a given graph of order Cn and average degree at least three are investigated. In particular it is proved that the random graph G(n, p) on n vertices with edge probability	contains a square grid on En/2 vertices. © 1994 John Wiley & Sons, Inc.
Note on the heights of random recursive trees and random m‐ary search trees
Authors: Pittel Boris 
Published: June 2007

AbstractA process of growing a random recursive tree Tn is studied. The sequence {Tn} is shown to be a sequence of “snapshots” of a Crump–Mode branching process. This connection and a theorem by Kingman are used to show quickly that the height of Tn is asymptotic, with probability one, to c log n. In particular, c = e = 2.718 … for the uniform recursive tree, and c = (2γ)−1, where γe1+γ = 1, for the ordered recursive tree. An analogous reduction provides a short proof of Devroye's limit law for the height of a random m‐ary search tree. We show finally a close connection between another Devroye's result, on the height of a random union‐find tree, and our theorem on the height of the uniform recursive tree. © 1994 John Wiley & Sons, Inc.
Almost all regular graphs are hamiltonian
Authors: Robinson R. W. , Wormald N. C. 
Published: June 2007

AbstractIn a previous article the authors showed that almost all labelled cubic graphs are hamiltonian. In the present article, this result is used to show that almost all r‐regular graphs are hamiltonian for any fixed r ⩾ 3, by an analysis of the distribution of 1‐factors in random regular graphs. Moreover, almost all such graphs are r‐edge‐colorable if they have an even number of vertices. Similarly, almost all r‐regular bipartite graphs are hamiltonian and r‐edge‐colorable for fixed r ⩾ 3. © 1994 John Wiley & Sons, Inc.
Random sparse unary predicates
Authors: Shelah Saharon , Spencer Joel 
Published: June 2007

AbstractRandom unary predicates U on [n] holding with probability p are examined with respect to sentences A in a first‐order language containing U and “less than.” When p = p(n) satisfies nk+1 ≪ 1 ≪ npk it is shown that Pr[A] approaches a limit dependent only on k and A. In a similar circular model the limit is shown to be zero or one. © 1994 John Wiley & Sons, Inc.
Unlabeled trees: Distribution of the maximum degree
Authors: Goh William M. Y. , Schmutz Eric 
Published: June 2007

AbstractPick a tree uniformly at random from among all unlabeled trees on n vertices, and let Xn be the maximum of the degrees of its vertices. For any fixed integer d,
magnified image
as n→∞, where μn = c1 log n, where {μn} : = μn – ⌊μ⌋ denotes the fractional part of μn and where co, c1, and η∞ are knnown constants, givenb approximately by c0 = 3.262 …, c1 = 0.9227 …, and η∞ = 0.3383…. © 1994 John Wiley & Sons, Inc.
Low‐diameter graph decomposition is in NC
Authors: Awerbuch Baruch , Berger Bonnie , Cowen Lenore , Peleg David 
Published: June 2007

AbstractWe obtain the firstNCalgorithm for the low‐diameter graph decomposition problem on arbitrary graphs. Our algorithm runs inO(log5(n)) time, and usesO(n2) processors. © 1994 John Wiley & Sons, Inc.
A probably fast, provably optimal algorithm for rectilinear Steiner trees
Authors: Deneen Linda L. , Shute Gary M. , Thomborson Clark D. 
Published: June 2007

AbstractWe use the technique of divide‐and‐conquer to construct a rectilinear Steiner minimal tree on a set of sites in the plane. A well‐known optimal algorithm for this problem by Dreyfus and Wagner [10] is used to solve the problem in the base case. The run time of our optimal algorithm is probabilistic in nature: for all ϵ > 0, there exists b > 0 such that Prob[T(n) > 2b√n log n]>1–ϵ, for n log n > 1 – ϵ, for n sites uniformly distributed on a rectangle. The key fact in the run‐time argument is the existence of probable bounds on the number of edges of an optimal tree crossing our subdivision lines. We can test these bounds in low‐degree polynomial time for any given set of sites. © 1994 John Wiley & Sons, Inc.
Near‐perfect token distribution
Authors: Broder A. Z. , Frieze A. M. , Shamir E. , Upfal E. 
Published: June 2007

AbstractSuppose that n tokens are arbitrarily placed on the n nodes of a graph. At each parallel step one token may be moved from each node to an adjacent node. An algorithm for the near‐perfect token distribution problem redistributes the tokens in a finite number of steps, so that, at the end, no more than O(1) tokens reside at each node. (In perfect distribution, at the end, exactly one token resides at each node.) In this paper we present a simple algorithm that works for all extrovert graphs, a new property which we define and study. In terms of connectivity requirements, extrovert graphs are roughly in‐between expanders and compressors. Our results lead to an optimal solution for the near‐perfect token distribution problem on almost all cubic graphs. The new solution is conceptually simpler than previous algorithms, and applies to graphs of minimum possible degree. © 1994 John Wiley & Sons, Inc.
Improved upper bounds for the critical probability of oriented percolation in two dimensions
Authors: Balister Paul , Bollobás Béla , Stacey Alan 
Published: June 2007

AbstractWe refine the method of our previous paper [2] which gave upper bounds for the critical probability in two‐dimensional oriented percolation. We use our refinement to show that

© 1994 John Wiley & Sons, Inc.
Lower bounds for a subexponential optimization algorithm
Authors: Matoušek Jiří 
Published: June 2007

AbstractRecently Sharir and Welzl described a randomized algorithm for a certain class of optimization problems (including linear programming), and then a subexponential bound for the expected running time was established. We give an example of an (artificial) optimization problem fitting into the Sharir–Welzl framework for which the running time is close to the upper bound, thus showing that the analysis of the algorithm cannot be much improved without stronger assumptions on the optimization problem and/or modifying the algorithm. Further we describe results of computer simulations for a specific linear programming problem, which indicate that “one‐permutation” and “move‐to‐front” variants of the Sharir–Welzl algorithm may sometimes perform much worse than the algorithm itself. © 1994 John Wiley & Sons, Inc.
A shuffle that mixes sets of any fixed size much faster than it mixes the whole deck
Authors: Pemantle Robin 
Published: June 2007

AbstractConsider an n by n array of cards shufled in the following manner. An element x of the array is chosen uniformly at random. Then with probability 1/2 the rectangle of cards above and to the left of x is rotated 180deg;, and with probability 1/2 the rectangle of cards below and to the right of x is rotated 180°. It is shown by an eigenvalue method that the time required to approach‐ the uniform distribution is between n2/2 and cn2 in n for some constant c. On the other hand, for any k it is shown that the time needed to uniformly distribute a set of cards of size k is at most c(k)n, where c(k) is a constant times k3 In(k)2. This is established via coupling; no attempt is made to get a good constant. © 1994 John Wiley & Sons, Inc.
Modified Corn Starches with Improved Comprehensive Properties for Preparing Thermoplastics
Authors: Zhang Shui‐Dong , Zhang Yu‐Rong , Zhu Jiang , Wang Xiu‐Li , Yang Ke‐Ke , Wang Yu‐Zhong 
Published: June 2007

AbstractA novel method of starch modification was developed to obtain thermoplastic starch plastics with improved comprehensive properties. Corn starch was oxidized under mild conditions using sodium periodate to prepare dialdehyde starch, which had an acceptable average molecular weight. The dialdehyde starch with 35.2% carbonyl content was reacted with different alcohols (methanol, ethanol, and glycol) to prepare a series of novel starch derivatives, whose structures were characterized by 1H‐NMR and FT‐IR. The thermogravimetric analysis showed that these starch derivatives had an improved thermal stability compared with dialdehyde starch. Thermoplastic starch and its derivatives were prepared when water and glycerol were added as plasticizers. The modified thermoplastic starch and its derivatives had better mechanical properties than other modified starches, and lower humidity absorption than conventional thermoplastic starches. The highest tensile strength and elongation at break reached 17.5 MPa and 149%, respectively, and the highest humidity absorption was about 37%.
Correlations of the Composition, Minerals, and RVA Pasting Properties of Various Potato Starches
Authors: Zaidul I. S. Md. , Norulaini Nik , Omar A. K. Mohd. , Yamauchi Hiroaki , Noda Takahiro 
Published: June 2007

AbstractMultiple linear regression equations were developed to correlate the granule size distribution, composition, and minerals content with the Rapid Visco Analyser (RVA) pasting properties of potato starches of different cultivars. From the experimental values and the values of the regression coefficients, it could be observed that a higher level of amylose resulted in a lower peak viscosity (PV) and breakdown (BD) and higher setback (SB) and peak viscosity temperature (PVT) in the potato starches. The reverse was observed when the phosphorus content was higher. Smaller granule size was associated with a decrease in the PVT, whereas larger granules demonstrated higher PV, BD, and SB values in the potato starches. A higher calcium content was associated with a decrease in PV and an increase in BD, SB, and PVT. On the other hand, higher potassium was associated with an increase in PV, BD, SB, and PVT. The sodium contents demonstrated a higher PV and SB, and the reverse was observed in the BD and PVT. It is difficult to conclude the precise role of magnesium ions to the RVA properties although as divalent cations, they may have similar effect as calcium. From the positive and negative values of the regression coefficients it was shown that the correlation is useful for determining more precise values of the RVA pasting properties using a multiple linear regression equation. The correlations were also useful for predicting the effects of the starch composition and minerals on the RVA pasting properties.
Starch Characterisation of Araucaria angustifolia and Araucaria araucana Seeds
Authors: Conforti Paula A. , Lupano Cecilia E. 
Published: June 2007

AbstractAraucaria angustifolia and Araucaria araucana are conifers that cover different areas of South America. Their seeds have been consumed from prehistoric times until today in Brazil, Argentina and Chile. In this work, the starch of Araucaria angustifolia and Araucaria araucana seeds were analysed by light and environmental scanning electron microscopy, X‐ray diffraction, and differential scanning calorimetry. The starch granules of A. angustifolia and A. araucana were round or slightly oval, with a central hilum. Both starches gave X‐ray diffraction patterns compatible with the A‐type, with strong peaks at 15°, 17°, and 23°. The gelatinisation temperature of A. angustifolia starch (68.5°C) was higher than that of A. araucana (66.6°C), probably due to the higher amylose content of the former (22.4 % and 17.3 %, respectively). The thermograms of A. araucana starch presented a minor peak at about 71°C, which was attributed to the fact that the starch granules population of A. araucana was heterogeneous, with large and small granules, whereas A. angustifolia starch contained mainly large granules.
Evaluation of bit error rate for packet combining with constellation rearrangement
Authors: Benjillali Mustapha , Szczecinski Leszek , Aïssa Sonia , Gonzalez Cristian 
Published: June 2007

AbstractIn this paper, we propose a method for evaluation of the bit error rate (BER) for packet combining based on constellation rearrangement (CoRe). Such mapping diversity scheme, adopted in the high speed downlink packet access (HSDPA), uses Gray‐mapped constellations and is based on suboptimal accumulation of the reliability metrics generated in each of the transmissions. We present an exact model for the logarithmic likelihood ratios (LLR) obtained by means of the so‐called max‐log approximation, and we show that their conditional probability density functions (pdf) are piecewise Gaussian. We then present the derivation of the uncoded BER and illustrate it with simulation results that confirm our formulation. Finally, we propose simplifications which significantly reduce the complexity of the evaluation method and provide results with a very good accuracy; an extension to transmissions over faded channel is also presented. Copyright © 2007 John Wiley & Sons, Ltd.
Sexual abuse of patients by therapists: Strategies for offender management and rehabilitation
Authors: Gartrell Nanette , Herman Judith , Olarte Silvia , Feldstein Michael , Localio Russell , Schoener Gary 
Published: June 2007

AbstractMany therapists are unsure of how to respond to reports of sexual abuse of patients by previous therapists. The results of strategies developed in Minnesota and other jurisdictions suggest ways to handle the reporting, Management, and rehabilitation of offenders in therapist‐patient sexual abuse cases.
Insanity and filicide: Women who murder their children
Authors: Holden Carol E. , Burland Andrea Stephenson , Lemmen Craig A. 
Published: June 2007

AbstractA mother who murders her child challenges the empathic skills of evaluating clinicians. In this chapter, original research, supplemented by detailed case histories, compares women adjudicated criminally responsible for the murders of their children with those adjudicated not guilty by reason of insanity.
K2[(UO2)As2O7] – the First Uranium Polyarsenate
Authors: Alekseev Evgeny V. , Krivovichev Sergey V. , Depmeier Wulf 
Published: June 2007

AbstractYellowish crystals of K2[(UO2)As2O7] (1) have been synthesized by solid‐state reactions method. The structure of 1 [orthorhombic, Pmmn, a = 12.601(2), b = 13.242(2), c = 5.621(1) Å, V = 937.9(3) Å3, Z = 4] has been solved by direct methods and refined to R1 = 0.049, wR2 = 0.1060 for 1059 observed reflections. The structure of 1 is based upon [(UO2)As2O7]2− sheets formed by corner sharing between [UO6]6− distorted octahedra and [As2O7]4− polyarsenate groups. The K+ cations are either in eightfold or tenfold coordination and are located between the sheets. The topology of the uranyl arsenate sheet is related to silicate minerals of the melilite group and related synthetic silicate, aluminate and germanate compounds.
Solvothermal Synthesis and Characterization of Lanthanide Chalcogenidostannates [Ln2(en)6(μ2‐OH)2][Sn2S6] (Ln = Dy, Er) and [Dy2(en)6(μ2‐OH)2][Sn2Se6]
Authors: Jia Ding‐Xian , Zhu Ai‐Mei , Deng Jie , Suzhou Yong Zhang 
Published: June 2007

AbstractNew lanthanide chalcogenidostannates [Ln2(en)6(μ2‐OH)2][Sn2S6] (Ln = Dy (1), Er (2)) and [Dy2(en)6(μ2‐OH)2][Sn2Se6] (3) (en = ethylenediamine) were synthesized by reactions of SnCl4 and S (or Se) with Ln2O3 oxides under the mild solvothermal conditions. Compounds 1‐3 are isostructural and consist of a binuclear lanthanide(III) complex cation [Ln2(en)6(μ2‐OH)2]4+ and a dimeric anion [Sn2E6]4− (E = S, Se). The anion is composed of two SnE4 tetrahedra sharing a common edge with C2h symmetry. All the lanthanide(III) atoms are eight‐coordinate by six nitrogen atoms of three en ligands and two oxygen atoms of two μ2‐OH groups forming distorted bicapped trigonal prisms. In compounds 1‐3, extensive hydrogen bonds are formed leading to three‐dimensional networks of anions and cations. Compounds 1‐3 remove all the organic part in one step upon heating in the nitrogen stream.
Syntheses, Crystal Structures and Photophysical Properties of a Series of Cadmium(II) Coordination Polymers
Authors: Xian Yu , Niu Shu Yun , Jin Jing , Sun Li Ping , Yang Guang Di , Ye Ling 
Published: June 2007

AbstractThree cadmium(II) coordination polymers [Cd(NA)2(H2O)2]n (1), {[Cd(NA)(phen)(NO3)]·(H2O)1/2}n (2), {[Cd(NA)(CH3C6H4COO)(H2O)2]·(CH3C6H4COOH)}n (3) (HNA = nicotinic acid, phen = 1, 10‐phenanthroline) have been synthesized by hydrothermal method. Their single‐crystal structures were determined by X‐ray diffractometry. The absorption, excitation and emission spectra were investigated and all the complexes emit strong fluorescence: λemmax = 544 nm (λex = 492 nm), 1; λemmax = 466 nm (λex = 393 nm), 2; λemmax = 430 nm (λex = 313 nm), 3. At room temperature in the solid state the fluorescence lifetimes of the complexes were investigated and the relationships between the spectra were discussed as well as the connections of luminescence and crystal structures.