Benny Sudakov

Ramsey games with giants (2009)

We describe a simple and yet surprisingly powerful probabilistic technique which shows how to find in a dense graph a large subset of vertices in which all (or almost all) small subsets have many...

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...

An improved bound for the stepping-up lemma (2009)

Decompositions into subgraphs of small diameter (2009)

The partition relation N \to (n)_{\ell}^k means that whenever the k-tuples of an N-element set are \ell-colored, there is a monochromatic set of size n, where a set is called monochromatic if all its...

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

We investigate decompositions of a graph into a small number of low diameter subgraphs. Let P(n,\epsilon,d) be the smallest k such that every graph G=(V,E) on n vertices has an edge partition E=E_0...

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...

Paths and stability number in digraphs (2009)

Hamiltonicity thresholds in Achlioptas processes (2009)

The Gallai-Milgram theorem says that the vertex set of any digraph with stability number k can be partitioned into k directed paths. In 1990, Hahn and Jackson conjectured that this theorem is best...

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)...

Density (2009)

On the random satisfiable process (2009)

theorems for bipartite graphs and related Ramsey-type results

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...

Discrete Kakeya-type problems and small bases (2009)

Noga Alon, Boris Bukh, Benny Sudakov

A subset U of a group G is called k-universal if U contains a translate of every k-element subset of G. We give several nearly optimal constructions of small k-universal sets, and use them to resolve...

LARGE NEARLY REGULAR INDUCED SUBGRAPHS ∗ (2009)

