Michael Krivelevich

Noga Alon, Ido Ben-eliezer, Michael Krivelevich

graphs

Small (2009)

sample spaces cannot fool low degree polynomials

The critical bias for the Hamiltonicity game is n/ln n (2009)

Krivelevich, Michael

We prove that in the biased 1:b Hamiltonicity Maker-Breaker game, played on the edges of the complete graph K_n, Maker has a winning strategy for b(n)

Spanning directed trees with many leaves (2009)

Noga Alon, Fedor V. Fomin, Gregory Gutin, Michael Krivelevich, Saket Saurabh

Abstract. The Directed Maximum Leaf Out-Branching problem is to find an out-branching (i.e. a rooted oriented spanning tree) in a given digraph with the maximum number of leaves. In this paper, we...

Ramsey games with giants (2009)

Bohman, Tom, Frieze, Alan, Krivelevich, Michael, Loh, Po-Shen, Sudakov, Benny

The classical result in the theory of random graphs, proved by Erdos and Renyi in 1960, concerns the threshold for the appearance of the giant component in the random graph process. We consider a...

Resilient pancyclicity of random and pseudo-random graphs (2009)

Krivelevich, Michael, Lee, Choongbum, Sudakov, Benny

A graph $G$ on $n$ vertices is \textit{pancyclic} if it contains cycles of length $t$ for all $3 \leq t \leq n$. In this paper we prove that for any fixed $\epsilon>0$, the random graph $G(n,p)$ with...

Hamiltonicity of the random geometric graph (2009)

Krivelevich, Michael, Muller, Tobias

Let $X_1,..., X_n$ be independent, uniformly random points from $[0,1]^2$. We prove that if we add edges between these points one by one by order of increasing edge length then, with probability...

Hamiltonicity thresholds in Achlioptas processes (2009)

Michael Krivelevich, Eyal Lubetzky, Benny Sudakov

In this paper we analyze the appearance of a Hamilton cycle in the following random process. The process starts with an empty graph on n labeled vertices. At each round we are presented with K = K(n)...

On the random satisfiable process (2009)

Michael Krivelevich, Benny Sudakov, Dan Vilenchik

