Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory
From MaRDI portal
Publication:579273
DOI10.1007/BF02579382zbMATH Open0625.05026DBLPjournals/combinatorica/Alon86bWikidataQ56047325 ScholiaQ56047325MaRDI QIDQ579273FDOQ579273
Authors: Noga Alon 
Publication date: 1986
Published in: Combinatorica (Search for Journal in Brave)
Recommendations
- scientific article; zbMATH DE number 3875168
- scientific article; zbMATH DE number 3893127
- scientific article; zbMATH DE number 4106902
- Orderings on graphs and game coloring number
- Some classes of perfectly orderable graphs
- Almost all comparability graphs are UPO
- scientific article; zbMATH DE number 1028228
- scientific article; zbMATH DE number 3889587
- scientific article
- scientific article; zbMATH DE number 4079483
Extremal problems in graph theory (05C35) Searching and sorting (68P10) Combinatorial aspects of finite geometries (05B25) Generalized Ramsey theory (05C55)
Cites Work
- Eigenvalues and expanders
- Intersection theorems with geometric consequences
- Parallelism in Comparison Problems
- Explicit Concentrators from Generalized N-Gons
- Asymptotic lower bounds for Ramsey functions
- Sorting in \(c \log n\) parallel steps
- Title not available (Why is that?)
- Superconcentrators
- \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
- Explicit constructions of linear-sized superconcentrators
- Title not available (Why is that?)
- Better expanders and superconcentrators
- Sorting and Selecting in Rounds
- Time-space tradeoffs for computing functions, using connectivity properties of their circuits
- Sorting in one round
- Graph-theoretic properties in computational complexity
- A note on time-space tradeoffs for computing continuous functions
- Parallel sorting
- On Concentrators, Superconcentrators, Generalizers, and Nonblocking Networks
- Parallel Sorting with Constant Time for Comparisons
- Title not available (Why is that?)
- Sorting and Merging in Rounds
- Asymptotically tight bounds on time-space trade-offs in a pebble game
- Space bounds for a game on graphs
- Title not available (Why is that?)
Cited In (42)
- The hardest halfspace
- Ramanujan edge-indexed graphs
- Domination in transitive colorings of tournaments
- Title not available (Why is that?)
- More on configurations in Priestley spaces, and some new problems
- Pach's selection theorem does not admit a topological extension
- Generalisations of matrix partitions: complexity and obstructions
- The size Ramsey number of a directed path
- Constant time parallel sorting: An empirical view.
- On embeddings of finite metric spaces in \(l^n_\infty \)
- Highly symmetric expanders
- The number of submatrices of a given type in a Hadamard matrix and related results
- Extending Erdős-Beck's theorem to higher dimensions
- Sorting in rounds
- Universal traversal sequences for expander graphs
- A Ramsey type problem concerning vertex colourings
- Random Cayley graphs and expanders
- Ramanujan graphs
- Parallel comparison algorithms for approximation problems
- The size-Ramsey number of trees
- Fast algorithms for general spin systems on bipartite expanders
- Incidence bounds for block designs
- Sign rank versus Vapnik-Chervonenkis dimension
- On the second eigenvalue of hypergraphs
- Elementary methods for incidence problems in finite fields
- \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
- Scalable secure storage when half the system is faulty
- On distinct perpendicular bisectors and pinned distances in finite fields
- On the spectrum of projective norm-graphs
- Dense expanders and pseudo-random bipartite graphs
- Unimodular graphs and Eisenstein sums
- Simple proofs for Furstenberg sets over finite fields
- Hardness of fully dense problems
- A sample of samplers: a computational perspective on sampling
- Number of directions determined by a set in \(\mathbb{F}_q^2\) and growth in \(\mathrm{Aff}(\mathbb{F}_q)\)
- Non-representability of finite projective planes by convex sets
- Candidate one-way functions based on expander graphs
- On the growth rate in SL2(Fp)${\rm SL_2}(\mathbb {F}_p)$, the affine group and sum‐product type implications
- On the number of flats spanned by a set of points in \(PG(d,q)\)
- Embedding graphs with bounded degree in sparse pseudorandom graphs
- Constructive bounds for a Ramsey-type problem
- The conjunctive complexity of quadratic Boolean functions
This page was built for publication: Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q579273)
