Benny Sudakov
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Benny Sudakov has a total of 2 co-authors. Here are the top co-authors by number of shared publications:
- Michael Krivelevich
Tel Aviv University
3 shared publications - Noga Alon
Department of Mathematics, Princeton University, Princeton, USA
3 shared publications
Latest Publications
- 1 January 2000
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 9 (1) , 1-12
Bipartite Subgraphs and the Smallest Eigenvalue
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 graph on n vertices with diameter D and maximum degree Δ satisfies μ [ges ] −Δ + 1/(D+1)n. This improves previous estimates and is tight up to a constant factor. The second result is the determination of the precise approximation guarantee of the MAX CUT algorithm of Goemans and Williamson for graphs G = (V, E) in which the size of the max cut is at least A[mid ]E[mid ], for all A between 0.845 and 1. This extends a result of Karloff.
- 1 January 2000
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 9 (1) , 1-12
Bipartite Subgraphs and the Smallest Eigenvalue
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 graph on n vertices with diameter D and maximum degree Δ satisfies μ [ges ] −Δ + 1/(D+1)n. This improves previous estimates and is tight up to a constant factor. The second result is the determination of the precise approximation guarantee of the MAX CUT algorithm of Goemans and Williamson for graphs G = (V, E) in which the size of the max cut is at least A[mid ]E[mid ], for all A between 0.845 and 1. This extends a result of Karloff.
- 1 October 1999
- Published by Springer Nature in Combinatorica
- Vol. 19 (4) , 453-472
List Coloring of Random and Pseudo-Random Graphs
- 1 October 1999
- Published by Springer Nature in Combinatorica
- Vol. 19 (4) , 453-472
List Coloring of Random and Pseudo-Random Graphs
- 1 October 1998
- Published by Wiley in Random Structures & Algorithms
- Vol. 13 (34) , 457-466
Finding a large hidden clique in a random graph
- 1 October 1998
- Published by Wiley in Random Structures & Algorithms
- Vol. 13 (34) , 457-466
Finding a large hidden clique in a random graph
- 30 July 1998
- Published by Elsevier in Information Processing Letters
- Vol. 67 (2) , 71-74
Coloring random graphs
- 30 July 1998
- Published by Elsevier in Information Processing Letters
- Vol. 67 (2) , 71-74
Coloring random graphs
- 1 September 1997
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 13 (3) , 281-285
A Note on τ-Critical Linear Hypergraphs
- 1 September 1997
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 13 (3) , 281-285
A Note on τ-Critical Linear Hypergraphs