Dimension expanders (Q2474479): Difference between revisions
From MaRDI portal
Changed an Item |
ReferenceBot (talk | contribs) Changed an Item |
||
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 |
Latest revision as of 17: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