Dimension expanders (Q2474479): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(6 intermediate revisions by 5 users not shown) | |||
Property / author | |||
Property / author: Alexander Lubotzky / rank | |||
Property / author | |||
Property / author: Q1296180 / rank | |||
Property / reviewed by | |||
Property / reviewed by: Marston D. E. Conder / rank | |||
Property / author | |||
Property / author: Alexander Lubotzky / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Efim I. Zelmanov / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Marston D. E. Conder / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W4213098650 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 0804.0481 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Towards dimension expanders over finite fields / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The amenability of affine algebras / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The amenability and non-amenability of skew fields / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Universal lattices and unbounded rank expanders. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Symmetric groups and expanders / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Universal lattices and property \(\tau\) / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Discrete groups, expanding graphs and invariant measures. Appendix by Jonathan D. Rogawski / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4841310 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3997989 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 18:28, 27 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Dimension expanders |
scientific article |
Statements
Dimension expanders (English)
0 references
6 March 2008
0 references
For any real \(\epsilon > 0\), an \(\epsilon\)-dimension expander is a pair \((V, \, \{T_i\}_{1 \leq i \leq k})\) consisting of a vector space \(V\) of finite dimension \(n\) over some field and a set of \(k\) linear transformations from \(V\) to \(V\) having the property that \[ \dim(W + \sum_{1\leq i\leq k} T_{i}(W)) \geq (1+\epsilon)\dim W \] for every subspace \(W\) of \(V\) with \(\dim W \leq {n \over 2}\). This notion generalizes the special case of an expander graph obtained as a Schreier graph for a finitely-generated permutation group, essentially replacing permutation representations by linear representations. The authors answer a question by \textit{A. Wigderson} [Lecture at IPAM, UCLA, February 2004] concerning \(\epsilon\)-dimension expanders of arbitrarily large dimension by proving that there exist \(k\) and \(\epsilon\) such that for every field \(F\) of characteristic zero and for every \(n\), explicit \(F\)-linear transformations \(T_i \! : F^n \to F^n\) can be found such that \((F^n, \, \{T_i\}_{1 \leq i \leq k})\) is an \(\epsilon\)-dimension expander. Their construction uses unitary group representations that are bounded away from the trivial representation in the sense of the Fell topology on the unitary dual of the group. Over finite fields (and more generally, fields of positive characteristic), the situation is more difficult, and left open, however, the authors report on some progress on this topic by \textit{Z. Dvir} and \textit{A. Shpilka} [Towards dimension expanders over finite fields, Proceedings of the 2008 IEEE 23rd Annual Conference on Computational Complexity (2008)]. They also describe connections between dimension expanders and their own work on algebras with property \(\tau\).
0 references
expander
0 references
dimension
0 references
linear transformation
0 references
property \(T\)
0 references
property \(\tau\)
0 references
0 references