# Learning Action-Effect Dynamics from Pairs of Scene-graphs

Written by AAAI Press Staff1
AAAI Style Contributions by Pater Patel Schneider, Sunil Issar,
J. Scott Penberthy, George Ferguson, Hans Guesgen, Francisco Cruz, Marc Pujol-
Gonzalez With help from the AAAI Publications Committee.

###### Abstract

‘Actions’ play a vital role in how humans interact with the world. Thus,
autonomous agents that would assist us in everyday tasks also require the
capability to perform ‘Reasoning about Actions & Change’ (RAC). Recently,
there has been growing interest in the study of RAC with visual and linguistic
inputs. Graphs are often used to represent semantic structure of the visual
content (i.e. objects, their attributes and relationships among objects),
commonly referred to as scene-graphs. In this work, we propose a novel method
that leverages scene-graph representation of images to reason about the
effects of actions described in natural language. We experiment with existing
CLEVR_HYP (Sampat et al. 2021) dataset and show that our proposed approach is
effective in terms of performance, data efficiency, and generalization
capability compared to existing models.

## Introduction

Reasoning about ‘Actions’ is important for humans as it helps us to predict if
a sequence of actions will lead us to achieve a desired goal; to explain
observations i.e. what actions may have taken place; and to diagnose faults
i.e. identifying actions that may have resulted in undesirable situation
(Baral 2010). As we are developing autonomous agents that can assist us in
performing everyday tasks, they would also require to interact with complex
environments. As pointed out by Davis and Marcus (2015), imagine a guest asks
a robot for a glass of wine; if the robot sees that the glass is broken or has
a dead cockroach inside, it should not simply pour the wine. Similarly, if a
cat runs in front of a house-cleaning robot, the robot should neither run it
over nor put it away on a shelf. Hence, the ability of artificial agents to
perform reasoning about actions is highly desirable.

Figure 1: Two possible ways (LS1 and LS2) to learn action-effect dynamics in a
supervised learning setting. In this paper, we implement LS2 which
demonstrates improvements over LS1. Blue box denotes vector representation.

As a result, Reasoning about Action and Change (RAC) has been a long-
established research problem, since the rise of Artificial Intelligence (AI).
McCarthy et al. (1960) were the first to emphasize on reasoning about effects
of actions. They developed an advice taker system that can do deductive
reasoning about scenarios such as “going to the airport from home” requires
“walking to the car” and “driving the car to airport”. Since then, many real-
life use cases have been identified which require AI models to understand
interactions among the states of the world, actions being performed, and most
likely following states (Banerjee et al. 2020).

While RAC has been more popular among knowledge representation and logic
community, it has recently piqued the interest of NLP and vision researchers.
A recent survey by Sampat et al. (2022) compiled a comprehensive list of works
that explore neural network’s ability to reason about actions and changes,
provided linguistic and/or visual inputs. Specifically, the works of Park et
al. (2020); Sampat et al. (2021); Shridhar et al. (2020); Yang et al. (2021);
Gao et al. (2018); Patel et al. (2022) are quite relevant.

In Figure 1, we describe two possible action-effect learning strategies (LS1
and LS2) through a toy example to convey our intuition behind this work. LS1
uses visual features (i.e. features from the image of an apple) and action
representation (of text “rotten”) learned through sentence embedding to
imagine effects (i.e. how a rotten apple would look like). LS1 has been an
intuitive choice to model action-effect learning in a supervised setting in
previous literature. In our hypothesis, LS1 does not improve the model’s
understanding of what effects the actions will produce. Thus, we propose
alternative strategy LS2. Specifically, we let the model observe the
difference between pairs of states before and after the action is performed
(i.e. decayed portion of the apple that distinguishes a good apple from the
rotten one), then associate those visual differences with the corresponding
linguistic action descriptions (i.e. text “rotten”). LS2 is likely to better
capture action-effect dynamics, as action representations are learned
explicitly.

## CLEVR_HYP Dataset (Sampat et al. 2021)

In this section, we summarize important aspects of CLEVR_HYP and terminology
used in subsequent sections.

### Problem Formulation

The task aims at understanding changes caused over an image by performing an
action described in natural language and then answering a reasoning question
over the resulting scene. Figure 2 shows an example from the dataset;

  * •

Inputs:

    1. 1.

Image (I)- Visual scene with rendered objects

    2. 2.

Action Text (TA)- Text describing action to be performed over I

    3. 3.

Question (QH)- Question to assess the system’s ability to understand changes
caused by TA on I

  * •

Output: Answer (A) for the given QH

  * •

Answer Vocabulary: [0-9, yes, no, cylinder, sphere, cube, small, big, metal,
rubber, red, green, gray, blue, brown, yellow, purple, cyan]

  * •

Evaluation: 27-way Answer Classification / Accuracy (%)

Figure 2: An example from the CLEVR_HYP dataset

### Dataset Details and Partitions

The CLEVR_HYP dataset assumes to have a closed set of object attributes,
action types, and question reasoning types.

  * •

Object attributes: 5 colors, 3 shapes, 2 sizes, 2 materials

  * •

Action types: Add object, Remove object(s), Change attribute, Move object (in-
plane and out-of-plane)

  * •

Reasoning types: Count objects, Compare objects, Existence of objects, Query
attribute and Compare attribute

The dataset is divided into the following partitions;

  * •

Train (67.5k) / Val (13.5k) sets have $<$I, TA, QH, A$>$ tuples along with the
scene-graphs as a visual oracle and functional programs111Originally
introduced in CLEVR (Johnson et al. 2017), ex. question ‘How many red metal
things are there?’ $\sim$ functional program
‘count(filter_color(filter_material(scene(),metal),red))’ as a textual oracle.

  * •

Test sets consist of only $<$I, TA, QH, A$>$ tuples, and no oracle annotations
available. There are three test sets,

    1. 1.

Ordinary test (13.5k) consists of examples with the same difficulty as
train/val

    2. 2.

2HopTA test (1.5k) consists of examples where two actions are performed ex.
‘Move a purple object on a red cube then paint it cyan.’

    3. 3.

2HopQH test (1.5k) consists of examples where two reasoning types are combined
ex. ‘How many objects are either red or cylinder?’

### Baseline Models

Following are two top-performing baselines reported in Sampat et al. (2021),
to which we will compare the results of our proposed approach in this paper.

  * •

(TIE) Text-conditioned Image Editing: Text-adaptive encoder-decoder with
residual gating (Vo et al. 2019) is used to generate new image conditioned on
the action text. Then, new image along with the question is fed into LXMERT
(Tan and Bansal 2019) (which is a pre-trained vision-language transformer), to
generate an answer.

  * •

(SGU) Scene-graph Update: In this model, understanding changes caused by an
action text is considered as a graph-editing problem. First, an image is
converted into a scene-graph and action text is converted into a functional
program (FP). Sampat et al. (2021) developed a module inspired by Chen et al.
(2020) that can generate an updated scene graph provided the initial scene-
graph and a functional program of action text. It is followed by a neural-
symbolic VQA model (Yi et al. 2018) that can generate an answer to the
question provided the updated scene-graph.

## Proposed Model: Action Representation Learner (ARL)

In this section, we describe the architecture of our proposed model Action
Representation Learner (ARL). Our hypothesis is that a model can learn better
action representations by observing difference between a pair of states
(before and after the action is performed) and then associate those visual
differences with linguistic description of actions. We create a 3-stage model
shown in Figure 3, which we believe would better capture the causal structure
of this task.

### Stage-1

This stage comprises an ‘Action Encoder’ and an ‘Effect Decoder’. As described
in previous section, the training set of CLEVR_HYP provides oracle annotations
for an initial scene-graph S (using which the image is rendered) and a scene-
graph after executing the action text S′. We take a random subset of 20k
scene-graph pairs from the training set balanced by action types (add, remove,
change, move) to train this encoder-decoder.

We capture the difference between states S and S′ i.e. A${}_{S,S^{\prime}}$
using the encoder. At the test time, we do not have the updated scene-graph S′
available. To address this issue, the encoder is followed by a decoder, which
can reconstruct S′ provided S and the learned scene difference
A${}_{S,S^{\prime}}$. We jointly train encoder-decoder with the following
objective;

$argmax_{\Theta_{ActionEncoder}\Theta_{EffectDecoder}}\\\
[logP({\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}S^{\prime}}|\frac{}{}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}S},\frac{}{}ActionEncoder({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}S},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}S^{\prime}}))]$
(1)

Figure 3: Detailed visualization of our proposed 3-stage Action Representation
Learner (ARL) model: (left) training phase (right) testing phase (bottom)
terms and notations used. Best viewed in color.

### Stage-2

We assume changes in the scene as a function of action. However we can obtain
Arep i.e. vector representation of natural language action, and it can be
trained to approximate A${}_{S,S^{\prime}}$ (from Stage-1). Specifically, we
freeze encoder-decoder trained in Stage-1 and learn ‘Natural language to
Action Representation’ module that maximizes the following log probability;

$argmax_{\Theta_{NL2ActionRep}}\\\
[logP({\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}S^{\prime}}|\frac{}{}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}S},\frac{}{}NL2ActionRep({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}T_{A}}))]$
(2)

Inside this module lies LSTM encoder, which precedes by an embedding layer and
followed by dense layers. During training, in addition to finding the values
for the weights of the LSTM and dense layers, the word embeddings for each
word in the training set are computed. This way, a fixed length vector is
generated for each word in the vocabulary depending on the position of the
word in context and updated using back-propagation. The LSTM has a hidden
layer of size 200.

### Stage-3

Stage-3 combines modules trained in Stage-1 and Stage-2 with off-the-shelf
‘Image to Scene-graph’ and ‘Scene-graph Question Answering’ networks.
Specifically, ‘Image to Scene-graph’ is Mask R-CNN (He et al. 2017) followed
by a ResNet-34 (He et al. 2016), that classifies visual attributes- color,
material, size, and shape and obtains 3D coordinates of each object in the
scene. The ‘Scene-graph Question Answering’ network is based on (Yi et al.
2018), which has near-perfect accuracy on the scene-graph question answering
task over CLEVR (Johnson et al. 2017).

