We consider the following probabilistic model of a graph on n labeled vertices. First choose random G(n, 1/2), and then randomly subset Q vertices size k force it to be clique by joining every pair an edge. The problem is give polynomial time algorithm for finding this hidden almost surely various values k. This question was posed independently, in variants, Jerrum Kučera. In paper we present efficient all k>cn0.5, any fixed c>0, thus improving trivial case k>cn0.5(log n)0.5. based spectral...

We prove that, for all values of the edge probability $p(n)$, largest eigenvalue random graph $G(n, p)$ satisfies almost surely $\lambda_1(G)=(1+o(1))\max\{\sqrt{\Delta}, np\}$, where Δ is maximum degree $G$, and o(1) term tends to zero as $\max\{\sqrt{\Delta}, np\}$ infinity.

More than forty years ago, Erdős conjectured that for any $t \leq \frac{n}{k}$ , every k -uniform hypergraph on n vertices without t disjoint edges has at most max ${\binom{kt-1}{k}, \binom{n}{k}-\binom{n-t+1}{k}\}$ edges. Although this appears to be a basic instance of the Turán problem (with -edge matching as excluded hypergraph), progress question remained elusive. In paper, we verify conjecture all < \frac{n}{3k^2}$ . This improves upon best previously known range =...

Abstract The classical result of Erdős and Rényi asserts that the random graph G ( n , p ) experiences sharp phase transition around \documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath}\pagestyle{empty}\begin{document}\begin{align*}p=\frac{1}{n}\end{align*} \end{document} – for any ε > 0 \documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath}\pagestyle{empty}\begin{document}\begin{align*}p=\frac{1-\epsilon}{n}\end{align*} all connected components are typically size O...

ABSTRACT For , the Erdős–Rogers function measures how large a ‐free induced subgraph there must be in graph on vertices. There has been an extensive amount of work towards estimating this function, but until very recently only case was well understood. A recent breakthrough Mattheus and Verstraëte Ramsey number states that which matches known lower bound up to term. In paper we build their approach generalize result by proving holds for every . This comes close best bound, improves...

For a graph H and an integer n , the Turán number is maximum possible of edges in simple on vertices that contains no copy . r -degenerate if every one its subgraphs vertex degree at most We prove that, for any fixed bipartite which all degrees colour class are This tight values can also be derived from earlier result Füredi. show there absolute positive constant c such motivated by conjecture Erdős asserts two graphs G Ramsey minimum colouring complete red blue, either or blue conjectured...

Abstract We describe a simple and yet surprisingly powerful probabilistic technique which shows how to find in dense graph large subset of vertices all (or almost all) small subsets have many common neighbors. Recently this has had several striking applications Extremal Graph Theory, Ramsey Additive Combinatorics, Combinatorial Geometry. In survey we discuss some them. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2011

The Ramsey number <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="r Subscript k Baseline left-parenthesis s comma n right-parenthesis"> <mml:semantics> <mml:mrow> <mml:msub> <mml:mi>r</mml:mi> <mml:mi>k</mml:mi> </mml:msub> <mml:mo stretchy="false">(</mml:mo> <mml:mi>s</mml:mi> <mml:mo>,</mml:mo> <mml:mi>n</mml:mi> stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">r_k(s,n)</mml:annotation>...

A beautiful conjecture of Erdős-Simonovits and Sidorenko states that, if H is a bipartite graph, then the random graph with edge density p has in expectation asymptotically minimum number copies over all graphs same order density. This also an equivalent analytic form connections to broad range topics, such as matrix theory, Markov chains, limits, quasirandomness. Here we prove vertex complete other part, deduce approximate version for H. Furthermore, large class graphs, stronger stability...

Abstract A classical theorem of Dirac from 1952 asserts that every graph on n vertices with minimum degree at least \documentclass{article} \usepackage{mathrsfs} \usepackage{amsmath} \pagestyle{empty} \begin{document} \begin{align*}\left\lceil n/2 \right\rceil\end{align*} \end{document} is Hamiltonian. In this paper we extend result to random graphs. Motivated by the study resilience properties prove if p ≫ log / , then a.a.s. subgraph G ( ) (1/2 + o (1) Our improves previously known bounds,...

We show that for any fixed dense graph $G$ and bounded-degree tree $T$ on the same number of vertices, a modest random perturbation will typically contain copy $T$. This combines viewpoints well-studied problems embedding trees into graphs graphs, extends sizable body existing research randomly perturbed graphs. Specifically, we there is $c=c(\alpha,\Delta)$ such if an $n$-vertex with minimum degree at least $\alpha n$, maximum most $\Delta$, then add $cn$ uniformly edges to $G$, resulting...

Abstract A proper coloring of the edges a graph G is called acyclic if there no 2‐colored cycle in . The edge chromatic number , denoted by a′ ( ), least colors an For certain graphs ) ≥ Δ( + 2 where maximum degree It known that ≤ 16 for any We prove exists constant c such whose girth at log and conjecture this upper bound holds all also show Δ almost Δ‐regular graphs. © 2001 John Wiley &amp; Sons, Inc. J Graph Theory 37: 157–167,

Abstract Random d ‐regular graphs have been well studied when is fixed and the number of vertices goes to infinity. We obtain results on many properties a random graph = ( n ) grows more quickly than $\sqrt{n}$ . These include connectivity, hamiltonicity, independent set size, chromatic number, choice size second eigenvalue, among others. ©2001 John Wiley &amp; Sons, Inc. Struct. Alg., 18: 346–363, 2001.

We consider the following probabilistic model of a graph on n labeled vertices. . First choose random Gn ,1 r 2 ,and then randomly subset Q vertices size k and force it to be clique by joining every pair an edge. The problem is give polynomial time algorithm for finding this hidden almost surely various values k. This question was posed independently, in variants, Jerrum Kucera. In paper we present efficient all ) cn 0.5 , ˇ any fixed c 0, thus improving trivial case log based spectral...

A distribution X over binary strings of length n has min-entropy k if every string probability at most 2-k in X. We say that is a δ-source its rate k⁄n least δ.We give the following new explicit instructions (namely, poly(n)- time computable functions) deterministicextractors, dispersers and related objects. All work for any fixed δ>0. No previous construction was known either these, δ‹1⁄2. The first two constitute major progress to very long-standing open problems.

Abstract In this article, we initiate a systematic study of graph resilience. The (local) resilience G with respect to property $\cal {P}$ measures how much one has change (locally) destroy . Estimating the leads many new and challenging problems. Here focus on random pseudorandom graphs prove several sharp results. © 2008 Wiley Periodicals, Inc. Random Struct. Alg.,