Monotone maps, sphericity and bounded second eigenvalue

DOI10.1016/j.jctb.2005.04.005zbMath1077.05058arXivmath/0401293OpenAlexW2028203362MaRDI QIDQ2573647

Nathan Linial, Yonatan Bilu

Publication date: 22 November 2005

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0401293

zbMATH Keywords

embeddingfinite metric space

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Special maps on metric spaces (54E40) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

On the Complexity of Closest Pair via Polar-Pair of Point-Sets ⋮ Space lower bounds for low-stretch greedy embeddings ⋮ Betweenness parameterized above tight lower bound ⋮ On closest pair in Euclidean metric: monochromatic is as hard as bichromatic ⋮ Unnamed Item ⋮ On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic ⋮ On the Complexity of Closest Pair via Polar-Pair of Point-Sets ⋮ Lower bounds for boxicity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Space graphs and sphericity
• Dispersed points and geometric embedding of complete bipartite graphs
• The Johnson-Lindenstrauss lemma and the sphericity of some graphs
• Mangoes and blueberries
• On embedding of graphs into Euclidean spaces of small dimension
• Line graphs, root systems, and elliptic geometry
• Geometric algorithms and combinatorial optimization.
• Unit disk graph recognition is NP-hard
• Embeddings of graphs in Euclidean spaces
• Geometrical embeddings of graphs
• Application of cut polyhedra. I
• Extensions of Lipschitz mappings into a Hilbert space
• Matrix Analysis
• On the Betti Numbers of Real Varieties