Alon Amit
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Alon Amit has a total of 3 co-authors. Here are the top co-authors by number of shared publications:
- Nathan Linial
The Hebrew University of Jerusalem
2 shared publications Jiří Matoušek
Department of Applied Mathematics and Institute for Theoretical Computer Science (ITI), Charles University, Malostranské nám. 25, 118 00 Praha 1, Czech Republic
1 shared publicationNathan Linial
Institute of Computer Science, Hebrew University, Jerusalem 91904, Israel
1 shared publication
Latest Publications
- 7 April 2006
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 15 (3) , 317-332
Random Lifts of Graphs: Edge Expansion
We continue the study of random lifts of graphs initiated in [4]. Here we study the possibility of generating graphs with high edge expansion as random lifts. Along the way, we introduce the method of -nets into the study of random structures. This enables us to improve (slightly) the known bounds for the edge expansion of regular graphs.
- 7 April 2006
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 15 (3) , 317-332
Random Lifts of Graphs: Edge Expansion
We continue the study of random lifts of graphs initiated in [4]. Here we study the possibility of generating graphs with high edge expansion as random lifts. Along the way, we introduce the method of -nets into the study of random structures. This enables us to improve (slightly) the known bounds for the edge expansion of regular graphs.
- 1 January 2002
- Published by Springer Nature in Combinatorica
- Vol. 22 (1) , 1-18
Random Graph Coverings I: General Theory and Graph Connectivity
- 1 January 2002
- Published by Springer Nature in Combinatorica
- Vol. 22 (1) , 1-18
Random Graph Coverings I: General Theory and Graph Connectivity
- 3 December 2001
- Published by Wiley in Random Structures & Algorithms
- Vol. 20 (1) , 1-22
Random lifts of graphs: Independence and chromatic number
For a graph G, a random n‐lift of G has the vertex set V(G)×[n] and for each edge [u, v] ∈ E(G), there is a random matching between {u}×[n] and {v}×[n]. We present bounds on the chromatic number and on the independence number of typical random lifts, with G fixed and n→∞. For the independence number, upper and lower bounds are obtained as solutions to certain optimization problems on the base graph. For a base graph G with chromatic number χ and fractional chromatic number χf, we show that the chromatic number of typical lifts is bounded from below by const ⋅ \documentclass{article}\pagestyle{empty}$\sqrt{\chi/\log\chi}$ and also by const ⋅ χf/log2χf (trivially, it is bounded by χ from above). We have examples of graphs where the chromatic number of the lift equals χ almost surely, and others where it is a.s. O(χ/logχ). Many interesting problems remain open. © 2002 John Wiley & Sons, Inc. Random Struct. Alg., 20, 1–22, 2002
- 3 December 2001
- Published by Wiley in Random Structures & Algorithms
- Vol. 20 (1) , 1-22
Random lifts of graphs: Independence and chromatic number
For a graph G, a random n‐lift of G has the vertex set V(G)×[n] and for each edge [u, v] ∈ E(G), there is a random matching between {u}×[n] and {v}×[n]. We present bounds on the chromatic number and on the independence number of typical random lifts, with G fixed and n→∞. For the independence number, upper and lower bounds are obtained as solutions to certain optimization problems on the base graph. For a base graph G with chromatic number χ and fractional chromatic number χf, we show that the chromatic number of typical lifts is bounded from below by const ⋅ \documentclass{article}\pagestyle{empty}$\sqrt{\chi/\log\chi}$ and also by const ⋅ χf/log2χf (trivially, it is bounded by χ from above). We have examples of graphs where the chromatic number of the lift equals χ almost surely, and others where it is a.s. O(χ/logχ). Many interesting problems remain open. © 2002 John Wiley & Sons, Inc. Random Struct. Alg., 20, 1–22, 2002