## Results and Analysis

### Quantitative Results

In this section, we discuss performance of our model quantitatively and
qualitatively. We also discuss three ablations conducted for our model.

Evaluation Metric: The classification task of CLEVR_HYP has exactly one
correct answer. Therefore, the exact match accuracy (%) metric is used for
evaluation.

Test performance on CLEVR_HYP(%)
---
|  | TIE | SGU | ARL
Ordinary |  | 64.7 | 70.5 | 76.4
2HopAT |  | 55.6 | 64.4 | 69.2
2HopQH |  | 58.7 | 66.5 | 70.7
Table 1: Performance of two baselines (TIE, SGU) reported in (Sampat et al.
2021) and our proposed model (ARL) on three test sets of CLEVR_HYP

Our experimental results are summarized in Table 1. Our proposed approach
(ARL) outperforms existing baselines by 5.9%, 4.8% and 4.2% on Ordinary,
2HopTA Test and 2HopQH Test respectively. This demonstrates that our model not
only achieves better overall accuracy but also has improved generalization
capability when multiple actions have to be performed on the image or
understand logical combinations of attributes while performing reasoning.

### Qualitative results

Figure 4: Correct scene-graph predictions for the given input image and action
text by our ARL model

In Figure 4, we visually demonstrate scene-graphs predicted by our ARL model
over a variety of action texts. From examples 1-2, we can observe that the
model can correctly identify objects that match the object attributes (color,
size, shape, material) provided in the action text. Examples 3-4 demonstrate
that our system is consistent in predictions when we use synonyms of various
words (e.g. sphere$\sim$ball, shiny$\sim$metallic) in the dataset. Finally,
examples 5-6 show that our model does reasonably well on other actions (add
and change).

We further generate a t-SNE plot of action vectors learned by our best
proposed model, which is shown in Figure 5. At a first glance, we can say that
the learned action representations formulate well-defined and separable
clusters corresponding to each action type. Clusters for add, remove and
change actions are closer and somewhat overlapping.

Figure 5: The t-SNE plot of learned action vectors

### Ablations

#### Importance of Stage-1 training

Cause-effect learning with respect to actions is a key focus in CLEVR_HYP. In
existing models, it is formulated as a updated scene-graph prediction task
(i.e. given an initial scene and an action, determine what the resulting scene
would look like after executing the action). In our opinion, Stage-1 plays a
critical role in learning causal structure of the world. To demonstrate this,
we set up two experiments; first, where training takes place in a sequential
manner (Stage-1 followed by Stage-2), where trained encoder-decoders from
Stage-1 are frozen and utilized in Stage-2. Second experiment, where there is
no separate Stage-1 training and encoder-decoder in Stage-2 are randomly
initialized.

Figure 6: Performance of our model with varying (top) data size and (bottom) action vector lengths Task | Experiment | Accuracy (%)
---|---|---
Scene-graph Update | Stage(2 only) | 56.3
Stage(1+2) | 87.2
Question Answering | Stage(2+3 only) | 45.7
Stage(1+2+3) | 76.4
Table 2: Performance of our model in the absence and presence of stage-1 over
ordinary test set

The results are summarized in Table 2. We can observe that inclusion of
Stage-1 training improves the accuracy of scene-graph prediction by $\sim$30%
compared to the Stage(2 only) model. To evaluate question answering task of
CLEVR_HYP, both setups are followed by Stage-3 where the image to scene-graph
generator and scene-graph question answering modules are combined to predict
the answer. It is known that (Yi et al. 2018) has near-perfect performance on
the scene-graph question answering task over CLEVR (Johnson et al. 2017). As a
result, the gains achieved in the scene-graph task directly benefit the
question answering performance without much of a loss. In other words, there
are only 0.2% instances where the scene prediction is correct but the final
answer is incorrect.

#### Performance with different data size used for training Stage-1

In this ablation, the goal is to find out how many scene-graph pairs are
required to effectively learn effects of the actions. We experiment with
different data sizes- from 2k to 25k samples. Figure 6 (top) shows the effect
of training with diverse training data size on scene-graph update and
downstream question answering task. The model learns better initially with
more data samples, however performance saturates after 20k samples.

#### Performance with different lengths of learned action vector in Stage-1

In this ablation, the goal is to find out optimal length of action vectors
that can reasonably simulate the effects of the actions. We experiment with
different lengths of learned action vector- from 25 to 200 in increment of 25.
Figure 6 (bottom) shows the effect of training with diverse action vector
lengths on scene-graph update and downstream question answering task. The
model learns better initially when the vector length is increased, however
performance reaches at peak for the action vector length of 125.

## Conclusion

In the vision and language domain, several tasks are proposed that require an
understanding of the causal structure of the world. In this work, we propose
an effective way of learning action representations and implement a 3-stage
model for the what-if vision-language reasoning task CLEVR_HYP. We provide
insights on the learned action representations and validate the effectiveness
of our proposed method through ablations. Finally, we demonstrate that our
proposed method outperforms existing baselines while being data-efficient and
showing some degree of generalization capability. By extending our approach to
a larger set of actions, we aim to develop AI agents which are equipped with
action-effect reasoning capability and can better collaborate with humans in
the physical world.

## References

  * Banerjee et al. (2020) Banerjee, P.; Baral, C.; Luo, M.; Mitra, A.; Pal, K.; Son, T. C.; and Varshney, N. 2020.  Can Transformers Reason About Effects of Actions?  _arXiv preprint arXiv:2012.09938_.
  * Baral (2010) Baral, C. 2010.  Reasoning about actions and change: from single agent actions to multi-agent actions.  In _In KR_.
  * Chen et al. (2020) Chen, L.; Lin, G.; Wang, S.; and Wu, Q. 2020.  Graph edit distance reward: Learning to edit scene graph.  In _European Conference on Computer Vision_ , 539–554. Springer.
  * Davis and Marcus (2015) Davis, E.; and Marcus, G. 2015.  Commonsense reasoning and commonsense knowledge in artificial intelligence.  _In Communications of ACM_.
  * Gao et al. (2018) Gao, Q.; Yang, S.; Chai, J.; and Vanderwende, L. 2018.  What action causes this? towards naive physical action-effect prediction.  In _In ACL_.
  * He et al. (2017) He, K.; Gkioxari, G.; Dollár, P.; and Girshick, R. B. 2017.  Mask R-CNN.  In _IEEE International Conference on Computer Vision, ICCV 2017, Venice, Italy, October 22-29, 2017_ , 2980–2988. IEEE Computer Society.
  * He et al. (2016) He, K.; Zhang, X.; Ren, S.; and Sun, J. 2016.  Deep Residual Learning for Image Recognition.  In _2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas, NV, USA, June 27-30, 2016_ , 770–778. IEEE Computer Society.
  * Johnson et al. (2017) Johnson, J.; Hariharan, B.; van der Maaten, L.; Fei-Fei, L.; Zitnick, C. L.; and Girshick, R. B. 2017.  CLEVR: A Diagnostic Dataset for Compositional Language and Elementary Visual Reasoning.  In _2017 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017, Honolulu, HI, USA, July 21-26, 2017_ , 1988–1997. IEEE Computer Society.
  * McCarthy et al. (1960) McCarthy, J.; et al. 1960.  _Programs with common sense_.  RLE and MIT computation center Cambridge, MA, USA.
  * Park et al. (2020) Park, J. S.; Bhagavatula, C.; Mottaghi, R.; Farhadi, A.; and Choi, Y. 2020.  Visualcomet: Reasoning about the dynamic context of a still image.  In _In ECCV_.
  * Patel et al. (2022) Patel, M.; Gokhale, T.; Baral, C.; and Yang, Y. 2022.  Benchmarking Counterfactual Reasoning Abilities about Implicit Physical Properties.  In _NeurIPS 2022 Workshop on Neuro Causal and Symbolic AI (nCSI)_.
  * Sampat et al. (2021) Sampat, S. K.; Kumar, A.; Yang, Y.; and Baral, C. 2021.  CLEVR_HYP: A Challenge Dataset and Baselines for Visual Question Answering with Hypothetical Actions over Images.  In _In NAACL:HLT_.
  * Sampat et al. (2022) Sampat, S. K.; Patel, M.; Das, S.; Yang, Y.; and Baral, C. 2022.  Reasoning about Actions over Visual and Linguistic Modalities: A Survey.  _arXiv preprint arXiv:2207.07568_.
  * Shridhar et al. (2020) Shridhar, M.; Thomason, J.; Gordon, D.; Bisk, Y.; Han, W.; Mottaghi, R.; Zettlemoyer, L.; and Fox, D. 2020.  Alfred: A benchmark for interpreting grounded instructions for everyday tasks.  In _In CVPR_.
  * Tan and Bansal (2019) Tan, H.; and Bansal, M. 2019.  LXMERT: Learning Cross-Modality Encoder Representations from Transformers.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , 5100–5111. Association for Computational Linguistics.
  * Vo et al. (2019) Vo, N.; Jiang, L.; Sun, C.; Murphy, K.; Li, L.; Fei-Fei, L.; and Hays, J. 2019\.  Composing Text and Image for Image Retrieval - an Empirical Odyssey.  In _IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2019, Long Beach, CA, USA, June 16-20, 2019_ , 6439–6448. Computer Vision Foundation / IEEE.
  * Yang et al. (2021) Yang, Y.; Panagopoulou, A.; Lyu, Q.; Zhang, L.; Yatskar, M.; and Callison-Burch, C. 2021.  Visual Goal-Step Inference using wikiHow.  In _In EMNLP_.
  * Yi et al. (2018) Yi, K.; Wu, J.; Gan, C.; Torralba, A.; Kohli, P.; and Tenenbaum, J. 2018.  Neural-Symbolic VQA: Disentangling Reasoning from Vision and Language Understanding.  In _Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada_ , 1039–1050.


#  Some remarks on off-diagonal Ramsey numbers
for vector spaces over $\mathbb{F}_{2}$

