Search

Abstract: We introduce a new procedure for generating the binomial random graph/hypergraph models, referred to as online sprinkling. As an illustrative application of this method, we show that for any fixed integer k ≥ 3, the binomial k‐uniform random hypergraph H n , p k contains N : = ( 1 − o ( 1 ) ) ( n − 1 k − 1 ) p edge‐disjoint perfect matchings, provided p ≥ log ⁡ C n n k − 1, where C : = C ( k ) is an integer depending only on k. Our result for N is asymptotically optimal and for p is optimal up to the p o l y l o g ( n ) factor. This significantly improves a result of Frieze and Krivelevich. [ABSTRACT FROM AUTHOR]

We consider random-turn positional games, introduced by Peres, Schramm, Sheffield, and Wilson in 2007. A p-random-turn positional game is a two-player game, played the same as an ordinary positional game, except that instead of alternating turns, a coin is being tossed before each turn to decide the identity of the next player to move (the probability of Player I to move is p). We analyze the random-turn version of several classical Maker-Breaker games such as the game Box (introduced by Chvátal and Erdős in 1987), the Hamilton cycle game and the k-vertex-connectivity game (both played on the edge set of [ABSTRACT FROM AUTHOR]

A graph G is said to be [ABSTRACT FROM AUTHOR]

We discuss a new algorithmic type of problem in random graphs studying the minimum number of queries one has to ask about adjacency between pairs of vertices of a random graph [ABSTRACT FROM AUTHOR]

In this paper we show how to use simple partitioning lemmas in order to embed spanning graphs in a typical member of G(n, p). Let the maximum density of a graph H be the maximum average degree of all the subgraphs of H. First, we show that for p = ω(Δ12n-1/2d log³ n), a graph G ~ G(n, p) w.h.p. contains copies of all spanning graphs H with maximum degree at most Δ and maximum density at most d. For d < Δ/2, this improves a result of Dellamonica, Kohayakawa, Rödl and Ruci´ncki. Next, we show that if we additionally restrict the spanning graphs to have girth at least 7 then the random graph contains w.h.p. all such graphs for p = ω(Δ12n-1/2 log³n). In particular, if p = ω(ω12n-1/2 log³ n), the random graph therefore contains w.h.p. every spanning tree with maximum degree bounded by Δ. This improves a result of Johannsen, Krivelevich and Samotij. Finally, in the same spirit, we show that for any spanning graph H with constant maximum degree, and for suitable p, if we randomly color the edges of a graph G ~ G(n, p) with (1 + o(1))|E(H)| colors, then w.h.p. there exists a rainbow copy of H in G (that is, a copy of H with all edges colored with distinct colors). [ABSTRACT FROM AUTHOR]

ABSTRACT In this paper we analyze biased Maker-Breaker games and Avoider-Enforcer games, both played on the edge set of a random board [ABSTRACT FROM AUTHOR]

Let n, k, and t be integers satisfying [ABSTRACT FROM AUTHOR]

We study Maker-Breaker games played on the edge set of a random graph. Specifically, we analyze the moment a typical random graph process first becomes a Maker's win in a game in which Maker's goal is to build a graph which admits some monotone increasing property \documentclass{article} \usepackage{mathrsfs} \usepackage{amsmath,amssymb} \pagestyle{empty} \begin{document} \begin{align*}\mathcal{P}\end{align*} \end{document}. We focus on three natural target properties for Maker's graph, namely being k -vertex-connected, admitting a perfect matching, and being Hamiltonian. We prove the following optimal hitting time results: with high probability Maker wins the k -vertex connectivity game exactly at the time the random graph process first reaches minimum degree 2 k; with high probability Maker wins the perfect matching game exactly at the time the random graph process first reaches minimum degree 2; with high probability Maker wins the Hamiltonicity game exactly at the time the random graph process first reaches minimum degree 4. The latter two statements settle conjectures of Stojaković and Szabó. We also prove generalizations of the latter two results; these generalizations partially strengthen some known results in the theory of random graphs. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011 [ABSTRACT FROM AUTHOR]

: ObjectivesRipening of the cervix with a Foley catheter commonly results in cervical dilatation without contractions. We examined the outcome of labour in women who underwent induction of labour using a Foley catheter, followed by either 1. early amniotomy, or 2. augmentation of labour by oxytocin and late amniotomy: DesignProspective randomised clinical trial: SettingLabour and delivery ward of a university teaching hospital: ParticipantsPregnant women ≥38 weeks of a singleton gestation, who had had no prior caesarean section: MethodsAll women underwent cervical ripening using a Foley catheter. Following removal of the catheter, women were randomly assigned to either early (n = 80) or late amniotomy (n = 88).Main outcome measures Comparison of mode of delivery and duration of labour between the two groups: ResultsThe rate of caesarean section was significantly higher in the early amniotomy group compared with the late amniotomy group (25% vs 7.9%; relative risk 1.74; 95% CI 1.3 – 2.34). The increase in caesarean section rate was due primarily to dystocia (15% vs 3.3%; relative risk 1.8; 95% CI 1.32 – 2.45). When excluding caesarean deliveries, no significant difference was found in duration of labour between the groups (8.3 hours (3.8) vs 7.7 hours (2.9)): ConclusionsIn women who undergo cervical ripening with a Foley catheter, augmentation of labour by oxytocin followed by amniotomy during active labour results in a lower rate of caesarean delivery for dystocia [ABSTRACT FROM AUTHOR]

We give an exponential improvement to the lower bound on diagonal Ramsey numbers for any fixed number of colors greater than two. [ABSTRACT FROM AUTHOR]

Objective: Several studies have noted an increased prevalence of pyelectasis in male fetuses. It is speculated that pyelectasis represents a normal physiologic variant in males, whereas its presence in females indicates an increased risk of chromosomal abnormalities. Thus, we sought to investigate the association between fetal gender and the risk of major trisomies in fetuses with pyelectasis., Methods: Retrospective analysis of a Genzyme Genetics amniocentesis database (1995 to 2004) was performed. Specimens obtained after an ultrasonographic finding of pyelectasis were eligible for analysis. The prevalence of major trisomies (trisomy 13, 18, or 21) in male and female fetuses with pyelectasis was compared using binomial distribution., Results: A total of 760,495 amniocentesis specimens were analyzed. Fetal pyelectasis was reported in 671 cases. A male predominance, with a male-to-female ratio of 2.14:1 (457 compared with 214) was statistically significant (P < .001). A major trisomy was detected in 26 male fetuses (5.7%): 18 cases of trisomy 21, 2 cases of trisomy 18, and 6 cases of trisomy 13. Nine female fetuses had a major trisomy (4.2%): 6 cases of trisomy 21 and 3 cases of trisomy 13. There was no significant difference in the overall prevalence of trisomies between male and female fetuses (P = .14)., Conclusion: We concur with previous studies documenting a higher prevalence of pyelectasis in male fetuses. In addition, our results indicate that the prevalence of major trisomies among fetuses with pyelectasis is unlikely to be dependent on fetal gender. Thus, counseling patients with regard to the genetic implications of fetal pyelectasis should be gender independent., Level of Evidence: II-2.