Turán and Ramsey problems for alternating multilinear maps
Turán and Ramsey problems for alternating multilinear maps, Discrete Analysis 2023:12, 22 pp. Ramsey's theorem (in its finite version) states that for every positive integer $k$ there exists a positive integer $n$ such that every graph with $n$ vertices contains a clique or an independent set...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Diamond Open Access Journals
2023-08-01
|
| Series: | Discrete Analysis |
| Online Access: | https://doi.org/10.19086/da.84736 |
| _version_ | 1797742033988747264 |
|---|---|
| author | Youming Qiao |
| author_facet | Youming Qiao |
| author_sort | Youming Qiao |
| collection | DOAJ |
| description | Turán and Ramsey problems for alternating multilinear maps, Discrete Analysis 2023:12, 22 pp.
Ramsey's theorem (in its finite version) states that for every positive integer $k$ there exists a positive integer $n$ such that every graph with $n$ vertices contains a clique or an independent set with $k$ vertices. This result is just the beginning of what has become a huge field. Typically, a result in Ramsey theory takes the following form: one is given a structure $S$ and a family $\mathcal S$ of structured subsets of $S$, and the result says that however one colours the elements of $S$ with at most $r$ colours, there must be a substructure $S'\in\mathcal S$ with all its elements of the same colour. For example, it follows from the Hales-Jewett theorem that for every prime $p$ and every pair of positive integers $r$ and $k$ there exists a positive integer $n$ such that however the points of $\mathbb F_p^n$ are coloured with $r$ colours, there must be an affine subspace of $\mathbb F_p^n$ of dimension at least $k$ with all its points of the same colour.
Ramsey theory is not just a collection of attractive theorems, since Ramsey-theoretic results often have surprising applications. Typically, these will tell us that a set must have a subset with one of two very different properties. A simple example of this is the statement that every sequence of real numbers has a subsequence that is either increasing or decreasing (though that can be proved directly with a simpler argument). There are also more complicated examples where one obtains either a highly structured subset or a subset that is "maximally unstructured" in some suitable sense.
Some results that follow this general pattern are not directly deduced from classic results of Ramsey theory; they can therefore be regarded as a kind of extension of Ramsey theory. One such result, a "quantum Ramsey theorem" relevant to this paper, was proved by Nik Weaver in 2016. Define a _quantum system_ to be a linear subspace of $M_n(\mathbb C)$ that contains the identity and is closed under taking adjoints. Given a quantum system $\Lambda$ and a subspace $V\subset\mathbb C^n$, define the _restriction of_ $\Lambda$ _to_ $V$ to be the family $\{PAP:A\in\Lambda\}$, where $P$ is the orthogonal projection from $\mathbb C$ to $V$. Weaver proved that for every $s$ there exists $n$ (the bound obtained is $s^3-s+1$) such that for every quantum family $\Lambda\subset M_n(\mathbb C)$ there is a subspace $V$ of dimension $s$ such that the restriction of $\Lambda$ to $V$ is either as large as possible -- that is, it is isomorphic to $M_s(V)$ -- or as small as possible -- that is, it consists of multiples of $P$ (which from $V$'s perspective look like multiples of the identity).
An interesting example of Weaver's theorem is where $\Lambda$ consists of all diagonal matrices. It is not hard to show that the restriction of $\Lambda$ even to a 2-dimensional subspace must have dimension greater than 1, so, somewhat surprisingly, the theorem yields a subspace $V$ where the restriction is isomorphic to $M_n(V)$. (This becomes less surprising when one notes that if $D$ and $D'$ are diagonal matrices and $P$ is an orthogonal projection, it does not necessarily follow that $PDP$ and $PD'P$ commute.)
The main result of this paper sounds quite similar to Weaver's theorem, but there are important differences that cause it to need a significantly different proof. It concerns alternating bilinear forms. If $U$ is a vector space over a field $\mathbb F$, then an alternating form on $U$ is a bilinear map $f:U\times U\to\mathbb F$ such that $f(u,u)=0$ for every $u\in U$ (which implies that $f(u,v)=-f(u,v)$ for every $u,v\in U$, and conversely if $\mathbb F$ does not have characteristic 2). Write $\Lambda(U)$ for the space of all alternating bilinear forms on $U$. Then the main theorem of this paper states that if $U$ is of high enough dimension, then for every subspace $\mathcal A$ of $\Lambda(U)$, either there is an $s$-dimensional subspace $V$ of $U$ such that the restriction of $\mathcal A$ to $V$ contains just the zero map, or there is a $t$-dimensional subspace $W$ such that the restriction of $\mathcal A$ to $W$ is $\Lambda(W)$.
The bound obtained for the dimension of $U$ is $st^4$. Since this is a power-type bound, it is immediately clear that this result is not a simple consequence of Ramsey's theorem. The important differences between this and Weaver's result are that it works for arbitrary fields, and that diagonal matrices, which play a key role in Weaver's arguments, are absent here.
An indication that this is a natural direction to pursue, and not just a problem formulated for the sake of it, is that it can be reformulated as a statement about $p$-groups. It says that among $p$-groups that are nilpotent of order 2 (that is, the commutators $xyx^{-1}y^{-1}$ commute with all other elements) every sufficiently large group $G$ has a subgroup $S$ with one of the following two properties.
1. $S[G,G]/[G,G]$ is isomorphic to $\mathbb F_p^s$.
2. $S$ is isomorphic to the free nilpotent $p$-group of order 2 with $t$ generators.
The free nilpotent $p$-group of order 2 on $t$ generators $x_1,\dots,x_t$ is the group with all relations of the form $u^t=e$ and $u[v,w]=[v,w]u$, where $u,v,w$ are arbitrary words.
Very roughly, this says that $G$ has a subgroup that is either as structured as possible (modulo the commutator subgroup $[G,G]$ it is Abelian) or as unstructured as possible (it is free, up to the constraints that it is contained in a $p$-group that is nilpotent of order 2).
The paper contains a discussion of several other interesting connections with different parts of mathematics, as well as some natural conjectures, which include in particular a conjecture that would extend the main result of this paper from bilinear to multilinear forms. Thus, as well as proving Ramsey-theoretic results with attractive and non-obvious statements, it is potentially opening up a new subfield of Ramsey theory. |
| first_indexed | 2024-03-12T14:35:13Z |
| format | Article |
| id | doaj.art-58d137303c6a4addb83213106eb38489 |
| institution | Directory Open Access Journal |
| issn | 2397-3129 |
| language | English |
| last_indexed | 2024-03-12T14:35:13Z |
| publishDate | 2023-08-01 |
| publisher | Diamond Open Access Journals |
| record_format | Article |
| series | Discrete Analysis |
| spelling | doaj.art-58d137303c6a4addb83213106eb384892023-08-17T09:04:36ZengDiamond Open Access JournalsDiscrete Analysis2397-31292023-08-01Turán and Ramsey problems for alternating multilinear mapsYouming QiaoTurán and Ramsey problems for alternating multilinear maps, Discrete Analysis 2023:12, 22 pp. Ramsey's theorem (in its finite version) states that for every positive integer $k$ there exists a positive integer $n$ such that every graph with $n$ vertices contains a clique or an independent set with $k$ vertices. This result is just the beginning of what has become a huge field. Typically, a result in Ramsey theory takes the following form: one is given a structure $S$ and a family $\mathcal S$ of structured subsets of $S$, and the result says that however one colours the elements of $S$ with at most $r$ colours, there must be a substructure $S'\in\mathcal S$ with all its elements of the same colour. For example, it follows from the Hales-Jewett theorem that for every prime $p$ and every pair of positive integers $r$ and $k$ there exists a positive integer $n$ such that however the points of $\mathbb F_p^n$ are coloured with $r$ colours, there must be an affine subspace of $\mathbb F_p^n$ of dimension at least $k$ with all its points of the same colour. Ramsey theory is not just a collection of attractive theorems, since Ramsey-theoretic results often have surprising applications. Typically, these will tell us that a set must have a subset with one of two very different properties. A simple example of this is the statement that every sequence of real numbers has a subsequence that is either increasing or decreasing (though that can be proved directly with a simpler argument). There are also more complicated examples where one obtains either a highly structured subset or a subset that is "maximally unstructured" in some suitable sense. Some results that follow this general pattern are not directly deduced from classic results of Ramsey theory; they can therefore be regarded as a kind of extension of Ramsey theory. One such result, a "quantum Ramsey theorem" relevant to this paper, was proved by Nik Weaver in 2016. Define a _quantum system_ to be a linear subspace of $M_n(\mathbb C)$ that contains the identity and is closed under taking adjoints. Given a quantum system $\Lambda$ and a subspace $V\subset\mathbb C^n$, define the _restriction of_ $\Lambda$ _to_ $V$ to be the family $\{PAP:A\in\Lambda\}$, where $P$ is the orthogonal projection from $\mathbb C$ to $V$. Weaver proved that for every $s$ there exists $n$ (the bound obtained is $s^3-s+1$) such that for every quantum family $\Lambda\subset M_n(\mathbb C)$ there is a subspace $V$ of dimension $s$ such that the restriction of $\Lambda$ to $V$ is either as large as possible -- that is, it is isomorphic to $M_s(V)$ -- or as small as possible -- that is, it consists of multiples of $P$ (which from $V$'s perspective look like multiples of the identity). An interesting example of Weaver's theorem is where $\Lambda$ consists of all diagonal matrices. It is not hard to show that the restriction of $\Lambda$ even to a 2-dimensional subspace must have dimension greater than 1, so, somewhat surprisingly, the theorem yields a subspace $V$ where the restriction is isomorphic to $M_n(V)$. (This becomes less surprising when one notes that if $D$ and $D'$ are diagonal matrices and $P$ is an orthogonal projection, it does not necessarily follow that $PDP$ and $PD'P$ commute.) The main result of this paper sounds quite similar to Weaver's theorem, but there are important differences that cause it to need a significantly different proof. It concerns alternating bilinear forms. If $U$ is a vector space over a field $\mathbb F$, then an alternating form on $U$ is a bilinear map $f:U\times U\to\mathbb F$ such that $f(u,u)=0$ for every $u\in U$ (which implies that $f(u,v)=-f(u,v)$ for every $u,v\in U$, and conversely if $\mathbb F$ does not have characteristic 2). Write $\Lambda(U)$ for the space of all alternating bilinear forms on $U$. Then the main theorem of this paper states that if $U$ is of high enough dimension, then for every subspace $\mathcal A$ of $\Lambda(U)$, either there is an $s$-dimensional subspace $V$ of $U$ such that the restriction of $\mathcal A$ to $V$ contains just the zero map, or there is a $t$-dimensional subspace $W$ such that the restriction of $\mathcal A$ to $W$ is $\Lambda(W)$. The bound obtained for the dimension of $U$ is $st^4$. Since this is a power-type bound, it is immediately clear that this result is not a simple consequence of Ramsey's theorem. The important differences between this and Weaver's result are that it works for arbitrary fields, and that diagonal matrices, which play a key role in Weaver's arguments, are absent here. An indication that this is a natural direction to pursue, and not just a problem formulated for the sake of it, is that it can be reformulated as a statement about $p$-groups. It says that among $p$-groups that are nilpotent of order 2 (that is, the commutators $xyx^{-1}y^{-1}$ commute with all other elements) every sufficiently large group $G$ has a subgroup $S$ with one of the following two properties. 1. $S[G,G]/[G,G]$ is isomorphic to $\mathbb F_p^s$. 2. $S$ is isomorphic to the free nilpotent $p$-group of order 2 with $t$ generators. The free nilpotent $p$-group of order 2 on $t$ generators $x_1,\dots,x_t$ is the group with all relations of the form $u^t=e$ and $u[v,w]=[v,w]u$, where $u,v,w$ are arbitrary words. Very roughly, this says that $G$ has a subgroup that is either as structured as possible (modulo the commutator subgroup $[G,G]$ it is Abelian) or as unstructured as possible (it is free, up to the constraints that it is contained in a $p$-group that is nilpotent of order 2). The paper contains a discussion of several other interesting connections with different parts of mathematics, as well as some natural conjectures, which include in particular a conjecture that would extend the main result of this paper from bilinear to multilinear forms. Thus, as well as proving Ramsey-theoretic results with attractive and non-obvious statements, it is potentially opening up a new subfield of Ramsey theory.https://doi.org/10.19086/da.84736 |
| spellingShingle | Youming Qiao Turán and Ramsey problems for alternating multilinear maps Discrete Analysis |
| title | Turán and Ramsey problems for alternating multilinear maps |
| title_full | Turán and Ramsey problems for alternating multilinear maps |
| title_fullStr | Turán and Ramsey problems for alternating multilinear maps |
| title_full_unstemmed | Turán and Ramsey problems for alternating multilinear maps |
| title_short | Turán and Ramsey problems for alternating multilinear maps |
| title_sort | turan and ramsey problems for alternating multilinear maps |
| url | https://doi.org/10.19086/da.84736 |
| work_keys_str_mv | AT youmingqiao turanandramseyproblemsforalternatingmultilinearmaps |