Zach Hunter Department of Mathematics, ETH, Zürich, Switzerland. Email:
<EMAIL_ADDRESS>Cosmin Pohoata Department of Mathematics, Emory
University, Atlanta, GA. Email<EMAIL_ADDRESS>Research supported
by NSF Award DMS-2246659.

###### Abstract

For every positive integer $d$, we show that there must exist an absolute
constant $c>0$ such that the following holds: for any integer $n\geqslant
cd^{7}$ and any red-blue coloring of the one-dimensional subspaces of
$\mathbb{F}_{2}^{n}$, there must exist either a $d$-dimensional subspace for
which all of its one-dimensional subspaces get colored red or a
$2$-dimensional subspace for which all of its one-dimensional subspaces get
colored blue. This answers recent questions of Nelson and Nomoto, and confirms
that for any even plane binary matroid $N$, the class of $N$-free, claw-free
binary matroids is polynomially $\chi$-bounded.

Our argument will proceed via a reduction to a well-studied additive
combinatorics problem, originally posed by Green: given a set
$A\subset\mathbb{F}_{2}^{n}$ with density $\alpha\in[0,1]$, what is the
largest subspace that we can find in $A+A$? Our main contribution to the story
is a new result for this problem in the regime where $1/\alpha$ is large with
respect to $n$, which utilizes ideas from the recent breakthrough paper of
Kelley and Meka on sets of integers without three-term arithmetic
progressions.

##  1 Introduction

For every two positive integers $s$ and $d$, let $R_{\mathbb{F}_{2}}(s,d)$
denote the smallest integer $n$ such that in every red-blue coloring of all
the one-dimensional subspaces of $\mathbb{F}_{2}^{n}$ there must exist either
a $d$-dimensional subspace for which all of its one-dimensional subspaces get
colored red or an $s$-dimensional subspace for which all of one-dimensional
subspaces get colored blue. This quantity was first introduced in 1972 (in
much greater generality) by Graham, Leeb and Rothschild [14], who showed that
$R_{\mathbb{F}_{2}}(s,d)$ is finite for every choice of $s$ and $d$. The
result was subsequently simplified (and generalized) by Spencer in [24],
however the quantitative bounds implied by either of these arguments are all
rather poor, due to the repeated uses of the Hales-Jewett Theorem. Despite the
rich activity on their combinatorial counterparts over the years, there hasn’t
been much progress on these Ramsey numbers since.

In [19], Nelson and Nomoto established a new connection between
$R_{\mathbb{F}_{2}}(2,d)$ and the $\chi$-boundedness of certain classes of
binary matroids, which in some sense reignited interest for this problem.
Recall that a class $\mathcal{M}$ of matroids is $\chi$-bounded by a function
$f$ if $\chi(M)\leqslant f(\omega(M))$ for all $M\in\mathcal{M}$, and that
$\mathcal{M}$ is $\chi$-bounded if it is $\chi$-bounded by some $f$. For a
simple binary $n$-dimensional matroid $M=(E,G)$ defined on a finite projective
geometry $G:=\operatorname{PG}(n-1,2)$ and having ground set $E\subset G)$,
$\omega(M)$ denotes the dimension of the largest subgeometry of $M$ contained
in $E$, and $\chi(M):=n-\omega(M)$. These parameters represent natural
analogues of the clique number $\omega(G)$ and the chromatic number $\chi(G)$
of a graph $G$, respectively. See for example [21] for a discussion. A simple
binary matroid is called claw-free if none of its rank-$3$ flats are
independent sets. Unlike claw-free graphs, however, claw-free (simple binary)
matroids are not necessarily $\chi$-bounded [6]: for all $k\geqslant 0$, there
is a so-called even-plane matroid $M$ with $\omega(M)=2$ and $\chi(M)\geqslant
k$. A simple binary matroid $M$ is called an even plane matroid $M$ if all of
its 3-dimensional induced restrictions have even-sized ground sets. It is not
difficult to see that such matroids are claw-free, and so this implies that
the class of claw-free matroids is not $\chi$-bounded. One of the main results
in [19] is that even-plane matroids present the only obstruction to
$\chi$-boundedness.

######  Theorem 1.1 (Nelson-Namoto).

If $N$ is an even-plane matroid, then the class of $N$-free, claw-free
matroids is $\chi$-bounded by the function
$f(d)=R_{\mathbb{F}_{2}}(2,d+1)+d(\dim(N)+4)$.

Moreover, in [19] Nelson and Namoto also showed in that
$R_{\mathbb{F}_{2}}(2,d)\leqslant(d+1)2^{d}$, thus improving upon the bounds
from [14] and [24], and establishing that the class of $N$-free, claw-free
matroids above is $\chi$-bounded by an exponential function. In a very recent
paper [13], Frederickson and Yepremyan further improved this estimate to
$R_{\mathbb{F}_{2}}(2,d)\leqslant 1.566^{d}$ (by using some new ideas which
also allow one to improve upon a few other particular cases of the Graham-
Leeb-Rothschild theorem).

On the other hand, it is well-known that the class of claw-free graphs is
$\chi$-bounded by a quadratic function: in a claw-free graph $G$, each vertex
has the property that its neighborhood has no independent set of size $3$, so
the maximum degree of $G$ is upper bounded by the usual off-diagonal Ramsey
number $R(3,\omega(G)+1)$; see for example [9] and the references therein for
more details. In light of this analogy, it thus seems natural to ask whether
or not it could also be the case that for any even-plane matroid $N$, the
class of $N$-free, claw-free matroids is $\chi$-bounded by a function $f(d)$
that grows only polynomially in $d$ (or in other words, is polynomially
$\chi$-bounded).

In this paper, we settle this question in the affirmative by showing that
$R_{\mathbb{F}_{2}}(2,d)$ is polynomial in $d$. Specifically, our main result
is the following estimate:

######  Theorem 1.2.

For every integer $d\geqslant 1$, there exists an absolute constant $C>0$ such
that:

$R_{\mathbb{F}_{2}}(2,d)\leqslant Cd^{7}.$

This result settles a recent question of Nelson [20], alongside with the
original problem of Nelson-Nomoto from [19] (also reiterated in [13]), which
originally asked to determine whether or not $R_{\mathbb{F}_{2}}(2,d)$ is
subexponential.

The proof of Theorem 1.2 will build upon the original argument from [19], and
provide an upper bound for $R_{\mathbb{F}_{2}}(2,d)$ via a reduction to a
well-studied additive combinatorics problem, originally posed by Green in
[15]: given a set $A\subset\mathbb{F}_{2}^{n}$ with density $\alpha\in[0,1]$,
what is the largest subspace that we can find in $A+A$? To derive a polynomial
bound for $R_{\mathbb{F}_{2}}(2,d)$, we will establish a new result for this
problem in the regime where $1/\alpha$ is large with respect to $n$, by using
ideas from the breakthrough paper of Kelley and Meka on sets of integers
without three-term arithmetic progressions [17]. We will discuss this in
detail in Section 2, after first revisiting the reduction (and where the
exponential bound comes from).

Our argument will also allow us to get strong bounds for the following multi-
color generalization of the function $R_{\mathbb{F}_{2}}(2,d)$. To formulate
this more general statement, it will be convenient to use the following
notation: given a vector space $V$, let ${V\brack k}$ denote as usual the
collection of all $k$-dimensional linear subpaces of $V$. Given an $r$-tuple
of positive integers $(d_{1},\dots,d_{r})$, let
$R_{\mathbb{F}_{2}}(d_{1},\ldots,d_{r})$ denote the smallest $n$, such that
for every $r$-coloring $C:{\mathbb{F}_{2}^{n}\brack 1}\to\\{1,\dots,r\\}$,
there exists some $i\in\\{1,\dots,r\\}$ and a subspace
$V\leqslant\mathbb{F}_{2}^{n}$ of dimension $d_{i}$ such that $C(W)=i$ for all
$1$-dimensional subspaces $W\subset V$. From [14] and [24], we know that
$R_{\mathbb{F}_{2}}(d_{1},\ldots,d_{r})$ is finite for every choice of
$(d_{1},\dots,d_{r})$. In what follows, we establish the following
quantitative improvement when $d_{1}=\ldots=d_{r-1}=2$.

######  Theorem 1.3.

Let $r\geqslant 2$ and let $R_{\mathbb{F}_{2}}^{(r)}(2;d)$ denote the
$r$-color Ramsey number $R_{\mathbb{F}_{2}}(2,\ldots,2,d)$. There exists an
absolute constant $C$ such that the following holds: for every integer
$d\geqslant 1$,

$R_{\mathbb{F}_{2}}^{(r)}(2;d)\leqslant Cr(\log r+d)^{7}.$

This not only recovers Theorem 1.2 in the case when $r=2$, but it also
provides an upper bound of the same quality for all $r\geqslant 2$ (up to
constant factors depending on $r$). We will present the proof of Theorem 1.3
in Section 3, after sketching the argument for two colors in Section 2.

Notational conventions. We will use standard asymptotic notation, as follows.
For functions $f=f(n)$ and $g=g(n)$, we write $f=O(g)$ to mean that there is a
constant $C$ such that $|f(n)|\leqslant C|g(n)|$ for sufficiently large $n$.
Similarly, we write $f=\Omega(g)$ to mean that there is a constant $c>0$ such
that $f(n)\geqslant c|g(n)|$ for sufficiently large n. Finally, we write
$f=\Theta(g)$ to mean that $f=O(g)$ and $g=O(f)$, and we write $f=o(g)$ or
$g=\omega(f)$ to mean that $f(n)/g(n)\to 0$ as $n\to\infty$. We write
$O_{H}(1)$ for some unspecified constant that can be chosen as some bounded
value depending only on $H$. Whenever convenient, we will also use the
Vinogradov notation $f\ll g$ to denote that $f=O(g)$, that is, there exists
some constant $C>0$ such that $f<Cg$. Similarly, we will write $f\gg g$
whenever $g\ll f$.