RAMSEY-TYPE PROBLEM FOR AN ALMOST MONOCHROMATIC (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...

Hypergraph Ramsey numbers (2009)

Abstract. In this short note we prove that there is a constant c such that every k-edge-coloring of the complete graph Kn with n ≥ 2 ck contains a K4 whose edges receive at most two colors. This...

David Conlon, Jacob Fox, Benny Sudakov

The Ramsey number rk(s, n) is the minimum N such that every red-blue coloring of the k-tuples of an N-element set contains either a red set of size s or a blue set of size n, where a set is called...

Ramsey numbers of sparse hypergraphs (2009)

David Conlon, Jacob Fox, Benny Sudakov

We give a short proof that any k-uniform hypergraph H on n vertices with bounded degree ∆ has Ramsey number at most c(∆, k)n, for an appropriate constant c(∆, k). This result was recently...

Two (2009)

Pancyclicity of Hamiltonian and highly connected graphs (2009)

remarks on the Burr-Erdős conjecture

Keevash, Peter, Sudakov, Benny

A graph G on n vertices is Hamiltonian if it contains a cycle of length n and pancyclic if it contains cycles of length $\ell$ for all $3 \le \ell \le n$. Write $\alpha(G)$ for the independence...

Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality (2009)

Elchanan Mossel, Oded Regev, Jeffrey E. Steif, Benny Sudakov

In this paper we study non-interactive correlation distillation (NICD), a generalization of noise sensitivity previously considered in [5, 31, 39]. We extend the model to NICD on trees. In this model...

Large (2009)

H-free graphs of large minimum degree (2009)

nearly regular induced subgraphs

MaxCut in H-free graphs (2009)

We prove the following extension of an old result of Andrásfai, Erdős and Sós. For every fixed graph H with chromatic number r + 1 ≥ 3, and for every fixed ɛ> 0, there are n0 = n0(H, ɛ) and...

Large almost monochromatic subsets in hypergraphs (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...

We show that for all $\ell$ and $\epsilon>0$ there is a constant $c=c(\ell,\epsilon)>0$ such that every $\ell$-coloring of the triples of an $N$-element set contains a subset $S$ of size $c\sqrt{\log...

z (2008)

for the set of all `-subsets of [k] = f1; \Delta \Delta \Delta ; kg. Then A has k disjointly representable sets exactly when it has a [k] (1) trace. In this paper we will focus on three forbidden...

A (2008)

sharp threshold for network reliability

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

the probability of independent sets in random graphs

Discrete Kakeya-type problems and small bases (2008)

Noga Alon, Boris Bukh, Benny Sudakov

A subset U of a group G is called k-universal if U contains a translate of every k-element subset of G. We give several nearly optimal constructions of small k-universal sets, and use them to resolve...

A generalization of Turán’s (2008)

Benny Sudakov, Tibor Szabó, Van H. Vu

theorem

Maximizing the number of q-colorings (2008)

We prove that for every fixed k and ℓ ≥ 5 and for sufficiently large n, every edge coloring of the hypercube Qn with k colors contains a monochromatic cycle of length 2ℓ. This answers an open...

Loh, Po-Shen, Pikhurko, Oleg, Sudakov, Benny

Let P_G(q) denote the number of proper q-colorings of a graph G. This function, called the chromatic polynomial of G, was introduced by Birkhoff in 1912, who sought to attack the famous four-color...

Directed graphs without short cycles (2008)

Fox, Jacob, Keevash, Peter, Sudakov, Benny

For a directed graph $G$ without loops or parallel edges, let $\beta(G)$ denote the size of the smallest feedback arc set, i.e., the smallest subset $X \subset E(G)$ such that $G \sm X$ has no...

Hypergraph Ramsey numbers (2008)

Regular induced subgraphs of a random graph (2008)

The Ramsey number r_k(s,n) is the minimum N such that every red-blue coloring of the k-tuples of an N-element set contains either a red set of size s or a blue set of size n, where a set is called...

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)

Rainbow Turán problems (2008)

nearly regular induced subgraphs

Peter Keevash, Dhruv Mubayi, Benny Sudakov, Jacques Verstraëte

For a fixed graph H, we define the rainbow Turán number ex ∗ (n, H) to be the maximum number of edges in a graph on n vertices that has a proper edge-colouring with no rainbow H. Recall that the...

We prove that for every fixed k and ℓ ≥ 5 and for sufficiently large n, every edge coloring of the hypercube Qn with k colors contains a monochromatic cycle of length 2ℓ. This answers an open...

On the random satisfiable process (2008)

graphs with subgraphs having large independence numbers

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, ...,...

Triangle packings and 1-factors in oriented graphs (2008)

Keevash, Peter, Sudakov, Benny

An oriented graph is a directed graph which can be obtained from a simple undirected graph by orienting its edges. In this paper we show that any oriented graph G on n vertices with minimum indegree...

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)...

List (2008)

coloring of random and pseudo-random graphs

Coloring (2008)

graphs with sparse neighborhoods

Finding (2008)

a large hidden clique in a random graph ∗

Induced (2008)

subgraphs of prescribed size

Michael Krivelevich, Benny Sudakov, Prasad Tetali

smoothed analysis in dense graphs and formulas

Constrained Ramsey Numbers (2008)

Po-shen Loh, Benny Sudakov

For two graphs S and T, the constrained Ramsey number f(S, T) is the minimum n such that every edge coloring of the complete graph on n vertices (with any number of colors) has a monochromatic...

two segmentation problems

Bipartite (2008)

subgraphs and the smallest eigenvalue

Michael Krivelevich, Benny Sudakov, V. H. Vu

We prove that for every fixed k and ℓ ≥ 5 and for sufficiently large n, every edge coloring of the hypercube Qn with k colors contains a monochromatic cycle of length 2ℓ. This answers an open...

Covering (2008)

codes with improved density

Packing triangles in a graph and its complement (2008)

Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality (2008)

Published online in Wiley InterScience(www.interscience.wiley.com).

Elchanan Mossel, Oded Regev, Jeffrey E. Steif, Benny Sudakov

In this paper we study the problem of non-interactive correlation distillation (NICD), a generalization of noise sensitivity previously considered in [5, 31, 39]. We extend the model to NICD on...

Cycle (2008)

Benny Sudakov, Jacques Verstraëte

lengths in sparse graphs

Unavoidable patterns (2008)

Two remarks on the Burr-Erdos conjecture (2008)

Let \mathcal{F}_k denote the family of 2-edge-colored complete graphs on 2k vertices in which one color forms either a clique of order k or two disjoint cliques of order k. Bollob\'as conjectured...

Large induced trees in K_r-free graphs (2008)

The Ramsey number r(H) of a graph H is the minimum positive integer N such that every two-coloring of the edges of the complete graph K_N on N vertices contains a monochromatic copy of H. A graph H...

Fox, Jacob, Loh, Po-Shen, Sudakov, Benny

For a graph G, let t(G) denote the maximum number of vertices in an induced subgraph of G that is a tree. In this paper, we study the problem of bounding t(G) for graphs which do not contain a...

On smoothed analysis in dense graphs and formulas (2008)

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 et...

Ramsey numbers of sparse hypergraphs (2008)

David Conlon, Jacob Fox, Benny Sudakov

We give a short proof that any k-uniform hypergraph H on n vertices with bounded degree ∆ has Ramsey number at most c(∆, k)n, for an appropriate constant c(∆, k). This result was recently...

Constrained Ramsey Numbers (2008)

Po-shen Loh, Benny Sudakov

For two graphs S and T, the constrained Ramsey number f(S, T) is the minimum n such that every edge coloring of the complete graph on n vertices (with any number of colors) has a monochromatic...

Ramsey-type problem for an almost monochromatic K4 (2008)

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

In this short note we prove that there is a constant c such that every k-edge-coloring of the complete graph Kn with n ≥ 2 ck contains a K4 whose edges receive at most two colors. This improves on...

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.

Discrete Kakeya-type problems and small bases (2008)

Noga Alon, Boris Bukh, Benny Sudakov

A subset U of a group G is called k-universal if U contains a translate of every k-element subset of G. We give several nearly optimal constructions of small k-universal sets, and use them to resolve...

Rainbow Turán problems (2008)

Peter Keevash, Dhruv Mubayi, Benny Sudakov, Jacques Verstra Ëte

For a fixed graph H, we define the rainbow Turán number ex ∗ (n, H) to be the maximum number of edges in a graph on n vertices that has a proper edge-colouring with no rainbow H....

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...

Induced Ramsey-type theorems (2008)

We present a unified approach to proving Ramsey-type theorems for graphs with a forbidden induced subgraph which can be used to extend and improve the earlier results of Rödl, Erdős-Hajnal,...

Density (2008)

On smoothed analysis in dense graphs and formulas (2008)

theorems for bipartite graphs and related Ramsey-type results

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)

Bounding the number of edges in permutation graphs (2008)

nearly regular induced subgraphs

Peter Keevash, Po-shen Loh, Benny Sudakov

Given an integer s ≥ 0 and a permutation π ∈ Sn, letΓπ,s be the graph on n vertices {1,...,n} where two vertices i<jare adjacent if the permutation flips their order and there are at most s...

Vol. 18, No. 4, pp. 713–727 SET SYSTEMS WITH RESTRICTED CROSS-INTERSECTIONS AND THE MINIMUM RANK OF INCLUSION MATRICES ∗ (2008)

Benny Sudakov, Jacques Verstraëte

Abstract. A set system is L-intersecting if any pairwise intersection size lies in L, where L is some set of s nonnegative integers. The celebrated Frankl–Ray-Chaudhuri–Wilson theorems give tight...

and Extractors (2008)

Boaz Barak, Guy Kindler, Benny Sudakov, Avi Wigderson

A distribution X over binary strings of length n has minentropy k if every string has probability at most 2 −k in X. 1 We say that X is a δ-source if its rate k/n is at least δ. We give the...

Cycle (2008)

lengths in sparse graphs

H-free graphs of large minimum degree (2008)

On the random satisfiable 3CNF process (2008)

We prove the following extension of an old result of Andrásfai, Erdős and Sós. For every fixed graph H with chromatic number r +1 ≥ 3, and for every fixed ɛ>0, there are n0 = n0(H, ɛ) andρ...

Michael Krivelevich, Benny Sudakov, Dan Vilenchik

RAMSEY NUMBERS AND THE SIZE OF GRAPHS ∗ (2008)

Alan Frieze, Michael Krivelevich, Benny Sudakov

Abstract. For two graphs H and G, the Ramsey number r(H, G) is the smallest positive integer n such that every red-blue edge coloring of the complete graph Kn on n vertices contains either a red copy...

The (2008)

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...

The (2008)

Alan Frieze, Michael Krivelevich, Benny Sudakov

strong chromatic index of random graphs

A note on odd cycle-complete graph Ramsey numbers (2008)

Abstract: We prove that for every fixed k and ℓ ≥ 5 and for sufficiently large n, every edge coloring of the hypercube Qn with k colors contains a monochromatic cycle of length 2ℓ. This answers...

A generalization of Turán's theorem (2008)

The Ramsey number r(C l ; K n ) is the smallest positive integer m such that every graph of order m contains either cycle of length l or a set of n independent vertices.

Benny Sudakov, Tibor Szabó, Van H. Vu

In this paper we obtain an asymptotic generalization of Turán's theorem. We prove that if all the non-trivial eigenvalues of a d-regular graph G on n vertices are sufficiently small, then the...

On the value of a random minimum length Steiner tree (2007)

David Gamarnik, Benny Sudakov

Consider a complete graph on n vertices with edge lengths chosen randomly and independently from e.g., an exponential distribution with parameter 1. Fix k vertices and consider the minimal length...

Sharp threshold for network reliability (2007)

Asymptotically the list colouring constants are 1 (2007)

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...

Bruce Reed, Benny Sudakov

In this paper we prove the following result about vertex list colourings, which shows that a conjecture from [9] is asymptotically correct. Let G be a graph with the sets of lists S(v), satisfying...

Nowhere-Zero Flows in Random Graphs (2007)

A Note on tau-Critical Linear Hypergraphs (2007)

A nowhere-zero 3-ow in a graph G is an assignment of a direction and a value 1 or 2 to each edge of G such that for each vertex v in G, the sum of the values of the edges with tail v equals the sum...

Acyclic Edge Colorings of Graphs (2007)

J.P. Roudneff as well as R. Aharoni and R. Ziv conjectured that every -critical linear hypergraph has at most \Gamma +1 2 \Delta edges. In this note we prove this conjecture for 5, and obtain a...

Noga Alon, Benny Sudakov, Ayal Zaks

A proper coloring of the edges of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic edge chromatic number of G, denoted by a 0 (G), is the least number of colors in an...

A note on odd cycle-complete graph Ramsey numbers (2007)

240 JOURNAL OF GRAPH THEORY (2007)

The Ramsey number r(Cl,Kn) is the smallest positive integer m such that every graph of order m contains either cycle of length l or a set of n independent vertices. In this short note we slightly...

On the number of edges not covered by monochromatic copies of a xed (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...

Learning a Hidden Matching Combinatorial Identication of Hidden Matchings with Applications to Whole Genome Sequencing (2007)

graph

Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, Benny Sudakov

We consider the problem of learning a matching (i.e., a graph in which all vertices have degree 0 or 1) in a model where the only allowed operation is to query whether a set of vertices induces an...

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

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

z (2007)

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

Asymptotically optimal treepackings in regular graphs (2007)

Let T be a tree with t vertices. Clearly, an n vertex graph contains at most n=t vertex disjoint trees isomorphic to T. In this paper we show that for every > 0, there exists a D(; t)> 0 such...

Sharp threshold for network reliability (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

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...

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...

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

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...

z (2007)

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...

Asymptotically optimal treepackings in regular graphs (2007)

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

Let T be a tree with t vertices. Clearly, an n vertex graph contains at most n=t vertex disjoint trees isomorphic to T. In this paper we show that for every > 0, there exists a D(; t)> 0 such...

A new lower bound for a Ramsey-type problem (2007)

(Extended abstract)

Sparse pseudo-random graphs are Hamiltonian (2007)

Let 3 r be xed integers and let G be a graph on n vertices not containing a complete graph on s vertices. The main aim of this paper is to provide a new lower bound on the size of the maximum subset...

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)

z (2007)

Asymptotically optimal treepackings in regular graphs (2007)

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...

the J'anos Bolyai and Farkas Bolyai Fellowships. (2007)

Let T be a tree with t vertices. Clearly, an n vertex graph contains at most n/t vertex disjoint trees isomorphic to T. In this paper we show that for every ɛ>0, there exists a D(ɛ, t)> 0...

Vince Grolmusz, Benny Sudakov

k-wise Set-Intersections and k-wise

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 a hypergraph Turán problem of Frankl (2007)

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

P r be pairwise disjoint sets of size k and taking as edges all sets P i j with i j. This can be thought of as the `k-expansion' of the complete graph K r : each vertex has been replaced with 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) satisfies p(n) n -2/5 ln n then the probability that c, for some...

On the Largest Eigenvalue of a Random Subgraph of the Hypercube (2007)

Alexander Soshnikov, Benny Sudakov

Let G be a random subgraph of the n-cube where each edge appears randomly and independently with probability p. We prove that the largest eigenvalue of the adjacency matrix of G is almost surely 1...

Covering Codes with Improved Density (2007)

Learning a Hidden Matching (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...

Combinatorial Identification Of, Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, Benny Sudakov

We consider the problem of learning a matching (i.e., a graph in which all vertices have degree 0 or 1) in a model where the only allowed operation is to query whether a set of vertices induces an...

ICM 2002 Vol. III 587-603 (2007)

List Colouring Of, Bruce Reed, Benny Sudakov

Ohba has conjectured [9] that if the graph G has 2(G)+1 or fewer vertices then the list chromatic number and chromatic number of G are equal. In this paper we prove that this conjecture is...

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

The Number of Edge Colorings With No Monochromatic Cliques (2007)

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...

Noga Alon Ozsef, Noga Alon, Peter Keevash, Benny Sudakov

Let F (n; r; k) denote the maximum possible number of distinct edge-colorings of a simple graph on n vertices with r colors, which contain no monochromatic copy of K k . It is shown that for every...

Journal of ComR.@FRpFR. Theory, Series A 99, 180--190 (2002) doi:10.1006/jcta.2002.3264 NOTE (2007)

Vince Grolmusz, Benny Sudakov

this paper, we give bounds on the size of set-system and codes, satisfying som k-wise intersection-size orHam ing-distance properties. For k 2; thesetheorem s were proven by Ray-Chaudhuri and Wilson...

Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality (2007)

Elchanan Mossel, Ryan O'Donnell, Oded Regev, Jeffrey E. Steif, Benny Sudakov

In this paper we study the problem of non-interactive correlation distillation (NICD), a generalization of noise sensitivity previously considered in [5, 31, 39]. We extend the model to NICD on...

Discrete Kakeya-type problems and small bases (2007)

Alon, Noga, Bukh, Boris, Sudakov, Benny

A subset U of a group G is called k-universal if U contains a translate of every k-element subset of G. We give several nearly optimal constructions of small k-universal sets, and use them to resolve...

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...

Ramsey numbers of sparse hypergraphs (2007)

Avoiding small subgraphs in Achlioptas processes (2007)

We give a short proof that any k-uniform hypergraph H on n vertices with bounded degree \Delta has Ramsey number at most c(\Delta, k)n, for an appropriate constant c(\Delta, k). This result was...

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...

Density theorems for bipartite graphs and related Ramsey-type results (2007)

Nearly optimal embeddings of trees (2007)

In this paper, we present several density-type theorems which show how to find a copy of a sparse bipartite graph in a graph of positive density. Our results imply several new bounds for classical...

Sudakov, Benny, Vondrak, Jan

In this paper we show how to find nearly optimal embeddings of large trees in several natural classes of graphs. The size of the tree T can be as large as a constant fraction of the size of the graph...

Cycle lengths in sparse graphs (2007)

Sudakov, Benny, Verstraete, Jacques

Let C(G) denote the set of lengths of cycles in a graph G. In the first part of this paper, we study the minimum possible value of |C(G)| over all graphs G of average degree d and girth g. Erdos...

The game chromatic number of random graphs (2007)

Bohman, Tom, Frieze, Alan, Sudakov, Benny

Given a graph G and an integer k, two players take turns coloring the vertices of G one by one using k colors so that neighboring vertices get different colors. The first player wins iff at the end...

How many random edges make a dense hypergraph non-2-colorable? (2007)

Sudakov, Benny, Vondrak, Jan

We study a model of random uniform hypergraphs, where a random instance is obtained by adding random edges to a large hypergraph of a given density. We obtain a tight bound on the number of random...

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...

Additive approximation for edge-deletion problems (2007)

Alon, Noga, Shapira, Asaf, Sudakov, Benny

A graph property is monotone if it is closed under removal of vertices and edges. In this paper we consider the following edge-deletion problem; given a monotone property P and a graph G, compute the...

On graphs with subgraphs of large independence numbers (2007)

Alon, Noga, Sudakov, Benny

Let G be a graph on n vertices in which every induced subgraph on s=\log^3 n vertices has an independent set of size at least t=\log n. What is the largest q=q(n) so that every such G must contain an...

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...

Making a K_4-free graph bipartite (2007)

Sudakov, Benny

We show that every K_4-free graph G with n vertices can be made bipartite by deleting at most n^2/9 edges. Moreover, the only extremal graph which requires deletion of that many edges is a complete...

Ramsey numbers and the size of graphs (2007)

Sudakov, Benny

For two graph H and G, the Ramsey number r(H, G) is the smallest positive integer n such that every red-blue edge coloring of the complete graph K_n on n vertices contains either a red copy of H or a...

Local resilience of graphs (2007)

Sudakov, Benny, Vu, Van

In this paper, we initiate a systematic study of graph resilience. The (local) resilience of a graph G with respect to a property P measures how much one has to change G (locally) in order to destroy...

Induced Ramsey-type theorems (2007)

Constrained Ramsey Numbers (2007)

We present a unified approach to proving Ramsey-type theorems for graphs with a forbidden induced subgraph which can be used to extend and improve the earlier results of Rodl, Erdos-Hajnal,...

Loh, Po-Shen, Sudakov, Benny

For two graphs S and T, the constrained Ramsey number f(S, T) is the minimum n such that every edge coloring of the complete graph on n vertices, with any number of colors, has a monochromatic...

On the strong chromatic number of random graphs (2007)

Loh, Po-Shen, Sudakov, Benny

Let G be a graph with n vertices, and let k be an integer dividing n. G is said to be strongly k-colorable if for every partition of V(G) into disjoint sets V_1 \cup ... \cup V_r, all of size exactly...

Independent transversals in locally sparse graphs (2007)

Loh, Po-Shen, Sudakov, Benny

Let G be a graph with maximum degree \Delta whose vertex set is partitioned into parts V(G) = V_1 \cup ... \cup V_r. A transversal is a subset of V(G) containing exactly one vertex from each part...

On a problem of Duke-Erdos-Rodl on cycle-connected subgraphs (2007)

Rainbow Turán Problems (2007)

In this short note, we prove that for \beta < 1/5 every graph G with n vertices and n^{2-\beta} edges contains a subgraph G' with at least cn^{2-2\beta} edges such that every pair of edges in G' lie...

Keevash, Peter, Mubayi, Dhruv, Sudakov, Benny, Verstraëte, Jacques

For a fixed graph H, we define the rainbow Turán number ex^*(n,H) to be the maximum number of edges in a graph on n vertices that has a proper edge-colouring with no rainbow H. Recall that the...

Bounding the Number of Edges in Permutation Graphs (2006)

Keevash, Peter, Loh, Po-Shen, Sudakov, Benny

Given an integer s >= 0 and a permutation pi is an element of S-n, let Gamma(pi,s) be the graph on n vertices {1,..., n} where two vertices i < j are adjacent if the permutation flips their order and...

Pseudo-random graphs (2006)

150 JOURNAL OF GRAPH THEORY (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,...

On a hypergraph Turán problem of Frankl (2006)

Abstract: Let G be a graph on n vertices in which every induced subgraph on s = log 3 n vertices has an independent set of size at least t = log n. What is the largest q = q(n) so that every such G...

Let C (k, Peter Keevash, Benny Sudakov, Alfred P. Sloan

be the 2k-uniform hypergraph obtained by letting P1,...,Pr be pairwise disjoint sets of size k and taking as edges all sets Pi ∪Pj with i�=j. This can be thought of as the ‘k-expansion ’ of...

CYCLE LENGTHS IN SPARSE GRAPHS (2006)

Benny Sudakov, Jacques Verstra Ëte

Let C(G) denote the set of lengths of cycles in a graph G. In the first part of this paper, we study the minimum possible value of |C(G) | over all graphs G of average degree d and girth g.Erdős [8]...

Local Resilience of Graphs* (2006)

Benny Sudakov, V. H. Vu

ABSTRACT: In this article, we initiate a systematic study of graph resilience. The (local) resilience of a graph G with respect to a property P measures how much one has to change G (locally) to...

The game chromatic number of random graphs (2006)

Tom Bohman, Alan Frieze, Benny Sudakov

ABSTRACT: Given a graph G and an integer k, two players take turns coloring the vertices of G one by one using k colors so that neighboring vertices get different colors. The first player wins iff at...

Set Systems with Restricted Cross-Intersections and the Minimum Rank of Inclusion Matrices (2005)

Kevash, Peter, Sudakov, Benny

A set system is L-intersecting if any pairwise intersection size lies in L, where L is some set of s nonnegative integers. The celebrated Frankl-Ray-Chaudhuri-Wilson theorems give tight bounds on the...

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,...

Additive approximation for edge-deletion problems (2005)

Noga Alon, Asaf Shapira, Benny Sudakov

A graph property is monotone if it is closed under removal of vertices and edges. In this paper we consider the following algorithmic problem, called the edge-deletion problem; given a monotone...

On a hypergraph Turán problem (2005)

Peter Keevash, Mike Saks, Benny Sudakov

A simple k-colouring of a multigraph G is a decomposition of the edge multiset as the sum of k simple graphs, called `colours'. A copy of some xed graph H in G is called multicoloured if its...

Additive approximation for edge-deletion problems (2005)

Noga Alon, Asaf Shapira, Benny Sudakov

A graph property is monotone if it is closed under removal of vertices and edges. In this paper we consider the following algorithmic problem, called the edge-deletion problem; given a monotone...

Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers, and Extractors (2005)

Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson

A distribution X over binary strings of length n has min-entropy k if every string has probability at most 2 −k in X. 1 X is called a δ-source if its rate k/n is at least δ. We give the following...

Additive approximation for edge-deletion problems (2005)

Noga Alon, Asaf Shapira, Benny Sudakov

A graph property is monotone if it is closed under removal of vertices and edges. In this paper we consider the following algorithmic problem, called the edge-deletion problem; given a monotone...

Large Kr-free subgraphs in Ks-free graphs and some other Ramsey-type problems, Random Structures & Algorithms 26 (2005)

DOI: 10.1007/s00493-007-2238-0 MAKING A K4-FREE GRAPH BIPARTITE (2005)

ABSTRACT: In this paper we present three Ramsey-type results, which we derive from a simple and yet powerful lemma, proved using probabilistic arguments. Let 3 ≤ r < s be fixed integers and let...

Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers, and Extractors (2005)

We show that every K4-free graph G with n vertices can be made bipartite by deleting at most n 2 /9 edges. Moreover, the only extremal graph which requires deletion of that many edges is a complete...

Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson

We present new explicit constructions of deterministic randomness extractors, dispersers and related objects. More precisely, a distribution X over binary strings of length n is called a δ-source if...

How Many Random Edges Make a Dense (2005)

Hypergraph Non--colorable, Benny Sudakov, Jan Vondrák

ABSTRACT: We study a model of random uniform hypergraphs, where a random instance is obtained by adding random edges to a large hypergraph of a given density. The research on this model for graphs...

The number of edge colorings with no monochromatic cliques (2004)

Noga Alon, József Balogh, Peter Keevash, Benny Sudakov

Let F (n, r, k) denote the maximum possible number of distinct edge-colorings of a simple graph on n vertices with r colors which contain no monochromatic copy of Kk. Itisshownthatfor every fixed k...

Graph products, fourier analysis and spectral techniques (2004)

Noga Alon, Irit Dinur, Ehud Friedgut, Benny Sudakov

We consider powers of regular graphs defined by the weak graph product and give a characterization of maximum-size independent sets for a wide family of base graphs which includes, among others,...

On the value of a random minimum weight steiner tree (2004)

David Gamarnik, Oliver Riordan, Benny Sudakov

Consider a complete graph on n vertices with edge weights chosen randomly and independently from, for example, an exponential distribution with parameter 1. Fix k vertices and consider the minimum...

On the value of a random minimum weight steiner tree (2004)

Béla Bollobás, David Gamarnik, Oliver Riordan, Benny Sudakov

Consider a complete graph on n vertices with edge weights chosen randomly and independently from an exponential distribution with parameter 1. Fix k vertices and consider the minimum weight Steiner...

The Turán number of the Fano plane (2004)

List colouring of graphs with at most $\big(2-o(1)\big)\chi$ vertices (2003)

Let PG 2 (2) be the Fano plane, i.e., the unique hypergraph with 7 triples on 7 vertices in which every pair of vertices is contained in a unique triple. In this paper we prove that for su#ciently...

Reed, Bruce, Sudakov, Benny

Ohba has conjectured \cite{ohb} that if the graph $G$ has $2\chi(G)+1$ or fewer vertices then the list chromatic number and chromatic number of $G$ are equal. In this paper we prove that this...

The largest eigenvalue of sparse random graphs (2003)

Digital Object Identifier (DOI) 10.1007/s00220-003-0872-y Mathematical Physics On the Largest Eigenvalue of a Random Subgraph (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...

Of The Hypercube, Er Soshnikov, Benny Sudakov

Abstract: Let G be a random subgraph of the n-cube where each edge appears randomly and independently with probability p. We prove that the largest eigenvalue of the adjacency matrix of G is almost...

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,..

Benny Sudakov, Communicated Gil Kalai

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,...

Extremal (2003)

set systems with restricted k-wise intersections Zolta ´ nFu¨redi a,b,1 c,d,,2

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

Graph Products, Fourier Analysis and Spectral Techniques (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...

Noga Alon, Irit Dinur, Ehud Friedgut, Benny Sudakov

We consider powers of regular graphs defined by the weak graph product and give a characterization of maximum-size independent sets for a wide family of base graphs which includes, among others,...

Local Density in Graphs with Forbidden Subgraphs (2003)

Induced Subgraphs of Prescribed Size (2003)

this paper we consider the following more general question. Let G be a K r+1 -free graph of order n and let # be a constant, 0 <## 1. Suppose that every #n vertices of G span at least #n edges....

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 a hypergraph Turan problem of Frankl (2002)

Keevash, Peter, Sudakov, Benny

Let $C^{2k}_r$ be the $2k$-uniform hypergraph obtained by letting $P_1,...,P_r$ be pairwise disjoint sets of size $k$ and taking as edges all sets $P_i \cup P_j$ with $i \neq j$. This can be thought...

On the Largest Eigenvalue of a Random Subgraph of the Hypercube (2002)

Soshnikov, Alexander, Sudakov, Benny

Let G be a random subgraph of the n-cube where each edge appears randomly and independently with probability p. We prove that the largest eigenvalue of the adjacency matrix of G is almost surely...

Constructing worst case instances for semidefinite programming based approximation algorithms (2002)

On the asymmetry of random regular graphs and random graphs (2002)

Semide nite programming based approximation algorithms, such as the Goemans and Williamson approximation algorithm for the MAX CUT problem, are usually shown to have certain performance guarantees...

Jeong Han Kim, Benny Sudakov, Van H. Vu

This paper studies the symmetry of random regular graphs and random graphs. Our main result shows that for all 3 d n 4 the random d-regular graph on n vertices almost surely has no non-trivial...

Constructing worst case instances for semidefinite programming based approximation algorithms (2002)

Sparse Pseudo-Random Graphs Are Hamiltonian (2002)

Semide nite programming based approximation algorithms, such as the Goemans and Williamson approximation algorithm for the MAX CUT problem, are usually shown to have certain performance guarantees...

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)

DOI: 10.1017/S0963548303005728 Printed in the United Kingdom On Ramsey Numbers of Sparse Graphs (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...

Alexandr Kostochka, Benny Sudakov

2-colouring of the edges of the complete graph KN on N vertices, there is a monochromatic copy of G. In1975, Burr and Erdős posed a problem on Ramsey numbers of d-degenerate graphs, i.e., graphs in...

Learning a hidden matching (2002)

Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, Benny Sudakov

Abstract. We consider the problem of learning a matching (i.e., a graph in which all vertices have degree 0 or 1) in a model where the only allowed operation is to query whether a set of vertices...

On the asymmetry of random regular graphs and random graphs. Random Structures & Algorithms (2002)

Jeong Han Kim, Benny Sudakov, Van H. Vu

ABSTRACT: This paper studies the symmetry of random regular graphs and random graphs. Our main result shows that for all 3�d�n�4the random d-regular graph on nvertices almost...

188 JOURNAL OF GRAPH THEORY (2002)

Benny Sudakov, Tibor Szabó, Van H. Vu

Abstract: In this paper, we obtain an asymptotic generalization of Turán’s theorem. We prove that if all the non-trivial eigenvalues of a d-regular graph G on n vertices are sufficiently small,...

COMBINATORICA Bolyai Society – Springer-Verlag Combinatorica 25 (5) (2005) 561–574 THE TURÁN NUMBER OF THE FANO PLANE (2002)

THe largest eigenvalue of sparse random graphs (2001)

Let PG2(2) be the Fano plane, i.e., the unique hypergraph with 7 triples on 7 vertices in which every pair of vertices is contained in a unique triple. In this paper we prove that for sufficiently...

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...

Acyclic edge colorings of graphs (2001)

Noga Alon, Benny Sudakov, Ayal Zaks

A proper coloring of the edges of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic edge chromatic number of G, denoted by a ′ (G), is the least number of colors in an...

On k-wise set-intersections and k-wise hamming-distances (2001)

Vince Grolmusz, Benny Sudakov

We prove a version of the Ray-Chaudhuri{Wilson and Frankl-Wilson theorems for k-wise intersections and also generalize a classical code-theoretic result of Delsarte for k-wise Hamming distances. A...

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

Michael Krivelevich, Ram Nathaniel, Benny Sudakov

hypergraphs

Asymptotically Optimal Tree-Packings in Regular Graphs (2001)

Constructing Worst Case Instances for Semidefinite Programming Based Approximation Algorithms (2001)

Let T be a tree with t vertices. Clearly, an n vertex graph contains at most n=t vertex disjoint trees isomorphic to T . In this paper we show that for every > 0, there exists a D(; t) > 0 such...

On the Asymmetry of Random Regular Graphs and Random Graphs (2001)

Semide nite programming based approximation algorithms, such as the Goemans and Williamson approximation algorithm for the MAX CUT problem, are usually shown to have certain performance guarantees...

Jeong Han Kim, Benny Sudakov, Kim Benny, Sudakov Van, Van H. Vu

This paper studies the symmetry of random regular graphs and random graphs. Our main result shows that for all 3 4 the random d-regular graph on n vertices almost surely has no non-trivial...

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...

Constructing Worst Case Instances for Semidefinite Programming Based Approximation Algorithms (2001)

COMBINATORICA Bolyai Society – Springer-Verlag Combinatorica 25 (4) (2005) 487–498 A NEW LOWER BOUND FOR A RAMSEY-TYPE PROBLEM (2001)

SL,BAEb#[1 programming based approximation algorithms, such as the Goemans and Williamson approximation algorithm for the MAX CUT problem, are usually shown to have certain performance guarantees...

Acyclic edge colorings of graphs (2001)

Let 3 ≤ r<sbe fixed integers and let G be a graph on n vertices not containing a complete graph on s vertices. The main aim of this paper is to provide a new lower bound on the size of the...

Noga Alon, Benny Sudakov, Ayal Zaks

Abstract: A proper coloring of the edges of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic edge chromatic number of G, denoted by a 0 (G), is the least number of colors...

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...

LIST COLOURING WHEN THE CHROMATIC NUMBER IS CLOSE TO THE ORDER OF THE GRAPH (2001)

Bruce Reed, Benny Sudakov

Ohba has conjectured [7] thatifGhas 2χ(G)+1 or fewer vertices then the list chromatic number and chromatic number of G are equal. In this short note we prove the weaker version of the conjecture...

Bipartite subgraphs and the smallest eigenvalue (2000)

Journal of Combinatorial Theory, Series B 86, 27–37 (2002) doi:10.1006/jctb.2002.2110 Asymptotically the List Colouring Constants Are1 (2000)

Two results dealing with the relation between the smallest eigenvalue of a graph and its bipartite subgraphs are obtained. The first result is that the smallest eigenvalue µ of any non-bipartite...

Bruce Reed, Benny Sudakov

In this paper we prove the following result about vertex list colourings, which shows that a conjecture of the first author (1999, J. Graph Theory 31, 149–153) is asymptotically correct.Let G be a...

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

: www.idealibrary.com on Nowhere-Zero Flows in Random Graphs (2000)

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,...

On Two Segmentation Problems (1999)

A nowhere-zero 3-flow in a graph G is an assignment of a direction and a value of 1 or 2 to each edge of G such that, for each vertex v in G, the sum of the values of the edges with tail v equals the...

Coloring Graphs with Sparse Neighborhoods (1999)

this paper is organized as follows. In Section 2 we consider the hypercube segmentation problem, describe our randomized approximation algorithm, and present is derandomization. In Section 3 we...

On Two Segmentation Problems (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...

On two segmentation problems (1999)

The hypercube segmentation problem is the following: Given a set S of m vertices of the discrete d-dimensional cube {0, 1}^d, find k vertices P 1 , ..., P k , P i in {0, 1}^d and a partitions of S...

Coloring random graphs (1998)

The hypercube segmentation problem is the following: Given a set S of m 4d vertices of the discrete d-dimensional cube 0, 1, find k vertices P 1,...,P k, 4d Pi � 0, 1 and a partitions of S into k...

The Chromatic Numbers of Random Hypergraphs (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.

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...

Bipartite Subgraphs and the Smallest Eigenvalue (1998)

Coloring Random Graphs (1998)

Two results dealing with the relation between the smallest eigenvalue of a graph and its bipartite subgraphs are obtained. The first result is that the smallest eigenvalue of any nonbipartite graph...

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...

Subgraphs with a large cochromatic number (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)

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...

The Chromatic Numbers of Random Hypergraphs (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...

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...

Intersecting systems (1993)

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...

A disjoint system of type (∀, ∃, k, n) is a collection C = {A1,..., Am} of pairwise disjoint families of k-subsets of an n-element set satisfying the following condition. For every ordered pair...

Disjoint Systems (1993)

Random regular graphs of high degree (1982)

A disjoint system of type (8; 9; k; n) is a collection C = fA 1 ; : : : ; Am g of pairwise disjoint families of k-subsets of an n-element set satisfying the following condition. For every ordered...

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 =...

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

Maximum Cuts and Judicious Partitions in Graphs without Short Cycles

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...

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