Abstract. In this work we suggest a new model for generating random satisfiable k-CNF formulas. To generate such formulas – randomly permute all 2 k ` ´ n possible clauses over the variables...

Embedding nearly-spanning bounded degree trees (2009)

Avoiding small subgraphs in Achlioptas processes, preprint (2009)

We derive a sufficient condition for a sparse graph G on n vertices to contain a copy of atreeT of maximum degree at most d on (1 − ɛ)n vertices, in terms of the expansion properties of G. As a...

Michael Krivelevich, Po-shen Loh, Benny Sudakov

ABSTRACT: For a fixed integer r, consider the following random process. At each round, one is presented with r random edges from the edge set of the complete graph on n vertices, and is asked to...

LARGE NEARLY REGULAR INDUCED SUBGRAPHS ∗ (2009)

Contents Minors in expanding graphs (2009)

Abstract. For a real c ≥ 1 and an integer n, let f(n, c) denote the maximum integer f such that every graph on n vertices contains an induced subgraph on at least f vertices in which the maximum...

Michael Krivelevich, Benjamin Sudakov

Spanning directed trees with many leaves (2009)

Noga Alon, Fedor V. Fomin, Gregory Gutin, Michael Krivelevich, Saket Saurabh

The Directed Maximum Leaf Out-Branching problem is to find an out-branching (i.e. a rooted oriented spanning tree) in a given digraph with the maximum number of leaves. In this paper, we obtain two...

Large (2009)

MaxCut in H-free graphs (2009)

nearly regular induced subgraphs

On smoothed k-CNF formulas and the Walksat (2009)

For a graph G, let f(G) denote the maximum number of edges in a cut of G. For an integer m and for a fixed graph H, let f(m, H) denote the minimum possible cardinality of f(G), as G ranges over all...

Amin Coja-oghlan, Uriel Feige, Alan Frieze, Michael Krivelevich, Dan Vilenchik

algorithm

A note on regular Ramsey graphs (2009)

Noga Alon, Sonny Ben-shimon, Michael Krivelevich

We prove that there is an absolute constant C> 0 so that for every natural n there exists a trianglefree regular graph with no independent set of size at least C √ n log n. 1

Algorithms (2008)

Noga Alon, Gregory Gutin, Michael Krivelevich

with large domination ratio

A (2008)

A note on regular Ramsey graphs (2008)

sharp threshold for network reliability

Alon, Noga, Ben-Shimon, Sonny, Krivelevich, Michael

We prove that there is an absolute constant $C>0$ so that for every natural $n$ there exists a triangle-free \emph{regular} graph with no independent set of size at least $C\sqrt{n\log n}$.

On (2008)

Michael Krivelevich, Benny Sudakov, Van H. Vu, Nicholas C. Wormald

the probability of independent sets in random graphs

Testing low-degree polynomials over GF(2) (2008)

Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron

Abstract. We describe an efficient randomized algorithm to test if a given binary function � � �� is a low-degree polynomial (that is, a sum of low-degree...

Spanning directed trees with many leaves ⋆ (2008)

Noga Alon, Fedor V. Fomin, Gregory Gutin, Michael Krivelevich, Saket Saurabh

Abstract. The Directed Maximum Leaf Out-Branching problem is to find an out-branching (i.e. a rooted oriented spanning tree) in a given digraph with the maximum number of leaves. In this paper, we...

Regular induced subgraphs of a random graph (2008)

Krivelevich, Michael, Sudakov, Benny, Wormald, Nicholas

An old problem of Erd\H{o}s, Fajtlowicz and Staton asks for the order of a largest induced regular subgraph that can be found in every graph on n vertices. Motivated by this problem, we consider the...

Large (2008)

Michael Krivelevich, Zeev Nutov, Mohammad R. Salavatipour, Jacques Verstraete, Raphael Yuster

nearly regular induced subgraphs

and (2008)

Permission to make digital/hard copy of all or part of this material without fee for personal or classroom use provided that the copies are not made or distributed for profit or commercial advantage,...

Long (2008)

Noga Alon, Michael Krivelevich, Paul Seymour

cycles in critical graphs

On the random satisfiable process (2008)

Krivelevich, Michael, Sudakov, Benny, Vilenchik, Dan

In this work we suggest a new model for generating random satisfiable k-CNF formulas. To generate such formulas -- randomly permute all 2^k\binom{n}{k} possible clauses over the variables x_1, ...,...

Fast winning strategies in Avoider-Enforcer games (2008)

Hefetz, Dan, Krivelevich, Michael, Stojaković, Miloš, Szabó, Tibor

In numerous positional games the identity of the winner is easily determined. In this case one of the more interesting questions is not {\em who} wins but rather {\em how fast} can one win. These...

Hamiltonicity thresholds in Achlioptas processes (2008)

Krivelevich, Michael, Lubetzky, Eyal, Sudakov, Benny

In this paper we analyze the appearance of a Hamilton cycle in the following random process. The process starts with an empty graph on n labeled vertices. At each round we are presented with K=K(n)...

Discrepancy games (2008)

Noga Alon, Michael Krivelevich, Joel Spencer, Tibor Szabó

We investigate a game played on a hypergraph H = (V,E) bytwoplayers, Balancer and Unbalancer. They select one element of the vertex set V alternately until all vertices are selected. Balancer wins if...

List (2008)

coloring of random and pseudo-random graphs

Coloring (2008)

Testing low-degree polynomials over GF(2), booktitle (2008)

graphs with sparse neighborhoods

Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron

We describe an efficient randomized algorithm to test if a given binary function f: {0, 1} n → {0, 1} is a low-degree polynomial (that is, a sum of low-degree monomials). For a given integer k ≥...

Finding (2008)

a large hidden clique in a random graph ∗

Induced (2008)

Noga Alon, Gregory Gutin, Michael Krivelevich

subgraphs of prescribed size

Algorithms (2008)

with large domination ratio

time has two-prover interactive protocols. Computational Complexity, 1:3–40, 1991. (2008)

Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron Testing, László Babai, ...

[4] Sanjeev Arora, László Babai, Jacques Stern, and Z Sweedyk. The hardness of approximate optima in lattices, codes, and systems of linear equations. Journal of

On (2008)

Michael Krivelevich, Benny Sudakov, Prasad Tetali

smoothed analysis in dense graphs and formulas

Abstract Testing Triangle-Freeness in General Graphs (2008)

Noga Alon, Tali Kaufman, Michael Krivelevich, Dana Ron

In this paper we consider the problem of testing whether a graph is triangle-free, and more generally, whether it is H-free, for a fixed subgraph H. The algorithm should accept graphs that are...

Discrepancy games (2008)

Noga Alon, Michael Krivelevich, Joel Spencer, Tibor Szabó

We investigate a game played on a hypergraph H = (V, E) by two players, Balancer and Unbalancer. They select one element of the vertex set V alternately until all vertices are selected. Balancer wins...

Planarity, colorability and minor games (2008)

Choosability in random hypergraphs (2008)

Let m and b be positive integers and let F be a hypergraph. In an (m, b, F) Maker-Breaker game two players, called Maker and Breaker, take turns selecting previously unclaimed vertices of F. Maker...

Michael Krivelevich, Benny Sudakov, V. H. Vu

The choice number of a hypergraph H = (V, E) is the least integer s for which for every family of color lists S = {S(v) : v ∈ V}, satisfying |S(v) | = s for every v ∈ V, there exists a choice...

Covering (2008)

codes with improved density

Fast (2008)

Vol. 19, No. 3, pp. 719–727 THE STRONG CHROMATIC INDEX OF RANDOM GRAPHS ∗ (2008)

winning strategies in positional games

Alan Frieze, Michael Krivelevich, Benny Sudakov

Abstract. The strong chromatic index of a graph G, denoted by χs(G), is the minimum number of colors needed to color its edges so that each color class is an induced matching. In this paper we...

Covering Codes With Improved Density (2008)

A. Blokhuis, G. D. Cohen, I. S. Honkala, S. N. Litsyn, A. C. Lobstein, ...

The ADS of the code in i) and the binary Golay code produces a ‘RSY PH“V code. This is a new code.

Avoiding small subgraphs in Achlioptas processes, preprint (2008)

Michael Krivelevich, Po-shen Loh, Benny Sudakov

Abstract For a fixed integer r, consider the following random process. At each round, one is presented with r random edges from the edge set of the complete graph on n vertices, and is asked to...

On smoothed analysis in dense graphs and formulas (2008)

Michael Krivelevich, Benny Sudakov, Prasad Tetali

ABSTRACT: We study a model of random graphs, where a random instance is obtained by adding random edges to a large graph of a given density. The research on this model has been started by Bohman and...

Large (2008)

Testing low-degree polynomials over (2008)

nearly regular induced subgraphs

Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn

Abstract. We describe an efficient randomized algorithm to test if a given binary function is a low-degree polynomial (that is, a sum of low-degree monomials). For a �� given integer...

Algorithms with large domination ratio Noga Alon \Lambda (2008)

Gregory Gutin, Michael Krivelevich

Abstract Let P be an optimization problem, and let A be an approximation algorithm for P. The domination ratio domr(A; n) is the maximum real q such that the solution x(I) obtained by A for any...

On rainbow trees and cycles Alan Frieze (2008)

The isoperimetric constant of the random graph process, preprint (2008)

0 such that if an edge colouring of Kn is cn-bounded then there exist rainbow cycles of all sizes 3 < = k < = n.

Itai Benjamini, Simi Haber, Michael Krivelevich, Eyal Lubetzky

2\Delta graphs, where eG(0) is the edgeless graph on n vertices, and eG(t) is the result of addingan edge to e G(t- 1), uniformly distributed over all the missing edges. We show that in almost every...

Discrepancy games (2008)

Noga Alon, Michael Krivelevich, Joel Spencer, Tibor Szabó

We investigate a game played on a hypergraph H = (V,E) by two players, Balancer and Unbalancer. They select one element of the vertex set V alternately until all vertices are selected. Balancer wins...

Contents Minors in expanding graphs (2008)

Michael Krivelevich, Benjamin Sudakov

On the random satisfiable 3CNF process (2008)

Michael Krivelevich, Benny Sudakov, Dan Vilenchik

The (2008)

Alan Frieze, Michael Krivelevich, Benny Sudakov

strong chromatic index of random graphs

On the random satisfiable 3CNF process (2008)

Michael Krivelevich, Benny Sudakov, Dan Vilenchik

Abstract. In this work we suggest a new model for generating random satisfiable 3CNF formulas. To generate such formulas – randomly permute all 8 � � n possible clauses over the variables...

On two Hamilton cycle problems in random graphs (2008)

Alan Frieze, Michael Krivelevich, Benny Sudakov

We study two problems related to the existence of Hamilton cycles in random graphs. The first question relates to the number of edge disjoint Hamilton cycles that the random graph Gn,p contains....

The (2008)

strong chromatic index of random graphs

On two Hamilton cycle problems in random graphs (2008)

Spanning directed trees with many leaves (2008)

1 Introduction In this paper, we give results on two problems related to Hamilton cycles in random graphs. 1.1 Edge Disjoint Hamilton Cycles It was shown by Koml'os and Szemer'edi [8] that...

Noga Alon, Fedor V. Fomin, Gregory Gutin, Michael Krivelevich, Saket Saurabh

Abstract. The Directed Maximum Leaf Out-Branching problem is to find an out-branching (i.e. a rooted oriented spanning tree) in a given digraph with the maximum number of leaves. In this paper, we...

Course number: 0366-3267 (2008)

Biased positional games and small hypergraphs with large covers, submitted (2008)

Prospective audience: the course is intended for second and third year undergraduate students

Avoider-Enforcer: The Rules of the Game (2008)

There are several types of positional games depending on how the identity of the winner is determined. In this paper we restrict our attention to two of them.

Ido Ben-eliezer, Tali Kaufman, Michael Krivelevich, Dana Ron

An Avoider-Enforcer game is played by two players, called Avoider and Enforcer, on a hypergraph F ⊆ 2 X. The players claim previously unoccupied elements of the board X in turns. Enforcer wins if...

The (2008)

the strength of query types in property testing:

Avoider-Enforcer: The Rules of the Game (2008)

On smoothed k-CNF formulas and the Walksat (2008)

An Avoider-Enforcer game is played by two players, called Avoider and Enforcer, on a hypergraph F ⊆ 2 X. The players claim previously unoccupied elements of the board X in turns. Enforcer wins if...

Amin Coja-oghlan, Uriel Feige, Alan Frieze, Michael Krivelevich, Dan Vilenchik

algorithm

fixed degree sequence (2008)

Colin Cooper, Alan Frieze, Michael Krivelevich

cycles in random graphs with a

A sharp threshold for the Hamilton cycle Maker-Breaker game (2008)

Perfectly balanced partitions of smoothed graphs (2008)

We study the Hamilton cycle Maker-Breaker game, played on the edges of the random graph G(n, p). We prove a conjecture from [13], asserting that the property that Maker is able to win this game, has...

Ido Ben-eliezer, Michael Krivelevich

For a graph G = (V, E) of even order, a partition (V1, V2) of the vertices is said to be perfectly balanced if |V1 | = |V2 | and the numbers of edges in the subgraphs induced by V1 and V2 are equal....

A note on regular Ramsey graphs (2008)

Noga Alon, Sonny Ben-shimon, Michael Krivelevich

We prove that there is an absolute constant C> 0 so that for every natural n there exists a trianglefree regular graph with no independent set of size at least C √ n log n. 1

Fast winning strategies in Avoider-Enforcer games (2008)

On rainbow trees and cycles (2008)

In numerous positional games the identity of the winner is easily determined. In this case one of the more interesting questions is not who wins but rather how fast can one win. These type of...

Sharp threshold for network reliability (2007)

We derive sufficient conditions for the existence of rainbow cycles of all lengths in edge colourings of complete graphs. We also consider rainbow colorings of a certain class of trees. 1

Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy

Given a graph G on n vertices with maximal degree d, form a random subgraph G p by choosing each edge of G independently with probability p. Strengthening a classical result of Margulis we prove that...

x (2007)

Let P be a property of graphs. An ffl-test for P is a randomized algorithm which, given the ability to make queries whether a desired pair of vertices of an input graph G with n vertices are adjacent...

On A Theorem Of Lovász On Covers In r-Partite Hypergraphs (2007)

Noga Alon, Haim Kaplan, Michael Krivelevich, Dahlia Malkhi

Abstract. In this paper, we provide a method to safely store a document in perhaps the most challenging settings, a highly decentralized replicated storage system where up to half of the storage...

Ron Aharoni, Ron Holzman, Michael Krivelevich

. A theorem of Lov'asz asserts that ø (H)=ø (H) r=2 for every r-partite hypergraph H (where ø and ø denote the covering number and fractional covering number respectively). Here it is shown...

Adding random edges to dense graphs (2007)

Tom Bohman, Alan Frieze, Michael Krivelevich, Ryan Martin

This paper investigates the addition of random edges to arbitrary dense graphs; in particular, we determine the number of random edges required to ensure various monotone properties including the...

240 JOURNAL OF GRAPH THEORY (2007)

Abstract: A subgraph of a graph G is called trivial if it is either a clique or an independent set. Let qðGÞ denote the maximum number of vertices in a trivial subgraph of G. Motivated by an open...

Joel Friedman, Andreas Goerdt, Michael Krivelevich

Recognizing more unsatisable random k-SAT instances eciently

Ron Holzman (2007)

graphs without short cycles (2007)

A graph G is called k-saturated, where k 3 is an integer, if G is K k

Noga Alon, Béla Bolloba S, Michael Krivelevich, Benny Sudakov E

Maximum cuts and judicious partitions in

It is shown that the chromatic number of any graph with maximum degree d in which the number of edges in the induced subgraph on the set of all neighbors of any vertex does not exceed d

Michael Krivelevich, Benny Sudakov, Van H. Vu, Nicholas C. Wormald

Let k be the asymptotic value of the independence number of the random graph G(n; p). We prove that if the edge probability p(n) satises p(n) n

Sharp thresholds for certain Ramsey properties of random graphs (2007)

We show that if the second largest absolute value of an eigenvalue of a d-regular graph G on n vertices is at most cd 3

Ehud Friedgut, Michael Krivelevich

In a series of papers culminating in [11] Rodl, Rucinski and others study the thresholds of Ramsey properties of random graphs i.e. for a given graph H, when does a random graph almost surely have...

Sharp threshold for network reliability (2007)

Sparse pseudo-random graphs are Hamiltonian (2007)

Given a graph G on n vertices with average degree d, form a random subgraph G p by choosing each edge of G independently with probability p. Strengthening a classical result of Margulis we prove that...

Choosability in random hypergraphs (2007)

In this paper we study Hamilton cycles in sparse pseudo-random graphs. We prove that if the second largest absolute value of an eigenvalue of a d-regular graph G on n vertices satises (log log n) 2...

The choice number of a hypergraph H = (V; E) is the least integer s for which for every family of color lists S = fS(v) : v 2 V g, satisfying jS(v)j = s for every v 2 V, there exists a choice...

We consider the following probabilistic model of a graph on n labeled vertices. First choose a random graph G(n; 1=2) and then choose randomly a subset Q of vertices of size k and force it to be a...

Michael Krivelevich, Benny Sudakov, Van H. Vu, Nicholas C. Wormald

Let k be the asymptotic value of the independence number of the random graph G(n; p). We prove that if the edge probability p(n) satises p(n) n

Michael Krivelevich, Benny Sudakov, Van H. Vu, Nicholas C. Wormald

Random d-regular graphs have been well studied when d is xed and the number of vertices goes to innity. We obtain results on many of the properties of a random d-regular graph when d = d(n) grows...

Noga Alon, Michael Krivelevich, Paul Seymour

It is shown that any k-critical graph with n vertices contains a cycle of length at least 2

U (2007)

Michael Krivelevich, Beverly Sackler, Faculty Exact Sciences

Almost perfect matchings in random uniform

Department of Mathematics, (2007)

Noga Alon, Haim Kaplan, Michael Krivelevich, Dahlia Malkhi

Abstract. In this paper, we provide a method to safely store a document in perhaps the most challenging settings, a highly decentralized replicated storage system where up to half of the storage...

mkrivel@math.ias.edu. Research supported by an IAS/DIMACS Postdoctoral (2007)

A graph G is k-critical if it has chromatic number k, but every proper subgraph of it is (k 1)-colorable. This paper is devoted to investigating the following question: for given k and n, what is the...

Hamilton Cycles in Random Subgraphs of Pseudo-Random Graphs Alan Frieze (2007)

(Extended abstract)

Given an r-regular graph G on n vertices with a Hamilton cycle, order its edges randomly and insert them one by one according to the chosen order, starting from the empty graph. We prove that if the...

-FREE SUBGRAPHS (2007)

for all (x 1; : : : ; xn) 2 S. The width of a function f j is dened as (2007)

Abstract. The main result of this paper is that for every 2 r and n suf-ciently large there exist graphs of order n, not containing a complete graph on s vertices, in which every relatively not too...

Ron Aharoni, Ron Holzman, Michael Krivelevich, Roy Meshulam

Abstract. In 1950 Bang proposed a conjecture which became known as \the plank conjecture": Suppose that a convex set S contained in the unit cube of

A lower bound for irredundant Ramsey (2007)

Sharp Thresholds for Ramsey Properties of Random Graphs. (2007)

numbers

Ehud Friedgut, Michael Krivelevich

In a series of papers culminating in [11] Rodl, Ruci'nski and others study the thresholds of Ramsey properties of random graphs and hypergraphs, i.e. for a given graph H, when does a random...

x (2007)

Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy

Let P be a property of graphs. An -test for P is a randomized algorithm which, given the ability to make queries whether a desired pair of vertices of an input graph G with n vertices are adjacent or...

Sparse pseudo-random graphs are Hamiltonian (2007)

In this paper we study Hamilton cycles in sparse pseudo-random graphs. We prove that if the second largest absolute value of an eigenvalue of a d-regular graph G on n vertices satises (log log n)

We consider the following probabilistic model of a graph on n labeled vertices. First choose a random graph G(n; 1=2) and then choose randomly a subset Q of vertices of size k and force it to be a...

Dimitris Achlioptas, Jeong Han Kim, Michael Krivelevich, Prasad Tetali

Approximating the independence number and the chromatic number in expected polynomial time

x (2007)

A 2-coloring of a hypergraph is a mapping from its vertex set to a set of two colors such that no edge is monochromatic. Let H = H(k; n; p) be a random k-uniform hypergraph on a vertex set V of...

) for every proper (2007)

Department of Mathematics, (2007)

graphs

The weighted set covering problem, restricted to the class of r-uniform hypergraphs, is considered. We propose a new approach, based on a recent result of Aharoni, Holzman and Krivelevich about the...

Noga Alon, Michael Krivelevich, Simon Litsyn

hashing and applications to digital ngerprinting

Hamilton Cycles in Random Subgraphs of Pseudo-Random Graphs Alan Frieze (2007)

Given an r-regular graph G on n vertices with a Hamilton cycle, order its edges randomly and insert them one by one according to the chosen order, starting from the empty graph. We prove that if the...

On the Probability of Independent Sets in Random Graphs (2007)

We show that if the second largest absolute value of an eigenvalue of a d-regular graph G on n vertices is at most cd 3

Michael Krivelevich, Benny Sudakov, Van H. Vu, Nicholas C. Wormald

Let k be the asymptotic value of the independence number of the random graph G(n; p). We prove that if the edge probability p(n) satis es p(n) n n then the probability that G(n; p) does not contain...

On the Probability of Independent Sets in Random Graphs (2007)

Michael Krivelevich, Benny Sudakov, Van H. Vu, Nicholas C. Wormald

Let k be the asymptotic value of the independence number of the random graph G(n, p). We prove that if the edge probability p(n) satisfies p(n) n -2/5 ln n then the probability that c, for some...

Bounding Ramsey numbers through large (2007)

Deviation Inequalities Michael, Michael Krivelevich

We develop a new approach for proving lower bounds for various Ramsey numbers, based on using large deviation inequalities. This approach enables us to obtain the bounds for the o-diagonal Ramsey );...

Covering Codes with Improved Density (2007)

Turán numbers of bipartite graphs and related Ramsey-type questions (2007)

We prove a general recursive inequality concerning (R), the asymptotic (worst) density of the best binary covering codes of radius R. In particular, this inequality implies that (R) e (R log R+ log...

Abraham D. Flaxman, Michael Krivelevich

For a graph H and an integer n, the Turan number ex(n; H) is the maximum possible number of edges in a simple graph on n vertices that contains no copy of H . H is r-degenerate if every subgraph of...

Alan Frieze (2007)

It is known [6] that if the edge costs of the complete graph K n are independent random variables, uniformly distributed between 0 and 1, then the expected cost of the minimum spanning tree is...

Almost universal graphs Alan Frieze (2007)

Vertex Percolation on Expander Graphs (2007)

We study the question as to when a random graph with n vertices and m edges contains a copy of almost all graphs with n vertices and cn=2 edges, c constant. We identify a "phase transition...

Ben-Shimon, Sonny, Krivelevich, Michael

We say that a graph $G=(V,E)$ on $n$ vertices is a $\beta$-expander for some constant $\beta>0$ if every $U\subseteq V$ of cardinality $|U|\leq \frac{n}{2}$ satisfies $|N_G(U)|\geq \beta|U|$ where...

Large nearly regular induced subgraphs (2007)

Alon, Noga, Krivelevich, Michael, Sudakov, Benny

For a real c \geq 1 and an integer n, let f(n,c) denote the maximum integer f so that every graph on n vertices contains an induced subgraph on at least f vertices in which the maximum degree is at...

Avoiding small subgraphs in Achlioptas processes (2007)

Krivelevich, Michael, Loh, Po-Shen, Sudakov, Benny

For a fixed integer r, consider the following random process. At each round, one is presented with r random edges from the edge set of the complete graph on n vertices, and is asked to choose one of...

Better Algorithms and Bounds for Directed Maximum Leaf Problems (2007)

Alon, Noga, Fomin, Fedor V., Gutin, Gregory, Krivelevich, Michael, Saurabh, Saket

The {\sc Directed Maximum Leaf Out-Branching} problem is to find an out-branching (i.e. a rooted oriented spanning tree) in a given digraph with the maximum number of leaves. In this paper, we...

Minors in expanding graphs (2007)

Krivelevich, Michael, Sudakov, Benny

Extending several previous results we obtained nearly tight estimates on the maximum size of a clique-minor in various classes of expanding graphs. These results can be used to show that graphs...

Embedding nearly-spanning bounded degree trees (2007)

Alon, Noga, Krivelevich, Michael, Sudakov, Benny

We derive a sufficient condition for a sparse graph G on n vertices to contain a copy of a tree T of maximum degree at most d on (1-\epsilon)n vertices, in terms of the expansion properties of G. As...

Parameterized Algorithms for Directed Maximum Leaf Problems (2007)

Alon, Noga, Fomin, Fedor, Gutin, Gregory, Krivelevich, Michael, Saurabh, Saket

We prove that finding a rooted subtree with at least $k$ leaves in a digraph is a fixed parameter tractable problem. A similar result holds for finding rooted spanning trees with many leaves in...

Why almost all k-colorable graphs are easy to color (2007)

Amin Coja-oghlan, Michael Krivelevich, Dan Vilenchik

Coloring a k-colorable graph using k colors (k ≥ 3) is a notoriously hard problem. Considering average case analysis allows for better results. In this work we consider the uniform distribution...

Better Algorithms and Bounds for Directed Maximum Leaf Problems (2007)

Noga Alon, Fedor V. Fomin, Gregory Gutin, Michael Krivelevich, Saket Saurabh

Abstract. The Directed Maximum Leaf Out-Branching problem is to find an out-branching (i.e. a rooted oriented spanning tree) in a given digraph with the maximum number of leaves. In this paper, we...

Why almost all k-CNF formulas are easy (2007)

Amin Coja-oghlan, Michael Krivelevich, Dan Vilenchik

Abstract. Finding a satisfying assignment for a k-CNF formula (k ≥ 3), assuming such exists, is a notoriously hard problem. In this work we consider the uniform distribution over satisfiable k-CNF...

Parameterized Algorithms for Directed Maximum Leaf Problems (2007)

Noga Alon, Fedor V. Fomin, Gregory Gutin, Michael Krivelevich, Saket Saurabh

Abstract. We prove that finding a rooted subtree with at least k leaves in a digraph is a fixed parameter tractable problem. A similar result holds for finding rooted spanning trees with many leaves...

Parameterized Algorithms for Directed Maximum Leaf Problems (2007)

Noga Alon, Fedor V. Fomin, Gregory Gutin, Michael Krivelevich, Saket Saurabh

We prove that finding a rooted subtree with at least k leaves in a directed graph is a fixed parameter tractable problem. A similar result holds for finding rooted spanning trees with many leaves in...

Approximation Algorithms and Hardness Results for Cycle Packing Problems (2007)

Michael Krivelevich, Zeev Nutov, Mohammad R. Salavatipour, Jacques Yuster, Raphael Yuster

Vertex Percolation on Expander Graphs (2007)

Sonny Ben-shimon, Michael Krivelevich

We say that a graph G = (V, E) on n vertices is a β-expander for some constant β> 0 if every U ⊆ V of cardinality |U | ≤ n 2 satisfies |NG(U) | ≥ β|U | where NG(U) denotes the...

On unbiased games on random graphs (2007)

Dan Hefetz, Michael Krivelevich, Tibor Szabó, H ⊆h

We study unbiased Maker-Breaker positional games played on the edges of the random graph G(n, p). As the main result of the paper, we prove a conjecture from [18], that the property that Maker is...

Fast winning strategies in positional games (2007)

Parameterized Algorithms for Directed Maximum Leaf Problems (2007)

For the unbiased Maker-Breaker game, played on the hypergraph H, let τM(H) be the smallest integer t such that Maker can win the game within t moves (if the game is a Breaker’s win then set τM(H)...

Noga Alon, Fedor V. Fomin, Gregory Gutin, Michael Krivelevich, Saket Saurabh, Royal Holloway

D is an out-tree if T is an oriented tree with only one vertex s of in-degree zero (called the root). The vertices of

Parameterized Algorithms for Directed Maximum Leaf Problems (2007)

Noga Alon, Noga Alon, Fedor V. Fomin, Fedor V. Fomin, Gregory Gutin, Gregory Gutin, ...

We prove that finding a rooted subtree with at least k leaves in a digraph is a fixed parameter tractable problem. A similar result holds for finding rooted spanning trees with many leaves in...

Small sample spaces cannot fool low degree polynomials Extended Abstract (2007)

Noga Alon, Ido Ben-eliezer, Michael Krivelevich

A distribution D on a set S ⊂ {0, 1} N ɛ-fools polynomials of degree at most d in N variables over Z2 if for any such polynomial P, the probability that P (x) vanishes when x is chosen according...

Better Algorithms and Bounds for Directed Maximum Leaf Problems (2007)

Noga Alon, Fedor V. Fomin, Gregory Gutin, Michael Krivelevich, Saket Saurabh, Royal Holloway

Abstract. The Directed Maximum Leaf Out-Branching problem is to find an out-branching (i.e. a rooted oriented spanning tree) in a given digraph with the maximum number of leaves. In this paper, we...

Equitable coloring of random graphs (2007)

Michael Krivelevich, Balázs Patkós

An equitable coloring of a graph is a proper vertex coloring such that the sizes of any two color classes differ by at most one. The least positive integer k for which there exists an equitable...

Why almost all k-colorable graphs are easy to color (2007)

Amin Coja-oghlan, Michael Krivelevich, Dan Vilenchik

Abstract Coloring a k-colorable graph using k colors (k> = 3) is a notoriously hard problem. Consideringaverage case analysis allows for better results. In this work we consider the uniform...

Hamilton cycles in highly connected and expanding graphs (2006)

Hefetz, Dan, Krivelevich, Michael, Szabo, Tibor

In this paper we prove a sufficient condition for the existence of a Hamilton cycle, which is applicable to a wide variety of graphs, including relatively sparse graphs. In contrast to previous...

Solving random satisfiable 3CNF formulas in expected polynomial time (2006)

Michael Krivelevich, Dan Vilenchik

We present an algorithm for solving 3SAT instances. Several algorithms have been proved to work whp (with high probability) for various SAT distributions. However, an algorithm that works whp has a...

Pseudo-random graphs (2006)

On the chromatic number of random graphs with a fixed (2006)

Random graphs have proven to be one of the most important and fruitful concepts in modern Combinatorics and Theoretical Computer Science. Besides being a fascinating study subject for their own sake,...

Alan Frieze, Michael Krivelevich, Cliff Smyth

degree sequence

Solving random satisfiable 3CNF formulas in expected polynomial time (2006)

Michael Krivelevich, Dan Vilenchik

1 Introduction and Results 1.1 The Planted 3SAT Distribution A 3CNF for-mula over the variables x1, x2,..., xn is a conjunction ofclauses C1, C2,..., Cm where each clause is a disjunctionof three...

Testing triangle-freeness in general graphs (2006)

Noga Alon, Tali Kaufman, Michael Krivelevich, Dana Ron

In this paper we consider the problem of testing whether a graph is triangle-free, and more generally, whether it is H-free, for a fixed subgraph H. The algorithm should accept graphs that are...

Testing triangle-freeness in general graphs (2006)

Noga Alon, Tali Kaufman, Michael Krivelevich, Dana Ron

In this paper we consider the problem of testing whether a graph is triangle-free, and more generally, whether it is H-free, for a fixed subgraph H. The algorithm should accept graphs that are...

of (2006)

Nurit Gazit, Michael Krivelevich

the asymptotic value of the choice number

Colouring complete bipartite graphs from random lists, Random Structures and Algorithms 29 (2006)

Michael Krivelevich, Asaf Nachmias

Abstract Let Kn,n be the complete bipartite graph with n vertices in each side. For each vertex drawuniformly at random a list of size k from a base set S of size s = s(n). In this paper we...

Semirandom models as benchmarks for coloring algorithms (2006)

Michael Krivelevich, Dan Vilenchik

Abstract Semirandom models generate problem instances by blend-ing random and adversarial decisions, thus intermediating between the worst-case assumptions that may be overly pes-simistic in many...

Random regular graphs of non-constant degree: edge distribution and applications (2006)

Sonny Ben-shimon, Michael Krivelevich

edges and applications

On Fractional K-Factors of Random Graphs (2006)

Simha Haber, Michael Krivelevich

Random regular graphs of non-constant degree: edge distribution and applications (2006)

Sonny Ben-shimon, Michael Krivelevich

In this work we show that with high probability the chromatic number of a graph sampled from the random regular graph model Gn,d for d = o(n 1/5) is concentrated in two consecutive values, thus...

Colouring complete bipartite graphs from random lists (2005)

Krivelevich, Michael, Nachmias, Asaf

Let $K_{n,n}$ be the complete bipartite graph with $n$ vertices in each side. For each vertex draw uniformly at random a list of size $k$ from a base set $S$ of size $s=s(n)$. In this paper we...

Colouring powers of cycles from random lists (2005)

Krivelevich, Michael, Nachmias, Asaf

Let $C_n^k$ be the $k$-th power of a cycle on $n$ vertices (i.e. the vertices of $C_n^k$ are those of the $n$-cycle, and two vertices are connected by an edge if their distance along the cycle is at...

Random regular graphs of non-constant degree: Concentration of the chromatic number (2005)

Ben-Shimon, Sonny, Krivelevich, Michael

In this work we show that with high probability the chromatic number of a graph sampled from the random regular graph model $\Gnd$ for $d=o(n^{1/5})$ is concentrated in two consecutive values, thus...

The isoperimetric constant of the random graph process (2005)

Benjamini, Itai, Haber, Simi, Krivelevich, Michael, Lubetzky, Eyal

The isoperimetric constant of a graph $G$ on $n$ vertices, $i(G)$, is the minimum of $\frac{|\partial S|}{|S|}$, taken over all nonempty subsets $S\subset V(G)$ of size at most $n/2$, where $\partial...

Pseudo-random graphs (2005)

Krivelevich, Michael, Sudakov, Benny

Random graphs have proven to be one of the most important and fruitful concepts in modern Combinatorics and Theoretical Computer Science. Besides being a fascinating study subject for their own sake,...

Almost universal graphs (2005)

Almost universal graphs (2005)

We study the question as to when a random graph with n vertices and m edges contains a copy of almost all graphs with n vertices and cn/2 edges, c constant. We identify a ”phase transition ” at c...

Bart- Moe games, JumbleG and Discrepancy (2005)

We study the question as to when a random graph with n vertices and m edges contains a copy of almost all graphs with n vertices and cn/2 edges, c constant. We identify a ”phase transition ” at c...

TEL AVIV UNIVERSITY (2005)

Let A and B be hypergraphs with a common vertex set V. In a (p, q, A ∪ B) Bart-Moe game, the players take turns selecting previously unclaimed vertices of V. The game ends when every vertex has...

The Raymond, Beverly Sackler, Faculty Exact Sciences, Tali Kaufman, Under Professors, Noga Alon, ...

Property Testing is nowadays one of the central fields in Theoretical Computer Science. This concept played a major role in the proof of the celebrated PCP theorem. A typical task in Property Testing...

On the asymptotic value of the choice number of complete multi-partite graphs (2004)

Gazit, Nurit, Krivelevich, Michael

We calculate the asymptotic value of the choice number of complete multi-partite graphs.

A Lower Bound on the Density of Sphere Packings via Graph Theory (2004)

Krivelevich, Michael, Litsyn, Simon, Vardy, Alexander

Using graph-theoretic methods we give a new proof that for all sufficiently large $n$, there exist sphere packings in $\R^n$ of density at least $cn2^{-n}$, exceeding the classical Minkowski bound by...

Tight Bounds for Testing Bipartiteness in General Graphs (2004)

Tali Kaufman, Michael Krivelevich, Dana Ron

In this paper we consider the problem of testing bipartiteness of general graphs. The problem has previously been studied in two models, one most suitable for dense graphs, and one most suitable for...

The game of JumbleG (2004)

Alan Frieze, Michael Krivelevich, Oleg Pikhurko, Tibor Szabó

JumbleG is a Maker-Breaker game. Maker and Breaker take turns in choosing edges from the complete graph K n . Maker's aim is to choose what we call an -regular graph (that is, the minimum degree...

Testing Reed Muller Codes \Lambda (2004)

Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron

Abstract A code is locally testable if there is a way to indicate with high probability that a vector is far enough from any codeword by accessing only a very small number of the vector's bits....

A Lower Bound on the Density ofSphere Packings via Graph Theory (2004)

A lower bound on the density of sphere packings via graph theory (2004)

Abstract Using graph-theoretic methods we give a new proof that for all sufficiently large n, thereexist sphere packings in Rn of density at least cn2\Gamma n exceeding the classical Minkowskibound...

Michael Krivelevich, Simon Litsyn, Alexander Vardy

A lower bound on the density of sphere packings via graph theory (2004)

Krivelevich, Michael, Litsyn, Simon, Vardy, Alexander

Using graph-theoretic methods we give a new proof that for all sufficiently large n, there exist sphere packings in ℝn of density at least cn2−n exceeding the classical Minkowski bound by a...

on distance distributions in codes of given size (2003)

Michael Krivelevich, Simon Litsyn

We prove a new upper bound on the possible distance distribution of a code of a given size. The main instrument of the proof is the Beckner inequality from Harmonic Analysis. We also show that the...

The largest eigenvalue of sparse random graphs (2003)

On packing Hamilton Cycles in ε-Regular Graphs (2003)

We prove that for all values of the edge probability p(n) the largest eigenvalue of a random graph G(n; p) satises almost surely: 1 (G) = (1 + o(1)) maxf p ; npg, where is a maximal degree of G, and...

Addendum to "Scalable Secure Storage when Half the System is (2003)

A graph G = (V; E) on n vertices is (; )-regular if its minimal degree is at least n, and for every pair of disjoint subsets S; T V of cardinalities at least n, the number of edges e(S; T ) between S...

Faulty Noga Alon, Noga Alon, Haim Kaplan, Michael Krivelevich, Dahlia Malkhi, Julien Stern

Introduction. We consider the following problem. A file of size s bits is to be stored on n disks. Our failure model assumes that a potentially malicious adversary may choose after the file is stored...

The Largest Eigenvalue of Sparse Random Graphs (2003)

The Largest Eigenvalue of Sparse Random Graphs (2003)

this paper we study eigenvalues of random graphs. The random graph G(n, p)isthe discrete probability space composed of all labelled graphs on the vertices {1,..

doi:10.1017/S0963548305007017 Printed in the United Kingdom MaxCut in H-Free Graphs (2003)

We prove that for all values of the edge probability p(n) the largest eigenvalue of the random graph G(n; p) satis es almost surely: 1 (G) = (1 + o(1)) maxf ; npg, where is the maximum degree of G,...

The Emergence of a Giant Component in Random Subgraphs of Pseudo-Random Graphs (2003)

For a graph G, letf(G) denote the maximum number of edges in a cut of G. For an integer m and for a fixed graph H, letf(m, H) denote the minimum possible cardinality of f(G), as G ranges over all...

Alan Frieze, Michael Krivelevich, Ryan Martin

Let G be a d-regular graph G on n vertices. Suppose that the adjacency matrix of G is such that the eigenvalue which is second largest in absolute value satis es = o(d).

Generalized Hashing and Parent-Identifying Codes (2003)

Noga Alon, Gerard Cohen, Michael Krivelevich, Simon Litsyn

Let C be a code of length n over an alphabet of q letters. For a pair of integers 2 t < u, C is (t; u)-hashing if for any two subsets T ; U C, satisfying T U , jT j = t, jU j = u, there is a...

Tight Bounds for Testing Bipartiteness in General Graphs (2003)

Tali Kaufman, Michael Krivelevich, Dana Ron

In this paper we consider the problem of testing bipartiteness of general graphs. The problem has previously been studied in two models, one most suitable for dense graphs, and one most suitable for...

Induced Subgraphs of Prescribed Size (2003)

Noga Alon Michael, Michael Krivelevich, Benny Sudakov

A subgraph of a graph G is called trivial if it is either a clique or an independent set. Let q(G) denote the maximum number of vertices in a trivial subgraph of G. Motivated by an open problem of...

On packing Hamilton Cycles in ε-regular Graphs (2003)

Testing Low-Degree Polynomials over GF(2) (2003)

A graph G = (V; E) on n vertices is (; )-regular if its minimal degree is at least n, and for every pair of disjoint subsets S; T V of cardinalities at least n, the number of edges e(S; T ) between S...

Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron

We describe an efficient randomized algorithm to test if a given binary function f : f0; 1g ! f0; 1g is a low-degree polynomial (that is, a sum of low-degree monomials). For a given integer k 1 and a...

Adding Random Edges to Dense Graphs (2003)

Tom Bohman, Alan Frieze, Michael Krivelevich, Ryan Martin

This paper investigates the addition of random edges to arbitrary dense graphs; in particular, we determine the number of random edges required to ensure various monotone properties including the...

Testing Low-Degree Polynomials over GF(2) (2003)

Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron

We describe an efficient randomized algorithm to test if a given binary function f : f0; 1g ! f0; 1g is a low-degree polynomial (that is, a sum of low-degree monomials). For a given integer k 1 and a...

Two-coloring random hypergraphs (2002)

Dimitris Achlioptas, Jeong Han Kim, Michael Krivelevich

A 2-coloring of a hypergraph is a mapping from its vertex set to a set of two colors such that no edge is monochromatic. Let H = H(k;n; p) be a random k-uniform hypergraph on a vertex set V of...

Deciding k-colorability in expected polynomial time (2002)

Upper bounds on the rate of LDPC codes (2002)

For every xed k 3 we describe an algorithm for deciding k-colorability, whose expected running time in polynomial in the probability space G(n; p) of random graphs as long as the edge probability p =...

David Burshtein, Michael Krivelevich, Simon Litsyn, Gadi Miller

We derive upper bounds on the rate of low density parity check (LDPC) codes for which reliable communication is achievable. We rst generalize Gallager's bound to a general binaryinput...

Sparse graphs usually have exponentially many optimal colorings (2002)

Sparse Graphs Usually Have Exponentially Many Optimal Colorings (2002)

A proper coloring of a graph G = (V; E) is called optimal if the number of colors used is the minimal possible one, i.e., it coincides with the chromatic number of G. We investigate a typical...

Two-coloring Random Hypergraphs (2002)

A proper coloring of a graph G = (V; E) is called optimal if the number of colors used is the minimal possible; i.e., it coincides with the chromatic number of G.

Dimitris Achlioptas, Jeong Han Kim, Michael Krivelevich, Prasad Tetali

A 2-coloring of a hypergraph is a mapping from its vertex set to a set of two colors such that no edge is monochromatic. Let H = H(k;n; p) be a random k-uniform hypergraph on a vertex set V of...

Sparse Graphs Usually Have Exponentially Many Optimal Colorings (2002)

Coloring Random Graphs - an Algorithmic Perspective (2002)

A proper coloring of a graph G =(V,E) is called optimal if the number of colors used is the minimal possible; i.e., it coincides with the chromatic number of G.

Sparse Pseudo-Random Graphs Are Hamiltonian (2002)

Algorithmic Graph Coloring and Random Graphs have long become one of the most prominent branches of Combinatorics and Combinatorial Optimization. It is thus very natural to expect that their mixture...

On the Probability of Independent Sets in Random Graphs (2002)

In this article we study Hamilton cycles in sparse pseudo-random graphs. We prove that if the second largest absolute value λ of an eigenvalue of a d-regular graph G on n vertices...

Michael Krivelevich, Benny Sudakov, Van H. Vu, Vanh. Vu, Nicholas C. Wormald

Let k be the asymptotic value of the independence number of the random graph G(n, p). We prove that if the edge probability p(n) satisfies p(n) ## n n then the probability that G(n, p) does not...

DOI: 10.1017/S0963548303005741 Printed in the United Kingdom Turán Numbers of Bipartite Graphs and Related Ramsey-Type Questions (2002)

Two-coloring random hypergraphs (2002)

For a graph H and an integer n, theTurán number ex(n, H) isthemaximum possible number of edges in a simple graph on n vertices that contains no copy of H. H is rdegenerate if every one of its...

Dimitris Achlioptas, Jeong Han Kim, Michael Krivelevich, Prasad Tetali

ABSTRACT: A 2-coloring of a hypergraph is a mapping from its vertex set to a set of two colors such that no edge is monochromatic. Let H = H�k � n � p � be a random k-uniform hypergraph on a...

THe largest eigenvalue of sparse random graphs (2001)

Krivelevich, Michael, Sudakov, Benny

We prove that for all values of the edge probability p(n) the largest eigenvalue of a random graph G(n,p) satisfies almost surely: \lambda_1(G)=(1+o(1))max{\sqrt{\Delta},np}, where \Delta is a...

in (2001)

Approximating coloring and maximum independent sets in 3-uniform hypergraphs (2001)

the independence number and the chromatic number

Michael Krivelevich, Ram Nathaniel, Benny Sudakov

hypergraphs

Approximating coloring and maximum independent sets in 3-uniform hypergraphs (2001)

Michael Krivelevich, Ram Nathaniel, Benny Sudakov

We discuss approximation algorithms for the coloring problem and the maximum independent set problem in 3-uniform hypergraphs. An algorithm for coloring ˜ 1�5 3-uniform 2-colorable hypergraphs in...

COMBINATORICA Bolyai Society – Springer-Verlag Combinatorica 24 (3) (2004) 403–426 TRIANGLE FACTORS IN SPARSE PSEUDO-RANDOM GRAPHS (2001)

Michael Krivelevich, Benny Sudakov, Tibor Szab Ó

The goal of the paper is to initiate research towards a general, Blow-up Lemma type embedding statement for pseudo-random graphs with sublinear degrees. In particular, we show that if the second...

On the concentration of eigenvalues of random symmetric matrices (2000)

Krivelevich, Michael, Vu, Van H.

We prove that few largest (and most important) eigenvalues of random symmetric matrices of various kinds are very strongly concentrated. This strong concentration enables us to compute the means of...

Scalable Secure Storage when Half the System Is Faulty (2000)

Noga Alon, Haim Kaplan, Michael Krivelevich, Dahlia Malkhi, Julien Stern

In this paper, we provide a method to safely store a document in perhaps the most challenging settings, a highly decentralized replicated storage system where up to half of the storage servers may...

Scalable Secure Storage when Half the System Is Faulty (2000)

Noga Alon, Haim Kaplan, Michael Krivelevich, Dahlia Malkhi, Julien Stern

In this paper, we provide a method to safely store a document in perhaps the most challenging settings, a highly decentralized replicated storage system where up to half of the storage servers may...

On the concentration of eigenvalues of random symmetric matrices (2000)

Noga Alon, Michael Krivelevich, Van H. Vu

It is shown that for every 1 ≤ s ≤ n, the probability that the s-th largest eigenvalue of a random symmetric n-by-n matrix with independent random entries of absolute value at most 1 deviates...

On the concentration of eigenvalues of random symmetric matrices (2000)

Noga Alon, Michael Krivelevich, Van H. Vu

It is shown that for every 1 ≤ s ≤ n, the probability that the s-th largest eigenvalue of a random symmetric n-by-n matrix with independent random entries of absolute value at most 1 deviates...

Scalable Secure Storage when Half the System Is Faulty (2000)

Noga Alon, Haim Kaplan, Michael Krivelevich, Dahlia Malkhi, Julien Stern

In this paper, we provide a method to safely store a document in perhaps the most challenging settings, a highly decentralized replicated storage system where up to half of the storage servers may...

Scalable Secure Storage when Half the System Is Faulty (2000)

Noga Alon, Haim Kaplan, Michael Krivelevich, Dahlia Malkhi, Julien Stern

In this paper, we provide a method to safely store a document in perhaps the most challenging settings, a highly decentralized replicated storage system where up to half of the storage servers may...

On the concentration of eigenvalues of random symmetric matrices (2000)

Noga Alon, Michael Krivelevich, Van H. Vu

It is shown that for every 1 s n, the probability that the s-th largest eigenvalue of a random symmetric n-by-n matrix with independent random entries of absolute value at most 1 deviates from its...

DOI: 10.1017/S0963548302005199 Printed in the United Kingdom A Sharp Threshold for Network Reliability (2000)

Testing k-colorability (1999)

Given a graph G on n vertices with average degree d, form a random subgraph Gp by choosing each edge of G independently with probability p. Strengthening a classical result of Margulis we prove that,...

Regular Languages are Testable with a Constant Number of Queries (1999)

Let G be a graph on n vertices and suppose that at least n 2 edges have to be deleted from it to make it k-colorable. It is shown that in this case most induced subgraphs of G on ck ln k= 2 vertices...

Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy

We continue the study of combinatorial property testing, initiated by Goldreich, Goldwasser and Ron in [7]. The subject of this paper is testing regular languages. Our main result is as follows. For...

Efficient testing of large graphs (1999)

Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy

Let P be a property of graphs. An -test for P is a randomized algorithm which, given the ability to make queries whether a desired pair of vertices of an input graph G with n vertices are adjacent or...

Testing k-colorability (1999)

Regular Languages are Testable with a Constant Number of Queries (1999)

Let G be a graph on n vertices and suppose that at least n 2 edges have to be deleted from it to make it k-colorable. It is shown that in this case most induced subgraphs of G on ck ln k= 2 vertices...

Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy

We continue the study of combinatorial property testing, initiated by Goldreich, Goldwasser and Ron in [7]. The subject of this paper is testing regular languages. Our main result is as follows. For...

Regular Languages are Testable with a Constant Number of Queries (1999)

Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy

We continue the study of combinatorial property testing, initiated by Goldreich, Goldwasser and Ron in [7]. The subject of this paper is testing regular languages. Our main result is as follows. For...

Regular Languages are Testable with a Constant Number of Queries (1999)

Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy

We continue the study of combinatorial property testing, initiated by Goldreich, Goldwasser and Ron in [7]. The subject of this paper is testing regular languages. Our main result is as follows. For...

Coloring Graphs with Sparse Neighborhoods (1999)

Efficient testing of large graphs (1999)

INTRODUCTION The chromatic number /(G) of a graph G is the minimum number of colors required to color all its vertices so that adjacent vertices get distinct colors. It is easy and well known that if...

Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy

Let P be a property of graphs. An ɛ-test for P is a randomized algorithm which, given the ability to make queries whether a desired pair of vertices of an input graph G with n vertices are adjacent...

Testing k-colorability (1999)

Regular Languages are Testable with a Constant Number of Queries (1999)

Let G be a graph on n vertices and suppose that at least ɛn 2 edges have to be deleted from it to make it k-colorable. It is shown that in this case most induced subgraphs of G on ck ln k/ɛ 2...

Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy

We continue the study of combinatorial property testing, initiated by Goldreich, Goldwasser and Ron in [7]. The subject of this paper is testing regular languages. Our main result is as follows. For...

The choice number of random bipartite graphs, lecture at (1998)

Coloring random graphs (1998)

Abstract. A random bipartite graph G � n � n � p � is obtained by taking two disjoint subsets of vertices A and B of cardinality n each, and by connecting each pair of vertices a � A and b...

The choice number of random bipartite graphs, lecture at (1998)

We present a randomized polynomial time algorithm that colors almost every graph on n vertices in n=(log 2 n + c p log 2 n) colors for every positive constant c.

The Chromatic Numbers of Random Hypergraphs (1998)

A random bipartite graph G(n; n; p) is obtained by taking two disjoint subsets of vertices A and B of cardinality n each, and by connecting each pair of vertices a 2 A and b 2 B by an edge randomly...

Approximate Coloring of Uniform Hypergraphs (1998)

: For a pair of integers 1### r, the #-chromatic number of an r-uniform Z. hypergraph H# V, E is the minimal k, for which there exists a partition of V into subsets ## T,...,T such that e#T ## for...

Michael Krivelevich Benny, Michael Krivelevich, Benny Sudakov

We consider an algorithmic problem of coloring r-uniform hypergraphs. The problem of finding the exact value of the chromatic number of a hypergraph is known to be NP -hard, so we discuss approximate...

Coloring Random Graphs (1998)

Finding a Large Hidden Clique in a Random Graph (1998)

We present a randomized polynomial time algorithm that colors almost every graph on n vertices in n/(log 2 n + c # log 2 n) colors for every positive constant c. Ó 1998 Published by Elsevier Science...

Approximate Coloring of Uniform Hypergraphs (1998)

: We consider the following probabilistic model of a graph on n labeled vertices. Z. First choose a random graph Gn,1#2 , and then choose randomly a subset Q of vertices of size k and force it to be...

Coloring Graphs With Sparse Neighborhoods (1998)

We consider an algorithmic problem of coloring r-uniform hypergraphs. The problem of finding the exact value of the chromatic number of a hypergraph is known to be NP -hard, so we discuss approximate...

By Noga Alon, Noga Alon, Michael Krivelevich, Benny Sudakov

It is shown that the chromatic number of any graph with maximum degree d in which the number of edges in the induced subgraph on the set of all neighbors of any vertex does not exceed d 2 =f is at...

and (1998)

The Chromatic Numbers of Random Hypergraphs (1998)

It is shown that the chromatic number of any graph with maximum degree d in which the number of edges in the induced subgraph on the set of all neighbors of any vertex does not exceed d 2 f is at...

The chromatic numbers of random hypergraphs (1998)

For a pair of integers 1 < r, the -chromatic number of an r-uniform hypergraph H = (V; E) is the minimal k, for which there exists a partition of V into subsets T 1 ; : : : ; T k such that je \ T...

Finding a large hidden clique in a random graph (1998)

ABSTRACT: For a pair of integers 1��r, the �-chromatic number of an r-uniform hypergraph H � Ž V, E. is the minimal k, for which there exists a partition of V into subsets T,...,T such...

Subgraphs with a large cochromatic number (1997)

ABSTRACT: We consider the following probabilistic model of a graph on n labeled vertices. First choose a random graph Gn,1�2 Ž., and then choose randomly a subset Q of vertices of size k and force...

The concentration of the chromatic number of random graphs, Combinatorica 17 (1997)

The cochromatic number of a graph G = (V, E) is the smallest number of parts in a partition of V in which each part is either an independent set or induces a complete subgraph. We show that if the...

Subgraphs with a large cochromatic number (1997)

We prove that for every constant> 0 the chromatic number of the random graph G(n; p) with p = n

Triangle factors in random graphs (1997)

The cochromatic number of a graph G = (V; E) is the smallest number of parts in a partition of V in which each part is either an independent set or induces a complete subgraph. We show that if the...

Constructive bounds for a Ramsey-type problem (1997)

For a graph G = (V; E) on n vertices, where 3 divides n, a triangle factor is a subgraph of G, consisting of n=3 vertex disjoint triangles (complete graphs on three vertices). We discuss the problem...

Subgraphs with a Large Cochromatic Number (1997)

For every xed integers r; s satisfying 2 r there exists some = (r; s)> 0 for which we construct explicitly an innite family of graphs H r;s;n, where H r;s;n has n vertices, contains no clique on s...

An Improved Bound on the Minimal Number of Edges in Color-Critical Graphs (1997)

: The cochromatic number of a graph G =(V,E) is the smallest number of parts in a partition of V in which each part is either an independent set or induces a complete subgraph. We show that if the...

Constructive bounds for a Ramsey-type problem (1997)

It is proven that for k # 4 and n>kevery k-color-critical graph on n vertices has at least # k-1 2 + k-3 2(k 2 -2k-1) # n edges, thus improving a result of Gallai from 1963. A graph G is...

The Chromatic Numbers of Random Hypergraphs (1997)

For every fixed integers r; s satisfying 2 r ! s there exists some ffl = ffl(r; s) ? 0 for which we construct explicitly an infinite family of graphs H r;s;n , where H r;s;n has n vertices, contains...

Michael Krivelevich, Beverly Sackler, Faculty Exact Sciences, Benny Sudakov

For a pair of integers 1 fl ! r, the fl-chromatic number of an r-uniform hypergraph H = (V; E) is the minimal k, for which there exists a partition of V into subsets T 1 ; : : : ; T k such that je...

COMBINATORICA Bolyai Society – Springer-Verlag COMBINATORICA 19 (4) (1999) 453–472 LIST COLORING OF RANDOM AND PSEUDO-RANDOM GRAPHS (1997)

Subgraphs with a large cochromatic number (1997)

The choice number of a graph G is the minimum integer k such that for every assignment of asetS(v) ofkcolors to every vertex v of G, there is a proper coloring of G that assigns to each vertex v a...

On k-saturated graphs with restrictions on the degrees (1996)

Abstract: The cochromatic number of a graph G =(V,E) is the smallest number of parts in a partition of V in which each part is either an independent set or induces a complete subgraph. We show that...

Noga Alon, Paul Erdős, Ron Holzman, Michael Krivelevich

A graph G is called k-saturated, where k ≥ 3 is an integer, if G is K k-free but the addition of any edge produces a K k (we denote by K k a complete graph on k vertices). We investigate...

On a theorem of Lovasz on covers in r-partite hypergraphs (1996)

Ron Aharoni, Ron Holzman, Michael Krivelevich

(H) r=2 for every r-partite hypergraph H (where and denote the covering number and fractional covering number respectively). Here it is shown that the same upper bound is valid for a more general...

Perfect fractional matchings in random hypergraphs, Random Structures and Algorithms 9 (1996)

Triangle Factors in Random Graphs (1996)

Given an r-uniform hypergraph H = (V; E) on jV j = n vertices, a real-valued function f: E! R is called a perfect fractional matching if P v2e f(e) 1 for all v 2 V and

Michael Krivelevich, Raymond And Beverly Sackler

For a graph G = (V; E) on n vertices, where 3 divides n, a triangle factor is a subgraph of G, consisting of n=3 vertex disjoint triangles (complete graphs on three vertices). We discuss the problem...

On the edge distribution in triangle-free graphs (1995)

Explicit Construction of (1991)

Abstract. Two problems on the edge distribution in triangle-free graphs are considered: 1) Given an 0 1. Find the largest = () such that for innitely many n there exists a triangle-free graph G on n...

Random regular graphs of high degree (1982)

bounds for a Ramsey-type problem

Michael Krivelevich, Benny Sudakov, Van H. Vu, Nicholas C. Wormald

ABSTRACT: Random d-regular graphs have been well studied when d is fixed and the number of vertices goes to infinity. We obtain results on many of the properties of a random d-regular graph when d =...

Efficient Testing of Large Graphs

Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy

Let P be a property of graphs. An ffl-test for P is a randomized algorithm which, given the ability to make queries whether a desired pair of vertices of an input graph G with n vertices are adjacent...

An Improved Bound on the Minimal Number of Edges in Color-Critical Graphs

Michael Krivelevich School, Michael Krivelevich

It is proven that for k # 4 and n > k every k-color-critical graph on n vertices has at least # k-1 2 + k-3 2(k 2 -2k-1) # n edges, thus improving a result of Gallai from 1963. A graph G is...

List Coloring of Random and Pseudo-Random Graphs

Random Regular Graphs of High Degree

The choice number of a graph G is the minimum integer k such that for every assignment of a set S(v) of k colors to every vertex v of G, there is a proper coloring of G that assigns to each vertex v...

Michael Krivelevich, Benny Sudakov, Van H. Vu, Nicholas C. Wormald

Random d-regular graphs have been well studied when d is fixed and the number of vertices goes to infinity. We obtain results on many of the properties of a random d-regular graphs when d = d(n)...

Coloring Graphs with Sparse Neighborhoods

It is shown that the chromatic number of any graph with maximum degree d in which the number of edges in the induced subgraph on the set of all neighbors of any vertex does not exceed d 2 =f is at...

Pseudo-Random Graphs

The Choice Number of Dense Random Graphs

this paper and to make it more coherent, usually the parameters are denoted (v; k; ; )). Two simple examples of strongly regular graph are the pentagon C 5 that has parameters (5; 2; 0; 1), and the...

Maximum Cuts and Judicious Partitions in Graphs without Short Cycles

We prove that if the edge probability p(n) satis es n p(n) 3=4, where 0 < < 1=4 is a constant, then the choice number and the chromatic number of the random graph G(n; p) are almost surely...

Noga Alon, Bela Bollobas, Michael Krivelevich, Benny Sudakov

We consider the bipartite cut and the judicious partition problems in graphs of girth at least 4. For the bipartite cut problem we show that every graph G with m edges, whose shortest cycle has...

List Coloring of Random and Pseudo-Random Graphs