Given a finite additive abelian group $G$ and a set $A\subset G$, we write
$\mu(A):=|A|/|G|$ for the density of $A$ in $G$. Given two sets $A,X\subset
G$, we write $\mu_{X}(A):=|A\cap X|/|X|$ for the relative density of $A$
inside $X$. We will also use $1_{A}$ to denote the characteristic function of
the set $A$, by $\mu_{A}$ the normalized characteristic function
$\frac{1}{\mu(A)}1_{A}$.

For any two functions $f,g:G\to\mathbb{R}$, we denote by $f\circ g$ the
difference convolution of $f$ and $g$, namely

$f\circ g(x)=\frac{1}{|G|}\sum_{y\in G}f(y)g(x+y).$

Note that $\mu_{A}\circ\mu_{B}(x):=\mathbb{P}(a+b=x)$ where $a\sim A,b\sim B$
are sampled uniformly and independently from their respective sets.

Last but not least, given an integer $k\geqslant 1$, we sometimes use the
shorthand $[k]:=\\{1,\dots,k\\}$. Ggiven a positive real number $a$, we also
write $\mathcal{L}(a)$ to denote the least integer $m\geqslant 1$ such that
$2^{m}a\geqslant 1$.

##  2 Overview of the argument

In the same spirit with the arguments from [19] and [13], our starting point
will be the observation that in order to obtain an upper bound for
$R_{\mathbb{F}_{2}}(2,d)$, it will suffice to study a certain additive
combinatorics problem.

######  Observation 2.1.

If $R_{\mathbb{F}_{2}}(2,d)>n$, then there must exist some
$S\subset\mathbb{F}_{2}^{n}\setminus\\{(0,\ldots,0)\\}$ such that $S+S$ and
the complement $S^{c}:=\mathbb{F}_{2}^{n}\setminus S$ contain no
$d$-dimensional subspaces.

Indeed, let us denote the additive group $\mathbb{F}_{2}^{n}$ by $G$ and the
identity vector $(0,\ldots,0)$ by $0_{G}$ for convenience, and then note that
$R_{\mathbb{F}_{2}}(2,d)>n$ implies the existence of a partition of
$G\setminus\\{0_{G}\\}$ into sets $R$ and $S$ such that:

  * •

$R\cup\\{0_{G}\\}=G\setminus S$ does not contain a $d$-dimensional subspace;

  * •

$S\cup\\{0_{G}\\}$ does not contain a $2$-dimensional subspace.

The second bullet says that $S$ does not contain any pattern of the form
$x,y,x+y$ with $x,y\in\mathbb{F}_{2}^{n}$ and such that $x\neq y$; in other
words, $S$ is sum-free. This implies that $S+S\subset G\setminus S$, which by
the first bullet means that $S+S$ cannot contain a $d$-subspace.

We next note that the complement of $S$ lacking $d$-dimensional subspaces
tells us something about the density of $S$ in $G$. To this end, we recall the
following classical result going back to Bose and Burton [7]:

######  Lemma 2.2.

Let $G=\mathbb{F}_{2}^{n}$ be a vector space, and $S\subset
G\setminus\\{0_{G}\\}$ have density $\sigma:=\mu(S)$. Consider some $d\in[n]$,
and assume $\sigma<1/2^{d}$ so that $|S|<\frac{2^{n}-1}{2^{d}-1}$. Then
$S^{c}$ contains a vector space $V\leqslant G$ with $\dim(V)\geqslant d$.

The above result is sharp up to a factor of $\approx 2$. Indeed, if
$V^{\prime}\subset G$ has dimension $n+1-d$, then $\dim(V^{\prime}\cap
V)\geqslant 1$ for each $V\leqslant G$ with $\dim(V)=d$. Thus, taking
$S=V^{\prime}\setminus\\{0_{G}\\}$, we have that $S^{c}$ contains no subspace
with dimension $d$. In fact, [7, Theorem 2] shows that this construction of
$S$ is the worst-case scenario; however, for the sake of self-containment, we
decided to instead state the slightly weaker version above in order to include
a short probabilistic proof.

###### Proof.

Sample $\mathbf{V}$ uniformly at random among all the $d$-dimensional
subspaces of $G$. For every $s\in G\setminus\\{0_{G}\\}$, we shall prove
$P_{s}:=\mathbb{P}(s\in\mathbf{V})$ is equal to $(2^{d}-1)/(2^{n}-1)$.
Assuming this, the result follows by a union bound, since

$\mathbb{P}(\mathbf{V}\cap
S\neq\emptyset)\leqslant|S|\frac{2^{n}-1}{2^{d}-1}<1.$

To start, note that for $s,s^{\prime}\in G\setminus\\{0_{G}\\}$, there is an
automorphism $\phi:G\to G$ sending $s$ to $s^{\prime}$ (by changing bases
appropriately). Meanwhile, for any automorphism $\phi$, the distribution of
$\phi(\mathbf{V})$ should remain uniform over vector spaces of dimension $d$.
Thus, there is some constant $P$ such that $P_{s}=P$ for all $s\in
G\setminus\\{0_{G}\\}$. By double-counting, we get

$2^{d}-1=\mathbb{E}[|\mathbf{V}\setminus\\{0_{G}\\}|]=\sum_{s\in
G\setminus\\{0_{G}\\}}\mathbb{P}(s\in\mathbf{V})=(2^{n}-1)P,$

which rearranges to give the result. $\Box$

Putting together Observation 2.1 and Lemma 2.2, we arrive at the following
reduction, essentially first noted essentially in [19].

######  Observation 2.3.

If $R_{\mathbb{F}_{2}}(2,d)>n$, then there must exist a subset
$S\subset\mathbb{F}_{2}^{n}$ where $\mu(S)\geqslant 2^{-d}$ and such that
$S+S$ contains no $d$-dimensional subspaces.

This naturally leads us to a well-studied problem in additive combinatorics,
originally posed by Green in [15]: given a set $A\subset\mathbb{F}_{2}^{n}$
with density $\alpha\in[0,1]$, what is the largest subspace that one can find
in $A+A$?

In the case when $\alpha$ is fixed, the best known quantitative result for
this problem comes from [22] (see also [10]).

######  Theorem 2.1 (Sanders).

The exists an absolute constant $c>0$ such that the following holds: for any
subset $A\subset G:=\mathbb{F}_{2}^{n}$, we have that $A+A$ contains a subset
$V\leqslant G$ with

$\dim(V)\geqslant c\mu(A)n.$

Note that Theorem 2.1 combined with Observation 2.3 immediately tells us that

$R_{\mathbb{F}_{2}}(2,d)\leqslant\frac{d}{c}2^{d}<2^{(1+o(1))d}.$

In general, given $n\geqslant 1$ along with $\alpha>0$, define $f(n,\alpha)$
to be the maximal $d$ such that: for every $A\subset\mathbb{F}_{2}^{n}$ with
$\mu(A)\geqslant\alpha$, there exists $d$-subspace
$V\leqslant\mathbb{F}_{2}^{n}$ with $V\subset A+A$. We briefly recall what is
known here. Thus far in the literature, everyone has primarily focused on the
regime where $\alpha>0$ is fixed and then $n$ tends to $\infty$. The best
known upper bound is that, for fixed $\alpha\in(0,1/2)$, we have

$f(n,\alpha)\leqslant n-(C_{\alpha}-o(1))\sqrt{n},$

where $C_{\alpha}>0$ is chosen such that if $X\sim\mathcal{N}(0,1)$ is a
standard Gaussian, then $\mathbb{P}(X<-C_{\alpha})=\alpha$; this is due to a
beautiful “niveau-set construction” where $A$ is taken to be set of vectors
with Hamming weight at most $n/2-(C_{\alpha}/2-o(1))\sqrt{n}$. We refer to
[22, Section 3] for more details. Despite the general belief that this upper
bound is closer to the truth (i.e., that $f(n,\alpha)\geqslant(1-o(1))n$),
Theorem 2.1 remains the ‘state-of-the-art’ in the regime of interest.

###  2.1 Sketch of improvement for two colors

Our new bound for $R_{\mathbb{F}_{2}}(2,d)$ essentially comes from the
following new lower bound for $f(n,\alpha)$.

######  Theorem 2.2.

Given $n\geqslant 1$ and $\alpha>0$,

$f(n,\alpha)+1\gg\left(\frac{n}{\mathcal{L}(\alpha)^{5}}\right)^{1/4}.$ (2.1)

Indeed, note that Theorem 2.2 instantly implies that there exists an absolute
constant $C>0$ such that $f(Cd^{9},2^{-d})\geqslant d$, and by Observation 2.3
this subsequently yields that $R_{\mathbb{F}_{2}}(2,d)=O(d^{9})$. Now, while
this suffices to establish the polynomial growth of $R_{\mathbb{F}_{2}}(2,d)$
(and thus also the polynomial $\chi$-boundedness of the classes of $N$-free,
claw-free matroids, for every even-plane matroid $N$), it is not automatically
enough to get the claimed bound from Theorem 1.2. To achieve that, we will
(implicitly) establish the stronger estimate

$f(n,\alpha)+1\gg\left(\frac{n}{\mathcal{L}(\alpha)^{5}}\right)^{1/2}.$ (2.2)

Before we say more, we would first like to point out that both bounds perform
dramatically worse in the regime where $\alpha$ is fixed and $n$ became very
large (the usual regime of interest for $f(n,\alpha)$). Nevertheless, in the
context of Observation 2.3, we want $1/\alpha$ to be quite large with respect
$n$, which makes this different bound much more useful.

Both of the new lower bounds for $f(n,\alpha)$ from (2.1) and (2.2) can be
proven using recent “approximate Bogolyubov-Ruzsa results”, which have been
made possible by the recent breakthrough paper by Kelley and Meka [17]. In
order to maximize the clarity of the main ideas, in this section we will first
only sketch the proof Theorem 2.2 without addressing (2.2), and then return to
where the improved (2.2) comes from in Section 3, where we will in fact prove
a more general bound of this strength that will allow us to handle the
multicolor case.

Roughly speaking, an “exact Bogolyubov-Ruzsa result” takes a dense subset $A$,
and then finds a large subspace $V$ contained in some type of sumset of $A$
(say $A-A$); meanwhile, an “approximate Bogolyubov-Ruzsa result” instead finds
a large subspace $V$, such that the intersection of $V$ with $A-A$ is at least
a $(1-\epsilon)$-fraction of $V$.

Let us assume the following lemma. This precise form is obtained in the first
author’s manuscript [16], and morally equivalent versions have been mentioned
in [4, 17] (specifically, see [4, Theorem 5] and [17, Section 1.1]).

######  Lemma 2.4 ([16, Lemma 3.2.1]).

Let $G=\mathbb{F}_{2}^{n}$ and $A\subset G$ with $\alpha:=\mu(A)>0$. Given
$\gamma>0$, we can find $V\leqslant G$ with
$\operatorname{codim}(V)\ll\mathcal{L}(\alpha)^{5}\mathcal{L}(\gamma)^{4}$,
such that writing

$D:=\\{v\in V:\mu_{A}\circ\mu_{A}(v)\geqslant\frac{1}{2}\mu(V)^{2}\\}$

to denote the set of “locally popular differences”, we have

$\mu_{V}(D)\geqslant 1-\gamma.$

######  Remark 2.5.

To prove Theorem 2.2, it would be satisfactory to replace ‘$D$’ by ‘$A-A$’.
However, the proof easily gives this stronger form, so we saw no reason not to
mention it.

The important propery here is that the dependence on the codimension is
polylogarithmatically-efficient with respect to both $1/\alpha$ and $1/\gamma$
(which should be optimal, up to the powers of logs).

Given Lemma 2.4, along with Proposition 2.2 from before, we may quickly obtain
Theorem 2.2

###### Proof of Theorem 2.2.

First, let $C_{0}$ be the implicit absolute constant from Lemma 2.4.

Then suppose we are given a non-empty subset $A\subset G:=\mathbb{F}_{2}^{n}$
be given, and write $\alpha:=\mu(A)>0$.

Now, let $C$ be some sufficiently large absolute constant. If
$n<C\mathcal{L}(\alpha)^{5}$, then the conclusion of Thoerem 2.2 is trivially
satisfied by taking $V=\\{0_{G}\\}$ which has dimension
$0\geqslant\frac{1}{C}\left(\frac{n}{\mathcal{L}(\alpha)^{5}}\right)^{1/4}-1$.

Otherwise, by the largeness of $C$, we will have that
$\frac{n}{2C_{0}\mathcal{L}(\alpha)^{5}}>\frac{C}{2C_{0}}>1$. In which case we
may take $\gamma\in(0,1)$ so that
$C_{0}\mathcal{L}(\alpha)^{5}\mathcal{L}(\gamma)^{4}=n/2$, meaning

$\log_{2}(1/\gamma)=\left(\frac{n}{2C_{0}\mathcal{L}(\alpha)^{5}}\right)^{1/4}.$

Write
$d:=\lfloor\left(\frac{n}{2C_{0}\mathcal{L}(\alpha)^{5}}\right)^{1/4}\rfloor$,
so that $\gamma\leqslant 2^{-d}$.

Applying Lemma 2.4 (which holds with the constant $C_{0}$) to the set $A$ and
the constant $\gamma$, we can find some subspace $V\leqslant G$ with
$\dim(V)\geqslant n/2$, such that

$D:=\mu_{V}(\\{v\in
V:\mu_{A}(v)\circ\mu_{A}(v)\geqslant\frac{1}{2}\mu(V)^{2}\\})\geqslant
1-\gamma.$

Noting that $D\subset A-A=A+A$ (recall that $A=-A$, as
$G=\mathbb{F}_{2}^{n}$), it will suffice to show that $D$ contains a $d$-space
(recalling $d\gg(n/\mathcal{L}(\alpha)^{5})^{1/4}$).

We shall prove this using Lemma 2.2. Let $S:=V\setminus D$, so that $D=S^{c}$
(where the complement is taken with respect to $V$). Clearly,
$\mu_{V}(S)\leqslant\gamma\leqslant 2^{-d}$; so we will be done if we can
confirm that the trivial non-degeneracy assumptions in Lemma 2.2 are also
satified.

First, note that $\mu_{A}\circ\mu_{A}(0_{V})=1/\alpha\geqslant 1$, thus
$0_{V}\not\in S$, as desired. Also, without loss of generality, we may suppose
$n\geqslant 4$. Whence, $d\leqslant n/2\leqslant\dim(V)$ (recalling
$d\leqslant n^{1/4}$). This establishes the two non-degeneracy assumptions,
and thus the result. $\Box$

##  3 Proof of Theorem 1.3

To deduce Lemma 2.4, one iterates the following density increment result
(which is implicit in both [4, 17], and appears explicitly in the first
author’s manuscript [16]).

######  Lemma 3.1 ([16, Corollary 2.3.4], in characteristic two).

Let $V\cong\mathbb{F}_{2}^{n}$ be a vector space, and consider $A,C\subset V$
with $\mu(A)=\alpha,\mu(C)=\gamma$. Suppose that
$|\langle\mu_{A}\circ\mu_{A},\mu_{C}\rangle-1|>1/2$.

Then there exists a coset $U=t+V^{\prime}$ where
$\operatorname{codim}(V^{\prime})\ll\mathcal{L}(\alpha)^{4}\mathcal{L}(\gamma)^{2}$
and $\mu_{U}(A)\geqslant(1+1/16)\alpha$.

To get our stronger exponent, we shall utilize the new increment result of
Bloom and Sisask from [5].

######  Lemma 3.2 ([5, Proposition 9], in characteristic two).

Let $V\cong\mathbb{F}_{2}^{n}$ be a vector space, and consider $A,C\subset V$
with $\mu(A)=\alpha,\mu(C)=\gamma$. Suppose that
$|\langle\mu_{A}\circ\mu_{A},\mu_{C}\rangle-1|>1/2$.

Then there exists a coset $U=t+V^{\prime}$ where
$\operatorname{codim}(V^{\prime})\ll\mathcal{L}(\alpha)^{4}\mathcal{L}(\gamma)^{2}$
and $\mu_{U}(A)\geqslant(1+1/128)\alpha$.

We note that the usage of Lemma 3.2 is solely to improve the exponent in the
bound we get. Otherwise, the previous lemma would still suffice to establish a
multicolor bound with reasonably strong bounds.

Our main result will be a variant of a “sparsity-expansion dichotomy”
established by Chapman and Prendiville [8, Theorem 2.1].

######  Proposition 3.1.

Consider subsets $A_{1},\dots,A_{r}\subset G:=\mathbb{F}_{2}^{n}$. For each
$\alpha,\gamma\in(0,1)$, there exists some subspace $V\leqslant G$ with
$\operatorname{codim}(V)\ll r\mathcal{L}(\alpha)^{5}\mathcal{L}(\gamma)^{2}$
such that, for each $i\in[r]$, one of the following holds:

  * •

(Sparsity):

$\mu_{V}(A_{i})<\alpha;$

  * •

(Expansion):

$\mu_{V}(D_{i})>1-\gamma,$

where

$D_{i}:=\\{v\in
V:\mu_{A_{i}}\circ\mu_{A_{i}}(v)\geqslant\frac{1}{2}\mu(V)^{2}\\}.$

With Proposition 3.1 in hand, it will be easy to deduce our multicolor result.
This can be done by setting $\alpha=\gamma:=\frac{1}{10r2^{r}}$, and using the
same sorts of reductions as in the last section. We defer the formal details
to the end of this section, and first discuss the proof of Proposition 3.1. As
in [8, 23], let us start by first considering the following quantity.

Definition: Given a group $G$ and subsets $S,X\subset G$, denote by

$\mu_{X}^{*}(S):=\max_{g\in G}\left\\{\frac{|(g+X)\cap S|}{|X|}\right\\}$

the so-called maximal density of $S$ within (translates of) $X$.

Whenever the underlying group $G$ is the additive group $\mathbb{F}_{2}^{n}$,
we will actually only consider this quantity when $X$ is a subspace of
$\mathbb{F}_{2}^{n}$. In this particular situation, we record the following
simple observation.

######  Lemma 3.3.

Consider subspaces $V^{\prime}\subset V\subset\mathbb{F}_{2}^{n}$. Then

$\mu_{V^{\prime}}^{*}(S)\geqslant\mu_{V}^{*}(S)$

for every $S\subset\mathbb{F}_{2}^{n}$.

###### Proof.

This follows from an averaging argument. For convenience, let us write again
$G:=\mathbb{F}_{2}^{n}$. Pick $g_{0}\in G$ such that

$\mu_{V}^{*}(S)=\mu_{V}(g_{0}+S)=\mu_{V-g_{0}}(S).$

Since $V^{\prime}\subset V$, we can pick $v_{1},\dots,v_{\ell}\in V$ so that

$\bigsqcup_{i=1}^{\ell}v_{i}+V^{\prime}=V.$

Therefore,

$\mu_{V-g_{0}}(S)=\mathbb{E}_{i\in[\ell]}[\mu_{V^{\prime}+v_{i}-g_{0}}(S)].$

It follows that there must be some outcome $i$ where
$\mu_{V^{\prime}+v_{i}-g_{0}}(S)\geqslant\mu_{V-g_{0}}(S)$, so

$\mu_{V^{\prime}}^{*}(S)\geqslant\mu_{V^{\prime}+v_{i}-g_{0}}(S)\geqslant\mu_{V-g_{0}}(S)=\mu_{V}^{*}(S)$

as desired. $\Box$

We can now prove our main iteration lemma.

######  Proposition 3.2.

Consider subsets $A_{1},\dots,A_{r}\subset G:=\mathbb{F}_{2}^{n}$, along with
some subspace $V\leqslant G$. Also fix some constants $\alpha,\gamma\in(0,1)$.

Now suppose there was some $i\in[r]$ such that both of the following
properties held:

  * •

(failure of sparsity):

$\mu_{V}^{*}(A_{i})\geqslant\alpha;$

  * •

(failure of expansion):

$\mu_{V}(D_{i})\leqslant 1-\gamma,$

where

$D_{i}:=\\{v\in
V:\mu_{A_{i}}\circ\mu_{A_{i}}(v)\geqslant\frac{1}{2}\mu(V)^{2}\\}.$

Then there exists $V^{\prime}\leqslant V$ with
$\operatorname{codim}(V^{\prime})-\operatorname{codim}(V)\ll\mathcal{L}(\alpha)^{4}\mathcal{L}(\gamma)^{2}$,
so that

$\mu_{V^{\prime}}^{*}(A_{i})\geqslant(1+1/128)\mu_{V}^{*}(A_{i})$

(meanwhile $\mu_{V^{\prime}}^{*}(A_{j})\geqslant\mu_{V}^{*}(A_{j})$ for all
other $j\in[r]$).

###### Proof.

Pick $g\in G$ such that $\mu_{V}^{*}(A_{i})=\mu_{V}(A_{i}+g)$. Write
$A^{\prime}:=(A_{i}+g)\cap V$. By our first assumption, we have
$\mu_{V}(A^{\prime})\geqslant\alpha$.

Next take

$D^{\prime}:=\\{v\in
V:\mu_{A^{\prime}}\circ\mu_{A^{\prime}}(v)\geqslant\frac{1}{2}\\}.$

Note that since
$\mu_{V}(A^{\prime})=\mu_{V}^{*}(A)\geqslant\mu(V)\mu_{G}^{*}(A)\geqslant\mu(V)\mu(A)$
(using Lemma 3.3 for the second-to-last inequality), whence

$D_{i}=\\{v\in V:1_{A_{i}}\circ
1_{A_{i}}(v)\geqslant\frac{1}{2}\mu(A)^{2}\mu(V)^{2}\\}\supset\\{v\in
V:1_{A^{\prime}}\circ
1_{A^{\prime}}(v)\geqslant\frac{1}{2}\mu(A^{\prime})^{2}\\}=D^{\prime}.$

Thus our second assumption implies that $\mu(D^{\prime})\leqslant 1-\gamma$.

Take $C:=V\setminus D^{\prime}$. We have that $\mu(C)\geqslant\gamma$.
Meanwhile, we have that
$\langle\mu_{A^{\prime}}\circ\mu_{A^{\prime}},\mu_{C}\rangle\leqslant 1/2$,
whence we can apply Lemma 3.2 to find a coset $U=t+V^{\prime}$ with
$V^{\prime}\leqslant V$ and
$\operatorname{codim}(V^{\prime})-\operatorname{codim}(V)\ll\mathcal{L}(\alpha)^{4}\mathcal{L}(\gamma)^{2}$,
so that

$\mu_{U}(A^{\prime})\geqslant(1+1/128)\mu_{V}(A^{\prime})=(1+1/128)\mu_{V}^{*}(A).$

Noting that
$\mu_{V^{\prime}}^{*}(A)\geqslant\mu_{V^{\prime}}((g-t)+A)\geqslant(1+1/128)\mu_{V}^{*}(A)$
completes the claim. $\Box$

Now our main proposition follows from running an increment argument.

###### Proof of Proposition 3.1.

Fix $A_{1},\dots,A_{r}\subset G$ and $\alpha,\gamma$ as in the prompt.

Initialize with $V_{0}:=\mathbb{F}_{2}^{n}$. Then at time $t=0,1,\dots,$ we
take

$i_{t}:=\inf\left\\{i\in[r]:\mu_{V_{t}}^{*}(A_{i})\leqslant\alpha\text{ and
}\mu_{V_{t}}(\\{v\in
V_{t}:\mu_{A_{t}}\circ\mu_{A_{t}}(v)\geqslant\frac{1}{2}\mu(V_{t})^{2}\\})\leqslant
1-\gamma\right\\};$

if $i_{t}=\infty$ (i.e., there are no such indices as above), then we halt at
time $\tau:=t$. Otherwise, we can invoke Proposition 3.2, it to find some
$V^{\prime}\leqslant V_{t}$ where
$\operatorname{codim}(V^{\prime})-\operatorname{codim}(V_{t})\ll\mathcal{L}(\alpha)^{4}\mathcal{L}(\gamma)^{2}$,
so that
$\mu^{*}_{V^{\prime}}(A_{i_{t}})\geqslant(1+1/128)\mu_{V_{t}}^{*}(A_{i_{t}})$.
We define $V_{t+1}:=V^{\prime}$ and continue iterating the above (until we
halt).

Note that this process must halt after $\tau\ll r\mathcal{L}(\alpha)$ steps,
since for each $i\in[r]$, there can be at most $128\mathcal{L}(\alpha)$ times
$t$ where $i_{t}=i$. Indeed, if $\\#(t^{\prime}<t:i_{t^{\prime}}=i)=m>0$, we
get that

$1\geqslant\mu_{V_{t}}(A_{i})\geqslant(1+1/128)^{m}\alpha\geqslant
2^{m/128}\alpha.$

Meanwhile, we have that
$\operatorname{codim}(V_{\tau})=\sum_{t=1}^{\tau}\operatorname{codim}(V_{t})-\operatorname{codim}(V_{t-1})\leqslant\tau
O(\mathcal{L}(\alpha)^{4}\mathcal{L}(\gamma)^{2})$. Thus
$\operatorname{codim}(V_{\tau})\ll
r\mathcal{L}(\alpha)^{5}\mathcal{L}(\gamma)^{2}$. This gives the desired
result since the sparsity-expansion dichotomy holds for $V_{\tau}$. $\Box$

###  3.1 Proof of Theorem 1.3 given Proposition 3.1

Let $\alpha=\gamma:=\frac{1}{10r2^{d}}$, and note that
$L:=\mathcal{L}(\alpha)=\mathcal{L}(\gamma)=O(\log(r)+d)$. Let $C_{0}$ be the
implicit constant from Proposition 3.1, and consider
$n:=2C_{0}r\mathcal{L}(\alpha)^{5}\mathcal{L}(\gamma)^{2}=2C_{0}rL^{7}=O(r(\log(r)+d)^{7})$.

Furthermore, consider $G:=\mathbb{F}_{2}^{n}$ any choice of color classes
$A_{1},\dots,A_{r}\subset G$ where each $A_{i}$ is sum-free (in particular,
this implies $0\not\in A_{i}$ for each $i$). By Proposition 3.1 (with our sets
$A_{1},\dots,A_{r}$ and parameters $\alpha,\gamma$), we can find some subspace
$V\leqslant G$ with $\dim(V)\geqslant n/2$, so that the desired sparsity-
expansion dichotomy holds. Then, for $i\in[r]$, if $\mu_{V}(A_{i})<\alpha$, we
set $S_{i}:=A_{i}$, and otherwise we take

$S_{i}:=\\{v\in V:\mu_{A_{i}}\circ\mu_{A_{i}}(v)<\frac{1}{2}\mu(V)^{2}\\}.$

By the sparsity-expansion dichotomy, we have that
$\mu_{V}(S_{i})\leqslant\frac{1}{10r2^{d}}$ for each $i\in[r]$; and
deterministically we have that $0\not\in S_{i}$ (since $0\not\in A_{i}$ by
assumption, and if $A_{i}$ is non-empty, then
$\mu_{A_{i}}\circ\mu_{A_{i}}(0)=1/\alpha\geqslant
1\geqslant\frac{1}{2}\mu(V)^{2}$).

Thus, writing

$S:=\bigcup_{i=1}^{r}S_{i},$

we have that $0\not\in S$ and $\mu_{V}(S)\leqslant\frac{1}{102^{d}}$ (by union
bound). Finally, recalling that $\dim(V)\geqslant n/2\geqslant d$, we can
invoke Lemma 2.2 to deduce that $S^{c}:=V\setminus S$ contains a subspace
$V^{\prime}\leqslant V$ with $\dim(V^{\prime})\geqslant d$, which is disjoint
from $S$.

For each $i\in[r]$, we have that $S\supset S_{i}$, which implies $V^{\prime}$
is disjoint from $A_{i}$. Indeed, either we have that $S_{i}:=A_{i}$ (which
directly implies disjointness), or $S_{i}\supset V\setminus(A_{i}-A_{i})$
(which implies $V^{\prime}\subset A_{i}-A_{i}$, meaning $V^{\prime}$ should be
disjoint from $A_{i}$ by sum-freeness). So, it follows that $V^{\prime}\subset
G\setminus\bigcup_{i=1}^{r}A_{i}$, which implies the claim.

##  4 Another application

In this section, we would like to note that our methods can be extended
further to provide an even stronger form of Theorem 1.3 (namely, Theorem 4.1),
which gives similar results for arbitrary finite-fields.

Given a prime $p\geqslant 2$, let us say that a set
$S\subset\mathbb{F}_{p}^{n}$ is solution-free, if there exists some choice
$a,b\in\\{1,\dots,p-1\\}$ such that there is no $x,y,z\in S$ satisfying
$a\cdot(x-y)=b\cdot z$. Note that every sum-free set
$A\subset\mathbb{F}_{p}^{n}$ is a solution-free set (by taking $a=b=1$, and
rearranging $(x-y)=z$ as $x=y+z$).

This definition is motivated by “homogeneous partition-regular equations”
(discussed below). Obtaining quantitative bounds for coloring problems related
to these equations is an important topic in additive combinatorics, as such
questions represent generalizations of the celebrated theorem of Schur (which
states that for any finite coloring of $\mathbb{Z}_{>0}$, there must be a
color class which is not sum-free). We will establish nearly sharp bounds in
the finite-field setting for such problems.

In the integer setting, it is known that for any fixed $a,b\in\mathbb{Z}_{+}$,
and any $r\geqslant 1$, there exists some finite $N$ so that for any
$r$-coloring $C:[N]\to[r]$, we can find some monochromatic triple $x,y,z$ such
that $a(x-y)=bz$. Specializing to the case of $a=b=1$, this is the content of
Schur’s Theorem (which alternatively says that $[N]$ cannot be covered by $r$
sum-free sets (assuming $N$ is large enough with respect to $r$)). In [11],
Cwalina and Schoen studied the growth of $N=N_{a,b}(r)$ for any fixed
$a,b\in\mathbb{Z}_{+}$ as $r\to\infty$. They demonstrated that

$\exp(\Omega_{a,b}(r))\leqslant
N_{a,b}(r)\leqslant\exp(O_{a,b}(r^{4}\log(r)^{4})).$

We defer the interested reader to [11] for further motivation on the study of
such quantities; here, we will provide some nearly sharp bounds to a finite-
field analogue of this problem.

######  Theorem 4.1.

For each prime $p$, there exists a constant $C_{p}$ such that the following
holds:

Consider solution-free subsets $A_{1},\dots,A_{r}\subset
G:=\mathbb{F}_{p}^{n}$. Furthermore, suppose that $n>C_{p}r(\log(r)+d)^{7}$
for some $d\geqslant 1$.

Then there exists $V\leqslant G$ with $\dim(V)\geqslant d$ so that $V$ is
disjoint from $\bigcup_{i=1}^{r}A_{i}$.

This in particular tells us that $\mathbb{F}_{p}^{n}\setminus\\{0\\}$ cannot
be covered by $\ll n^{1-c}$ sum-free sets for any absolute constant $c>0$
(recalling that sum-free sets are solution-free). By considering using dyadic
intervals to cover each of the $n$ coordinates, it is not hard to see that
$O(\log(p)n)$ sum-free sets suffice to cover $\mathbb{F}_{p}^{n}$, thus this
is nearly sharp. It is conjectured that $\Omega(\log(p)n)$ sets are also
required, due to connections with conjectures regarding the asymptotic growth
of the $r$-color Ramsey $R(3,\ldots,3)$.

Previously, the best-known additive proof111Due to connections with the
$r$-color Ramsey number of triangles, it is known that you can’t use at most
$o(\log(n)/\log\log(n))$ sum-free sets to cover $\mathbb{F}_{p}^{n}$. But this
proof is purely graph theoretical, and cannot be generalized to give bounds in
the case of solution-free sets, or even to sets which all lack solutions to
the equation $x-y=2z$. could only prove that $n^{1/3}$ sum-free sets are not
sufficient to cover $\mathbb{F}_{2}^{n}\setminus\\{0\\}$ [8, Section 2]. For
more general solution free-sets, the aforementioned upper bound of Cwalina-
Schoen in the integer setting morally says that $n^{1/4-c}$ solution-free sets
should not be enough to cover $\mathbb{F}_{p}^{n}\setminus\\{0\\}$ for any
absolute constant $c>0$ [11, Theorem 1.7].

The starting point (for proving Theorem 4.1) is [5, Proposition 9].

######  Lemma 4.1 (Bloom-Sisask).

Fix a prime $p$. Let $V\cong\mathbb{F}_{p}^{n}$. Consider $A,C\subset V$ with
$\mu(A)=\alpha,\mu(C)=\gamma$. Suppose that
$|\langle\mu_{A}\circ\mu_{A},\mu_{C}\rangle-1|>1/2$.

Then there exists a coset $U=t+V^{\prime}$ where
$\operatorname{codim}(V^{\prime})\ll_{p}\mathcal{L}(\alpha)^{4}\mathcal{L}(\gamma)^{2}$
and $\mu_{U}(A)\geqslant(1+1/128)\alpha$.

Repeating the arguments from the last section, it is not difficult to
establish the following more general result.

######  Proposition 4.2.

Fix a prime $p$.

Consider subsets $A_{1},\dots,A_{r}\subset G:=\mathbb{F}_{p}^{n}$. For each
$\alpha,\gamma\in(0,1)$, there exists some subspace $V\leqslant G$ with
$\operatorname{codim}(V)\ll_{p}r\mathcal{L}(\alpha)^{5}\mathcal{L}(\gamma)^{2}$
such that, for each $i\in[r]$, one of the following holds:

  * •

(Sparsity):

$\mu_{V}(A_{i})<\alpha;$

  * •

(Expansion):

$\mu_{V}(D_{i})>1-\gamma,$

where

$D_{i}:=\\{v\in
V:\mu_{A_{i}}\circ\mu_{A_{i}}(v)\geqslant\frac{1}{2}\mu(V)^{2}\\}.$

We will leave the details of establishing Proposition 4.2 to the interested
reader. We now include the main ideas for how to prove Theorem 4.1 (at a high
level).

The rough idea is that if $A_{i}$ is a solution-free set, with no solutions to
$a\cdot(x-y)=b\cdot z$, then defining $A_{i}^{\prime}:=a\cdot A_{i}$, we have
that $0\not\in A_{i}^{\prime}$, and for any subspace $V\leqslant G$,
$\mu_{V}(A_{i}^{\prime})=\mu_{V}(A_{i})$ and $V\subset
A_{i}^{\prime}-A_{i}^{\prime}$ implies $V\cap A_{i}=\emptyset$. Meanwhile,
similarly to Lemma 2.2, if $S\subset V\cong\mathbb{F}_{p}^{n}$ is a set with
$0\not\in S$ and $\mu_{V}(S)<p^{-d}$ for some $d\leqslant n$, then we have
that there exists a subspace $V^{\prime}\subset V\setminus S$ with
$\dim(V^{\prime})\geqslant d$. One can now hope to argue in the same way as in
Subsection 3.1 (now taking $\alpha=\gamma:=\frac{1}{10rp^{d}}$). We outline
the argument below.

###### Proof sketch of Theorem 4.1.

Consider $r,d\geqslant 1$, and set $\alpha=\gamma:=\frac{1}{10rp^{d}}$. Note
that $\mathcal{L}(\alpha)=O_{p}((\log(r)+d))$.

Assume that $n>C_{p}r\mathcal{L}(\alpha)^{5}\mathcal{L}(\gamma)^{2}$ for some
sufficiently large constant $C_{p}$ (which is allowed to depend on $p$); note
that the lower bound on the right hand side is $O_{p}(r(\log(r)+d)^{7})$.

Now consider any solution-free sets
$A_{1},\dots,A_{r}\subset\mathbb{F}_{p}^{n}$. For each $i$, we can find some
$a,b\in\\{1,\dots,p-1\\}$, so that there is no $x,y,z\in A_{i}$ satisfying
$a\cdot(x-y)=b\cdot z$; set $A_{i}^{\prime}:=a\cdot A_{i}$.

Using Proposition 4.2, we can find $V\leqslant\mathbb{F}_{p}^{n}$ with
$\dim(V)\geqslant n/2\geqslant d$, and a partition $[r]=I_{1}\sqcup I_{2}$, so
that:

  * •

$\mu_{V}(A_{i}^{\prime})\leqslant\alpha$ for $i\in I_{1}$;

  * •

$\mu_{V}(V\setminus(A_{i}^{\prime}-A_{i}^{\prime}))\leqslant\gamma$ for $i\in
I_{2}$.

For $i\in I_{1}$, set $S_{i}:=A_{i}^{\prime}$, and for $i\in I_{2}$, set
$S_{i}:=V\setminus(A_{i}^{\prime}-A_{i}^{\prime})$. As discussed above, since
$A_{i}$ is solution-free, if $V^{\prime}\leqslant V$ is disjoint from $S_{i}$,
then $V^{\prime}$ is disjoint from $A_{i}$.

Now, taking $S:=\bigcup_{i=1}^{r}S_{i}$, we get that
$\mu_{V}(S)\leqslant\sum_{i=1}^{r}\mu_{V}(S_{i})\leqslant\frac{1}{10rp^{d}}<p^{-d}$.
Furthermore, it is easy to show that $0\not\in S$. Thus (using the analog of
Lemma 2.2 which we discussed previously) there exists some
$V^{\prime}\leqslant V$ with $\dim(V^{\prime})\geqslant d$ which is disjoint
from $S$, proving the theorem. $\Box$

##  5 Concluding remarks and open problems

In this paper, we proved that $R_{\mathbb{F}_{2}}(2,d)=O(d^{7})$, and more
generally that

$R_{\mathbb{F}_{2}}^{(r)}(2;d)=O_{r}(d^{7})$

holds for all $r\geqslant 2$. We would like to begin this section by
contrasting our multi-color result with the following result of Alon and Rödl
from [2], generalizing the works of Ajtai-Komloś-Szemerédi [1] and Kim [18]
about the usual off-diagonal Ramsey number $R(3,m)$.

######  Theorem 5.1 (Alon-Rödl).

Let $R^{(r)}(3;m)$ denote the $r$-color Ramsey number $R(3,\ldots,3;m)$. For
every $r\geqslant 2$, we have that

$R^{(r)}(3;m)=\Theta(m^{r}/\operatorname{polylog}m).$

For convenience, $\operatorname{polylog}m$ here stands for an unspecified
polynomial factor in $\log m$. For $r=2$, $R^{(2)}(3;m)=R(3,m)$, in which case
Theorem 5.1 recovers (up to this polylogarithmic factor) the fact that
$R(3,m)=\Theta(m^{2}/\log m)$. For every $r\geqslant 3$, Theorem 5.1 implies
for instance that

$\lim_{m\to\infty}\frac{R^{(r)}(3;m)}{R^{(r-1)}(3;m)}=\infty,$

formerly a conjecture of Erdős and Sós [12] already in the case $r=3$. It
would be tempting to make the analogous conjecture for
$\mathbb{R}_{\mathbb{F}_{2}}^{(r)}(2;d)$, namely that for every $r\geqslant
3$,

$\lim_{d\to\infty}\frac{R_{\mathbb{F}_{2}}^{(r)}(2;d)}{R_{\mathbb{F}_{2}}^{(r-1)}(2;d)}=\infty$
(5.1)

must always hold. However, despite the successful analogies between
$R_{\mathbb{F}_{2}}(2,d)$ and $R(3,m)$ thus far, we suspect (5.1) should not
hold. Instead, we would like to make the following competing conjecture
regarding the growth of $R_{\mathbb{F}_{2}}(2,d)$.

######  Conjecture 1.

$R_{\mathbb{F}_{2}}(2,d)=\Theta(d).$

A standard probabilistic construction can be used to see that222Technically
speaking, the “all-red coloring” of $\mathbb{F}_{2}^{d-1}$ already proves that
$R_{\mathbb{F}_{2}}(2,d)\geqslant d-1$. However, using a random coloring and a
straightforward union bound argument, one can show that
$R_{\mathbb{F}_{2}}(2,d)\geqslant(3/2-o(1))d$ (thus we have
$R_{\mathbb{F}_{2}}(2,d)-d\gg d$). We note that we are not aware of any better
bounds than this basic union bound argument. In fact, we do not even know how
to prove a better bound using (finitely many) additional colors (for example,
it would already be interesting to show that
$R^{(1000)}(2;d)\geqslant(3/2+c-o(1))d$ for some absolute constant $c>0$).
$R_{\mathbb{F}_{2}}(2,d)=\Omega(d)$, so in order to prove Conjecture 1 it
would suffice to show that $R_{\mathbb{F}_{2}}(2,d)=O(d)$. Furthermore, note
that

$R_{\mathbb{F}_{2}}^{(r)}(2;d)\leqslant
R_{\mathbb{F}_{2}}^{(r-1)}(2;R_{\mathbb{F}_{2}}(2,d))$

holds for every $r\geqslant 3$. Therefore, if $R_{\mathbb{F}_{2}}(2,d)=O(d)$,
then $R_{\mathbb{F}_{2}}^{(r)}(2;d)=O_{r}(d)$ follows for every $r\geqslant 3$
as well. Moreover, it is clear that $R_{\mathbb{F}_{2}}^{(r)}(2,d)\geqslant
R_{\mathbb{F}_{2}}^{(r-1)}(2,d)$ holds for every $r\geqslant 3$, thus
Conjecture 1 implies that $R_{\mathbb{F}_{2}}^{(r)}(2;d)=\Theta_{r}(d)$ holds
for every $r\geqslant 2$.

That being said, we still believe that it would be interesting to distinguish
quantitatively between, say, $R_{\mathbb{F}_{2}}(2,d)$ and
$R_{\mathbb{F}_{2}}(2,2,d)$. For example, if (5.1) is too much to ask for, can
one at least show that

$\lim_{d\to\infty}\left(R_{\mathbb{F}_{2}}^{(r)}(2;d)-R_{\mathbb{F}_{2}}^{(r-1)}(2;d)\right)=\infty$

for every $r\geqslant 3$?

In light of the additive combinatorics approach developed in this paper, an
important problem which is directly relevant to the faith of Conjecture 1
seems to be the question of determining whether or not there exists some
absolute constant $C>0$ such that $f(Cd,2^{-d})\geqslant d$ for all
$d\geqslant 1$.

There are also several natural open problems that one may pose about the
general behavior of $R_{\mathbb{F}_{p}}(s,d)$ for other choices of
$p,s\geqslant 2$ (as $d$ goes to $\infty$). We would like to share a few of
our favorite ones.

######  Conjecture 2.

For every $s\geqslant 2$, there exists some $C=C(s)>0$ such that

$R_{\mathbb{F}_{2}}(s,d)=O(d^{C}).$

In other words, we believe that $R_{\mathbb{F}_{2}}(s,d)$ is polynomial in $d$
for every $s\geqslant 2$. We suggest a possible approach, which could
potentially extend the ideas of this paper. Given $n,k\geqslant 1$ and
$\alpha>0$, define $f_{k}(n,\alpha)$ to be the largest $d$, such that given
any $A\subset G:=\mathbb{F}_{2}^{n}$ with $\mu(A)\geqslant\alpha$, we have
that there exist some $V\leqslant G$ with $\dim(V)\geqslant d$, such that for
each $v_{1},\dots,v_{k}\in V$, there exists $a\in A\setminus V$ such that the
parallelepiped

$\\{a+\sum_{i\in I}v_{i}:I\subset[k]\\}$

is contained entirely inside $A$. Note that $f_{1}(n,\alpha)$ is equal to the
function $f(n,\alpha)$ we introduced previously.

Using arguments like before, one can show that if

$f_{s-1}(n,2^{-d})\geqslant R_{\mathbb{F}_{2}}(s-1,d),$

then we have that $R_{\mathbb{F}_{2}}(s,d)\leqslant n$. Indeed, either the
first color class will be “sparse” (density $<2^{-d}$), which implies a
dimension $d$ subspace in the complement, or one should be able to pass to
some subspace $V$ where every $(s-1)$-dimensional $V^{\prime}$ subspace has
some disjoint ‘coset’/parallelepiped which can extend $V^{\prime}$ to a
$s$-subspace (thus $V$ should be colored to not have a red $(s-1)$-subspace
nor blue $d$-subspace, allowing us to iterate). Thus, if for each $k\geqslant
1$, one could show that $f_{k}(Cd^{C},2^{-d})\geqslant d$ for some constant
$C=C_{k}$, then $R_{\mathbb{F}_{2}}(s,d)\ll d^{O_{s}(1)}$ for every
$s\geqslant 2$. Furthermore, if $f_{k}(C_{k}d,2^{-d})\geqslant d$ holds for
some constant $C_{k}$, the sketch above would readily imply that
$R_{\mathbb{F}_{2}}(s,d)=O_{s}(d)$ for every $s\geqslant 2$.

Last but not least, it would also be interesting to get reasonable bounds for
the off-diagonal numbers in different finite fields. For example, it is
already not clear how to extend the arguments of this paper to show that
$R_{\mathbb{F}_{3}}(2,d)$ is polynomial in $d$. This presents new challenges,
as now there is a difference between the set of $1$-dimensional subspaces of
$\mathbb{F}_{3}^{n}$, and the set of non-zero points in this space (indeed,
one can define a 2-coloring $C:\mathbb{F}_{3}^{n}\setminus\\{0\\}\to\\{1,2\\}$
so that $C(v)\neq C(2\cdot v)$ for all non-zero $v$, in which case every non-
trivial subspace of $\mathbb{F}_{3}^{n}$ receives multiple colors). We
currently do not have ideas for any additive combinatorial result that would
readily give polynomial bounds in this setting.

## References

  * [1] M. Ajtai, J. Komloś and E. Szemerédi, A note on Ramsey numbers, Journal of Combinatorial Theory, Series A 29 (1980), 354–360.
  * [2] N. Alon and V. Rödl, Sharp bounds for some multicolor Ramsey numbers, Combinatorica 25 (2005), 125–141.
  * [3] N. Alon, J. H. Spencer, The Probabilistic Method, John Wiley and Sons, 1992.
  * [4] T. Bloom, O. Sisask, The Kelley–Meka bounds for sets free of three-term arithmetic progressions, preprint. [arXiv:2302.07211]
  * [5] T. Bloom, O. Sisask, An improvement to the Kelley-Meka bounds on three-term arithmetic progressions, preprint.
  * [6] M. Bonamy, F. Kardos, T. Kelly, P. Nelson, L. Postle, The structure of binary matroids with no induced claw or Fano plane restriction, Advances in Combinatorics, 2019:1, 17pp.
  * [7] R. C. Bose, R. C. Burton, A characterization of flat spaces in a finite geometry and the uniqueness of the Hamming and the MacDonald codes, in J. Comb. Theory 1 (1966), p. 96–104.
  * [8] J. Chapman, S. Prendiville, On the Ramsey number of the Brauer configuration, Bull. London Math. Soc. 52 (2020), 316–334.
  * [9] M. Chudnovsky, P. Seymour, Claw-free graphs VI. Colouring, Journal of Combinatorial Theory, Series B 100 (2010), 560–572.
  * [10] E. Croot, I. Laba, O. Sisask, Arithmetic progressions in sumsets and $L^{p}$-almost-periodicity, Combin. Probab. Comput. 22 (2013), no. 3, 351–365.
  * [11] K. Cwalina, T. Schoen, Tight bounds on additive Ramsey-type numbers, J. London Math. Soc., 92 (2017), 601–620.
  * [12] P. Erdős, V. T. Sós: Problems and results on Ramsey-Turán type theorems, Proc. of the West Coast Conference on Combinatorics, Graph Theory and Computing, Humboldt State University, Arcata, CA, 1979, Congressus Numer. Vol. XXVI, Utilitas Mathematics, Winnipeg, Man., 1980, pp. 17–23.
  * [13] B. Frederickson, L. Yepremyan, Vector space Ramsey numbers and weakly Sidorenko affine configurations, preprint. [arXiv:2308.13489]
  * [14] R. L. Graham, K. Leeb, B. L. Rothschild, Ramsey’s theorem for a class of categories, Advances in Math. 8 (1972), 417–433.
  * [15] B. J. Green. Finite field models in additive combinatorics. In Surveys in combinatorics 2005, volume 327 of London Math. Soc. Lecture Note Ser., 1–27. Cambridge Univ. Press, Cambridge, 2005.
  * [16] Z. Hunter, An exposition about almost-periods and ideas of Kelley-Meka, Master’s Thesis (2023).
  * [17] Z. Kelley and R. Meka, Strong bounds for 3-progressions, preprint. [arXiv:2302.05537]
  * [18] J. H. Kim, The Ramsey number $R(3,t)$ has order of magnitude $t^{2}/\log t$, Random Structures and Algorithms 7 (1995), 173–207.
  * [19] P. Nelson, K. Nomoto, The structure of claw-free binary matroids, Journal of Combinatorial Theory, Series B, 150 (2021), 76–118.
  * [20] P. Nelson, Problem 17 in the 2022 Barbados Workshop List of Open Problems.
  * [21] J. G. Oxley, Matroid Theory, Oxford University Press, New York (2011).
  * [22] T. Sanders, Green’s sumset problem at density one half, Acta Arithmetica 146 (2011), 91–101.
  * [23] T. Sanders, Bootstrapping partition regularity of linear systems, Proceedings of the Edinburgh Mathematical Society, Volume 63, Issue 3, August 2020, 630–653.
  * [24] J. H. Spencer, Ramsey’s theorem for spaces, Trans. Amer. Math. Soc. 249 (1979), no. 2, 363–371.