11institutetext:  11email<EMAIL_ADDRESS>

# FPM: A Collection of Large-scale Foundation Pre-trained Language Models

Dezhou Shen

###### Abstract

Large-scale Transformer models have significantly promoted the recent
development of natural language processing applications. However, little
effort has been made to unify the effective models. In this paper, driven by
providing a new set of baseline models in the future, we adopt various novel
transformer architectures and launch a model set with the help of recent
mainstream technologies. We focus the discussions on optimizing the depth of
the networks based on the existing powerful encode-decoder structures. We show
that by properly avoiding training defects such as non-convergence and
degradation, scaling up off-the-shelf transformer architectures consistently
delivers better performance. To stimulate future research on large-scale
language model pretraining, we present extensive results and detailed
discussions on network performance improvements with respect to the network
depth and confirm the existence of the optimal number of layers under specific
tasks. To the best of our knowledge, we provide the largest Chinese generative
model and the largest Chinese encoding model. The BERT language models we
trained on English datasets deliver a 14.45% higher F1 score than the Turing-
NLR.

###### Keywords:

Natural Language Processing Pre-trained Language Model Transformers.

##  1 Introduction

Thanks to the increasing availability of hardware and size of datasets,
natural language processing has developed rapidly in recent years. The massive
resources of computation and data make it possible to train large-scale
language models through self-supervised pre-training [10]. As the model size
increases, the memory consumption can exceed the limit of the modern hardware.
Fortunately, modern developments on distributed training have enabled models
with hundreds of millions or even tens of billions of parameters to be trained
on a large number of GPUs in parallel. And now there are many techniques, such
as layer normalization [1] and residual connection [5] in Transformer layers
[17], to eliminate model degradation when scaling up the training models.

However, little effort has been made to unify the effective models. In this
paper, driven by providing a new set of baseline models in the future, we
adopt various novel transformer architectures and launch a model set with the
help of recent mainstream technologies.

In summary, the contributions of this article are as follows:

  * •

We train a language model with 10.3 billion parameters, which to the best of
our knowledge, is the largest Chinese generative model.

  * •

We train a BERT language model with 495 million parameters, which to the best
of our knowledge, is the largest Chinese encoding model.

  * •

We train a GPT-2 language model with 6.4 billion parameters, which to the best
of our knowledge, is the largest English generative model.

  * •

We have trained a list of BERT language models, which to the best of our
knowledge, exceeds the Turing-NLR’s F1 score by 14.45% on English datasets.

  * •

We observe that the best result of Quora-Question-Pairs(QQP) from GLUE does
not come along with the largest 90-layer-BERT-E-E model, and the 70-layer-
BERT-E-L model achieves the state-of-the-art result with a 0.5% accuracy
improvement compared to the 90-layer-BERT-E-E model.

##  2 Related Work

###  2.1 Terminology

Pre-trained language models are classified into three categories:
autoregressive language models (such as GPT), masked language models (such as
BERT), and encoder-decoder models (such as BART, T5).

This paper uses three tokens, Chinese Pre-trained language Model (CPM) [22],
English Pre-trained language Model (EPM) [22], and Generative Pre-Training
(GPT) [11], to represent autoregressive language models. We use BERT [4] to
represent mask language models. Moreover, we use three tokens, Cost-efficient
Pre-trained language Models (CPM-2) [21], cost-efficient English Pre-trained
Language Models (EPM-2) [21] and Transformer [17], to represent encoder-
decoder models.

Autoregressive language models predict the next word $x$, given all the
previous words $x_{1}$, $x_{2}$, …, and $x_{i-1}$. The training goal is to
maximize the log likelihood $\sum_{i}m_{i}\log\left(P\left(x_{i}\mid
x_{1},\ldots,x_{i-1},x_{i+1},\ldots,x_{n}\right);\theta_{T}\right)$, where
$\theta$ is the model parameter. Typical autoregressive language models
include GPT, GPT-2 [12] and GPT-3 [2].

Mask language models use the special token [MASK] to randomly select the word
to be masked, or replace it with a random token. This architecture forces the
model to collect bidirectional information when making predictions. Popular
representations of MLM include BERT [4] and RoBERTa [8]. Specifically, MLMs
such as BERT use Transformer encoder architecture. Like the autoregressive
model, MLM stacks multiple Transformer encoder layers to learn increasing
complex and meaningful representations, but when learning the representation
of a specific token, it uses masked self-attention to focus on all others in
the sequence token.

Encoder-decoder models use more flexible “text input, text output” pattern,
which learns to generate tokens $y_{1}$, …, $y_{n}$ with the given input
sequence $x_{1}$, …, $x_{m}$. Representative models include BART [6] and T5
[13].

###  2.2 Pre-trained Models Review

Autoregressive models include 2.6-billion-parameter CPM [22], 2.7-billion-
parameter GPT-Neo, 6-billion-parameter GPT-J and 175-billion-parameter GPT-3
[2].

Mask language models include 330-million-parameter Roberta model, 27-billion-
parameter PLUG [7] model, 110-billion-parameter Pangu [20] model, and
1.6-billion-parameter CTRL model.

Encoder-decoder models include 11-billion-parameter CPM-2 [21] model.

The Table-1 shows the popular models performance on GLUE-QQP test set. In the
Section 4.3, we will compare the performance of ours with existing popular
models.

Table 1: Models performance on GLUE-QQP test set. model | QQP-acc. | QQP-f1
---|---|---
BiLSTM+Attn, ELMo [9] | 86.5% | 66.1%
BERT-BASE [4] | - | 71.2%
BERT-LARGE [4] | - | 72.1%
GPT [11] | - | 70.3%
ERINE2.0-BASE [16] | 89.8% | 73.2%
ERINE2.0-LARGE [16] | 90.1% | 73.8%
XLNet [19] | 90.4% | -
ELECTRA [3] | 90.8% | -
ERINE [15] | 90.9% | 75.2%
Turing NLR v5 [18] | 91.1% | 76.4%

##  3 Architecture

Based on the GPT, BERT, Transformer network structure, we extend the GPT,
BERT, and Transformer network structure to different numbers of the network
layers. We study the performance differences among the models by only changing
the number of layers.

###  3.1 GPT

In experiment of the original GPT article, Radford et al. use multi-layer
transformer decoders in the language model, which is a variant of Transformer.
It applies a multi-head self-attention operation to the input tokens, and a
position feed-forward layer to generate the output distribution on target
tokens.

We study the performance impact of the model depth by testing the CPM model
with 36, 64, 128 layers and the EPM model with 36, 50, 64 and 80 layers. All
other hyper-parameters are identical with the original models. We expanded
network layers number from 32 layers to 36, 64, and 128 for the CPM model, and
we have expanded layers from 32 to 36, 50, 64, and 80 for the EPM model.

###  3.2 BERT

BERT is a pre-trained Transformer network that sets up the latest state-of-
the-art results for various natural language processing tasks, including
question answering, sentence classification, and sentence pair regression.

The BERT-Large model mentioned in the paper by Devlin et al. consists of 24
self-attention layers. In this study, we extend the original network from 24
layers to 50, 60, 70, 80, and 90 layers, with all other hyper-parameters
unchanged. The performance impact of the model depth is also discussed in
Table-3.

###  3.3 Transformer

CPM-2 is a standard Transformer model that combines a bidirectional encoder
and a directional decoder. In order to reduce memory consumption and
accelerate pre-training, Zhang et al. use mixed-precision training, gradient
checkpointing, and zero stage optimization [14].

Most powerful neural sequence transduction models have an encoder-decoder
structure. Transformer [17] follows this overall architecture, and uses
stacked self-attention and point-by-point fully connected encoder and decoder
layers.

We reduce the original CPM-2 model from 48 layers of the Transformer unit to
12 and 24 layers. All other hyper-parameters in our model are consistent with
the CPM-2 model in the original paper. Moreover, we train the 12-layer EPM-2
model on English datasets.

##  4 Experiments

###  4.1 Setup

In this work, we focus on three models: GPT-2, BERT, CPM-2, a language model
based on a left-to-right generative transformer, a bidirectional transformer
model based on masking, an encoder-decoder language model, respectively.

####  4.1.1 Training Datasets

A dataset should be as large as possible with high quality first, the
classification should be as even as possible, and the content of the data
should be as clean as possible. This work only focuses on model training, and
uses existing large-scale datasets, the diversified English Pile dataset and
the Chinese Wudao dataset.

##### GPT-English

word segmentation uses GPT-2 English vocabulary, containing 30,000 symbols.
OpenAI team used 40GB of text and 8 million documents collected by WebText
corpus. WebText is a web page curated and filtered by OpenAI humans. All
outbound links with a rating of at least 3 karma are crawled from Reddit. The
generated dataset WebText contains a text subset of 45 million links. In the
cleanup phase, links created after December 2017 were removed, and after
deduplication and some heuristic-based cleanup, slightly more than 8 million
documents were left, a total of 40GB of text, and all Wikipedia documents were
deleted.

##### GPT-Chinese

word segmentation uses CPM Chinese vocabulary, containing 30,000 symbols.
Zhang et al. use 100G multi-category texts, including encyclopedias, news,
novels, and questions-answers. CPM Chinese vocabulary uses the unigram
language model to build a new sub-word vocabulary based on a sub-word corpus.
Since the length of input sequence is usually greater than the length of a
single document, different documents are connected by adding the “end-of-
document” symbol after each document. To make full use of input length, A new
sub-word vocabulary is constructed in the vocabulary construction process,
including commonly used words and characters. Considering that original BERT
word segmentation will introduce an additional splitter between words, Zhang
et al. set up a special token as a splitter to make the sub-word process
reversible.

##### Transformer-Chinese

word segmentation uses CPM-2 Chinese vocabulary. It contains 26,240 symbols
and is trained by Zhang et al. using 2.3TB of cleaned Chinese data. CPM-2’s
vocabulary is modified based on Chinese byte-pair encoding (BPE). Original BPE
inserts many redundant space marks “_” in word segmentation sequence. Zhang et
al. replace sentence segmentation device with a combination of word
segmentation device and the stammering word segmentation, and deletes it
Inserted spaces. Since it does not matter whether symbols in vocabulary appear
at the beginning of the word, tags like “happy” (happy) and “_happy” (_happy)
are merged into a single token “happy” to simplify the vocabulary.

##### Transformer-English

word segmentation, using CPM-2 English vocabulary, contains 29,752 symbols,
which is trained by Zhang et al. using 300GB of cleaned English data. CPM-2’s
vocabulary is modified based on English BPE. Original BPE inserts many
redundant space tokens “_” in word segmentation sequence. Zhang et al.
replaced the sentence tokenizer with word tokenizer combined with nltk word
segmentation, and deleted inserted spaces. English data comes from multiple
fields, including encyclopedias, novels, Q&A, scientific literature, e-books,
news, and reviews.

We use BERT’s English vocabulary for BERT-English word segmentation, which
contains 30,000 symbols. It was trained by Devil et al. using WordPiece
embedding on BooksCorpus (800M words) and English Wikipedia (2500M words).

For BERT-Chinese word segmentation, we use BERT’s Chinese vocabulary, which
contains 21,128 symbols and is trained by Cui et al. using 13.6 million lines
of Wikidata in Chinese. In the process of generating BERT vocabulary, Cui et
al. downloaded the latest Wikipediadump and used WikiExtractor.py to
preprocess it according to the recommendations of Devlin et al., resulting in
1,307 extracted files, and used language technology platform for Chinese word
segmentation.

We use an 800GB corpus from Pile. Due to the limitation of computing
resources, not all partitions was selected in the process. We use only four
blocks of 02, 03, 04, 17 about 213G data. Two types of the corpus,
StackExchange and Github, which contain many impurities, are included, and the
entire dataset is about 200G.

We use 3TB Chinese corpus collected by Yuan et al. In the process of using
Wudao corpus, due to the limitation of computing resources, we use 200G
corpus. Wudao dataset uses 3 billion web pages as an original data source to
extract text content from web pages with high text density. Evaluate the
quality of each data source before extracting the text, and ignore web pages
with text density below 70%.

The Chinese dialogue data from STC-680M corpus dataset, contains approximately
4.4 million conversations from Weibo. To build this million-scale dataset,
they first grab hundreds of millions of response pairs and then filter out
potential responses by deleting trivial answers such as “wow”, Advertisements,
and delete the content after the first 30 responses to keep the theme
consistent with cleaning up original data.

####  4.1.2 Training Optimization and Hyperparameters

To effectively train the model, in some experiments, mixed-precision training
and dynamic loss scaling are removed to use a tensor core of A100. However, in
some experiments, training fails to converge due to accuracy, and we remove
the mixed-precision training method. First initialize weights with a simple
normal distribution. Then scale the weights immediately before the residual
layer, where N is the number of transformer layers composed of self-attention
and Multilayer Perceptron (MLP) blocks. For optimizer, use Adam with a weight
decay of 0.01. In addition, a 1.0 global gradient norm crop is used to improve
the stability of training large models. In all cases, use a dropout of 0.1.
Finally, to better manage the memory footprint, activation checkpoints are
used after each transformer layer.

For GPT-2 model, we make all training experiments using 1024 symbol sequences,
and batch size is 512, and 300k iterations are performed. We preheat 1.5e-4
learning rate for 3k iterations, and then a single-loop cosine decay is
performed in the remaining iterations. Stop attenuation at the minimum
learning rate of 1e-5.

For BERT, we follow the training process described in original paper. Using
original BERT dictionary, vocabulary size is 30,522. In addition, follow
suggested sentence order prediction to reposition the next sentence prediction
head and use the whole word n-gram mask. For all cases, set batch size to
1024, and use a learning rate of 1.0e-4, warm up in 10,000 iterations and
decay linearly in remaining iterations. Other training parameters remain
unchanged.

Table 2: Corpus language, models parameters and layers for FPM models. model | corpus-size | language | $n_{parameters}$ | $n_{layers}$ | $d_{layer}$ | $n_{heads}$ | $d_{head}$
---|---|---|---|---|---|---|---
BERT-C | 200G | CN | 330M | 24 | 1024 | 16 | 64
BERT-E-S | 200G | EN | 687.5M | 50 | 1024 | 16 | 64
BERT-E-M | 200G | EN | 825M | 60 | 1024 | 16 | 64
BERT-E-L | 200G | EN | 962.5M | 70 | 1024 | 16 | 64
BERT-E-X | 200G | EN | 1.1B | 80 | 1024 | 16 | 64
BERT-E-E | 200G | EN | 1.24B | 90 | 1024 | 16 | 64
BERT-X-CN-S | 200G | CN | 495M | 36 | 1024 | 16 | 64
BERT-X-EN-S | 200G | EN | 495M | 36 | 1024 | 16 | 64
BERT-X-EN-M | 200G | EN | 687.5M | 48 | 1024 | 16 | 64
CPM-X-S | 200G | CN | 2.9B | 36 | 2560 | 32 | 80
CPM-X-M | 200G | CN | 5.1B | 64 | 2560 | 32 | 80
CPM-X-L | 200G | CN | 10.3B | 128 | 2560 | 32 | 80
CPM-X-EVA | 684M | CN | 2.9B | 36 | 2560 | 32 | 80
EPM-X-S | 200G | EN | 2.9B | 36 | 2560 | 32 | 80
EPM-X-M | 200G | EN | 4B | 50 | 2560 | 32 | 80
EPM-X-L | 200G | EN | 5.1B | 64 | 2560 | 32 | 80
EPM-X-X | 200G | EN | 6.4B | 80 | 2560 | 32 | 80
CPM-2-X-S | 200G | CN | 2.9B | 12 | 4096 | 64 | 64
CPM-2-X-M | 200G | CN | 5.6B | 24 | 4096 | 64 | 64
EPM-2-X-S | 200G | EN | 2.9B | 12 | 4096 | 64 | 64

###  4.2 Model Details

The infrastructure is optimized for multi-node deep learning applications. All
experiments use up to 2 DGX servers (a total of 16 A100 SXM3 40GB GPUs).
Through NVSwitch, we achieved a bandwidth of 300GB/sec between GPUs in servers
and achieved a bandwidth of 10GB/sec between servers that use 1 InfiniBand
adapter per server.

We describe the most significant models as follows:

  * •

Based on GPT-2, we trained a 10.3-billion-parameter model on Chinese datasets
and we trained a 2.9-billion-parameter model on a dialogue corpus. We trained
a BERT model with 495 million parameters on Chinese datasets. Moreover, we
trained a Transformer model with 5.6 billion parameters on Chinese datasets.

  * •

We apply the corresponding training work for English. Using the GPT-2 model,
we trained a model with 6.4 billion parameters on English datasets. We trained
a BERT model with 1.24 billion parameters on English datasets and we trained a
language model with a 688 million parameter on one GPU. We trained a
Transformer model with 2.9 billion parameters on English datasets.

####  4.2.1 EPM-X

Based on GPT-2 model, we have built an encoder-decoder language model EPM-2-X,
using GPT-English tokenizer, and trained a language model with 2.9 billion
parameters. It has a 12-layer network structure, 6 encoding layers, and 6
decoding layers.

####  4.2.2 EPM-2-X

Based on Transformer model, we have built an encoder-decoder language model
EPM-2-X, using Transformer-English tokenizer, and trained a language model
with 2.9 billion parameters. It has a 12-layer network structure, 6 encoding
layers, and 6 decoding layers.

####  4.2.3 BERT-E

Based on BERT model, we built encoding language model BERT-E. Using BERT-
English word tokenizer, we trained five models with different layers. The
largest model is a language model with 1.24 billion parameters. It has 90
layers of Transformer encoding layers. The network is cascaded, named BERT-
E-E. The second E here means Extreme.

####  4.2.4 BERT-X-EN

Based on BERT model, we have built encoding language model BERT-X-EN. Using
BERT-English word segmentation, we trained two models with different layers.
The largest model is 690 million parameters, includes 48 layers of Transformer
encoding layer stack, named BERT-X-EN-M.

####  4.2.5 CPM-X

Based on GPT-2 model, we have built a generative language model CPM-X, using
GPT-Chinese word segmentation, and trained 3 models with different sizes. The
largest model is a 10.3 billion parameter language model, which stacks 128
layers Transformer decoding layer, named CPM-X-L. Based on GPT-2 model, we
have built a generative language model CPM-X-EVA, using GPT-Chinese word
segmentation, using STC dialogue data, a language model of 2.9 billion
parameters, which stacked 36 layers of Transformer decoding layer, named CPM-
X-EVA.

####  4.2.6 CPM-2-X

Based on Transformer model, we built Transformer language model CPM-2-X. We
trained 2 models, the largest of which uses Transformer-Chinese word
segmentation, trained a 5.6 billion parameter language model. It has a
24-layer network structure, 12 encoding layers and 12 decoding layers, named
CPM-2-X-M.

####  4.2.7 BERT-C

Based on BERT model, we built encoding language model BERT-C. Using a BERT-
Chinese word tokenizer, we trained a language model with 330 million
parameters. It has a 24-layer Transformer encoding layer network cascaded,
named BERT-C.

####  4.2.8 BERT-X-CN

Based on BERT model, we built encoding language model BERT-X-CN. Using a BERT-
Chinese word tokenizer, we trained a language model with 495 million
parameters, including 36 layers of Transformer encoding layers, named BERT-X-
CN-S.

###  4.3 Evaluation

In evaluation stage, we evaluate five BERT-E models on the QQP classification
task from GLUE and evaluate BERT-C model on the TNEWS classification task from
CLUE.

Table 3: Evaluation results on QQP dev set. model | precision | recall | f1 | acc.
---|---|---|---|---
BERT-E-S | 89.84% | 90.42% | 90.11% | 90.73%
BERT-E-M | 89.84% | 90.43% | 90.12% | 90.73%
BERT-E-L |  90.55% |  91.19% |  90.85% |  91.42%
BERT-E-X | 89.99% | 90.39% | 90.18% | 90.82%
BERT-E-E | 90.00% | 90.68% | 90.31% | 90.91%

####  4.3.1 GLUE-QQP

We use an Nvidia 3090 GPU to finetune five BERT-E models on QQP dataset. The
QQP task has 363k, 40k and 390k records in the training, dev and test set.
From Table-3, BERT-E-L model has 70 layers, 1024 hidden dimensions, 16
attention heads, each head contains 64 hidden layers, and 962.5 million
parameters. In QQP classification task evaluated by GLUE, after 45 hours of
fine-tuning 270k steps on 109M corpus, the accuracy of 91.42% exceeded an
accuracy of BERT-Large of 72.1%, an increase of 19.32%. From the precision and
recall evaluation, compared with Turing-NLR’s F1, the first place in GLUE
evaluation of 76.4%, our BERT-E-L model F1 score gained an increase of 14.45%.

####  4.3.2 CLUE-TNEWS

We use an Nvidia 3090 GPU to finetune BERT-C model on TNEWS dataset. In TNEWS
classification task evaluated by CLUE, after fine-tuning the 9.7M corpus for 8
hours 70,000 steps, the accuracy of 65.86% surpassed 59.46% of ALBERT-xxlarge,
an increase of 6.4%.

Table 4: Cost for FPM models. model | time | step | gpus | flops(Eflops)
---|---|---|---|---
BERT-C | 81h | 750K | 8 | 727
BERT-E-S | 34h | 500K | 8 | 305
BERT-E-M | 38h51m | 500K | 8 | 349
BERT-E-L | 45h38m | 500K | 8 | 410
BERT-E-X | 54h24m | 500K | 8 | 488
BERT-E-E | 63h | 500K | 8 | 566
BERT-X-CN-S | 96h | 880K | 1 | 107
BERT-X-EN-S | 315h | 2.8M | 1 | 353
BERT-X-EN-M | 315h | 2.8M | 1 | 353
CPM-X-S | 3h | 10K | 8 | 27
CPM-X-M | 12h | 60K | 8 | 108
CPM-X-L | 24h | 100K | 8 | 216
CPM-X-EVA | 25h | 160K | 2 | 54
EPM-X-S | 20h | 320K | 4 | 92
EPM-X-M | 24h | 320K | 4 | 110
EPM-X-L | 27h | 320K | 4 | 121
EPM-X-X | 30h | 320K | 4 | 135
CPM-2-X-S | 60h | 200K | 2 | 135
CPM-2-X-M | 138h | 80K | 8 | 1240
EPM-2-X-S | 110h | 200K | 2 | 247

##  5 Discussion

We will discuss language, scale, network configuration, and cost for our
training models. Furthermore, we will discuss the optimal layer number for the
GLUE-QQP task.

###  5.1 Language, Scale and Architecture

From Table-2, this work has trained many Chinese and English corpora and
conducted detailed training.

The models with the least number of layers are CPM-2-X and EPM-2-X, with only
12 layers. Model with the most significant number of layers is CPM-X, with 128
layers trained. From perspective of the difficulty of training, GPT structure
is easier to cascade the number of layers. While Transformer structure is not
easy to increase the number of layers, it is easier to reach the upper limit
of hardware memory. From a perspective of model parameters, model with the
least amount of parameters is BERT-C, with only 330 million, and the most
significant parameter is CPM-X-L, with parameters reaching 10.3 billion.

For BERT, GPT, and Transformer, our network structure parameters used in this
work are fixed, and we use parameters in the original paper without
significant modifications.

###  5.2 Cost

We observe that in terms of time consumption, the shortest training time is
CPM-X-S, and the longest time is CPM-X-EN from Table-4. The least training
step number is CPM-X-S, only 100,000 steps. Moreover, the largest is CPM-X-EN
with 2.8 million steps. From the perspective of computing power, the least
computing resource is CPM-X-S, which uses 27 Eflops, and the most computing
power is CPM-2-X-M, which uses 1,240 EFlops.

###  5.3 Optimal Layers

From Table-3, we observe that the best result does not come with the largest
90-layer-BERT-E-E model, the 70-layer-BERT-E-L model achieved the state-of-
the-art result with about 0.5% gain to the 90-layer-BERT-E-E model. We can
conclude that for the GLUE-QQP task, the optimal layer number for BERT models
is 70. We conclude the result from the comparison with the current GPU
hardware limits. In the future, the optimal layer number for the GLUE-QQP task
might change with the help of advanced GPU servers.

##  6 Conclusion

We focus the discussions on optimizing the depth of the networks based on the
existing powerful encode-decoder structures. We observe that the best result
of QQP from GLUE does not come with the largest 90-layer-BERT-E-E model, the
70-layer-BERT-E-L model achieved the state-of-the-art result with about 0.5%
gain to the 90-layer-BERT-E-E model.

##  7 Future Work

With the development of hardware and software, we will try more efficient
model tricks for the deeper network layers and train more improved Chinese and
English models based on BERT and GPT in future. In addition, we will explore
the optimal structure in models for different numbers of model layers in
accuracy.

## References

  * [1] Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton.  Layer normalization.  arXiv preprint arXiv:1607.06450, 2016.
  * [2] Tom B. Brown, Benjamin Mann, Nick Ryder, et al.  Language models are few-shot learners.  In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
  * [3] Kevin Clark, Minh-Thang Luong, Quoc V Le, and Christopher D Manning.  Electra: Pre-training text encoders as discriminators rather than generators.  arXiv preprint arXiv:2003.10555, 2020.
  * [4] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pages 4171–4186, Minneapolis, Minnesota, 2019. Association for Computational Linguistics.
  * [5] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Identity mappings in deep residual networks.  In European conference on computer vision, pages 630–645. Springer, 2016.
  * [6] Mike Lewis, Yinhan Liu, Naman Goyal, et al.  BART: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension.  In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 7871–7880, Online, 2020. Association for Computational Linguistics.
  * [7] Junyang Lin, Rui Men, An Yang, et al.  M6: A chinese multimodal pretrainer.  ArXiv preprint, abs/2103.00823, 2021.
  * [8] Yinhan Liu, Myle Ott, Naman Goyal, et al.  Roberta: A robustly optimized bert pretraining approach.  ArXiv preprint, abs/1907.11692, 2019.
  * [9] Matthew E. Peters, Mark Neumann, Mohit Iyyer, et al.  Deep contextualized word representations.  In Proc. of NAACL, 2018.
  * [10] Xipeng Qiu, Tianxiang Sun, Yige Xu, et al.  Pre-trained models for natural language processing: A survey.  Science China Technological Sciences, pages 1–26, 2020.
  * [11] Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever.  Improving language understanding by generative pre-training.  OpenAI blog, 2018.
  * [12] Alec Radford, Jeffrey Wu, Rewon Child, et al.  Language models are unsupervised multitask learners.  Technical report, 2020.
  * [13] Colin Raffel, Noam Shazeer, Adam Roberts, et al.  Exploring the limits of transfer learning with a unified text-to-text transformer.  Journal of Machine Learning Research, 21:1–67, 2020.
  * [14] Samyam Rajbhandari, Jeff Rasley, Olatunji Ruwase, and Yuxiong He.  Zero: Memory optimizations toward training trillion parameter models.  In SC20: International Conference for High Performance Computing, Networking, Storage and Analysis, pages 1–16. IEEE, 2020.
  * [15] Yu Sun, Shuohuan Wang, Yukun Li, et al.  Ernie: Enhanced representation through knowledge integration.  arXiv preprint arXiv:1904.09223, 2019.
  * [16] Yu Sun, Shuohuan Wang, Yukun Li, et al.  Ernie 2.0: A continual pre-training framework for language understanding.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 8968–8975, 2020.
  * [17] Ashish Vaswani, Noam Shazeer, Niki Parmar, et al.  Attention is all you need.  In Advances in neural information processing systems, pages 5998–6008, 2017.
  * [18] Alex Wang, Amanpreet Singh, Julian Michael, et al.  Glue leaderboard, 2021.  https://gluebenchmark.com/leaderboard (visited: 2021-11-15).
  * [19] Zhilin Yang, Zihang Dai, Yiming Yang, Jaime Carbonell, Russ R Salakhutdinov, and Quoc V Le.  Xlnet: Generalized autoregressive pretraining for language understanding.  Advances in neural information processing systems, 32, 2019.
  * [20] Wei Zeng, Xiaozhe Ren, Teng Su, et al.  Pangu-$alpha$: Large-scale autoregressive pretrained chinese language models with auto-parallel computation.  ArXiv preprint, abs/2104.12369, 2021.
  * [21] Zhengyan Zhang, Yuxian Gu, Xu Han, et al.  Cpm-2: Large-scale cost-effective pre-trained language models.  ArXiv preprint, abs/2106.10715, 2021.
  * [22] Zhengyan Zhang, Xu Han, Hao Zhou, et al.  Cpm: A large-scale generative chinese pre-trained language model.  AI Open, 2:93–99, 2021.


# Coloring hypergraphs that are the union of nearly disjoint cliques

Dhruv Mubayi Department of Mathematics, Statistics, and Computer Science,
University of Illinois, Chicago, IL, 60607 USA. email<EMAIL_ADDRESS>Research partially supported by NSF awards DMS-1763317, DMS-1952767,
DMS-2153576, a Humboldt Research Award and a Simons Fellowship. Jacques
Verstraete Department of Mathematics, University of California, San Diego, CA,
92093-0112 USA. email<EMAIL_ADDRESS>Research supported by NSF award
DMS-1952786.

###### Abstract

We consider the maximum chromatic number of hypergraphs consisting of cliques
that have pairwise small intersections. Designs of the appropriate parameters
produce optimal constructions, but these are known to exist only when the
number of cliques is exponential in the clique size. We construct near designs
where the number of cliques is polynomial in the clique size, and show that
they have large chromatic number.

The case when the cliques have pairwise intersections of size at most one
seems particularly challenging. Here we give lower bounds by analyzing a
random greedy hypergraph process. We also consider the related question of
determining the maximum number of caps in a finite projective/affine plane and
obtain nontrivial upper and lower bounds.

##  1 Introduction

For $1\leq\ell<k\leq q$, an $\ell$-$(q,k)$-system is a $k$-uniform hypergraph
(henceforth $k$-graph) whose edge set is the union of cliques with $q$
vertices that pairwise share at most $\ell$ vertices. Such hypergraphs are
ubiquitous in combinatorics. Here are some examples:

  * •

$\ell$-$(q,k)$-systems are extremal examples for many well-studied questions
in extremal set theory, for example, an old open conjecture of Erdős [6]
states that the maximum number of triples in an $n$-vertex triple system with
no two disjoint pairs of edges with the same union is achieved by
1-$(5,2)$-systems.

  * •

Recently, Liu, the first author and Reiher [12] constructed the first family
of hypergraphs that fail to have the stability property and
$\ell$-$(q,k)$-systems were a crucial ingredient in constructing the extremal
examples.

  * •

Classical old open questions in projective geometry ask for the maximum size
of caps in various projective spaces. The triple system of collinear triples
in projective space is a $1$-$(q,3)$-system by letting the $q$-sets be lines.
Hence results about the independence number and chromatic number of
$1$-$(q,3)$-systems have connections to questions about large caps in
projective spaces, which is a fundamental problem in finite geometry.

The chromatic number $\chi(H)$ of a hypergraph $H$ is the minimum number of
colors required to color the vertex set of $H$ so that no edge of $H$ is
monochromatic. A fundamental question about hypergraphs, first systematically
investigated in the seminal work of Erdős and Lovász [8], is to determine the
maximum chromatic number of a hypergraph with a specified number of edges. In
this paper, we consider this problem for $\ell$-$(q,k)$-systems. Call a clique
with $q$ vertices a $q$-clique.

######  Definition 1.

Given integers $1\leq\ell<k\leq q$ and $e\geq 1$, let $f_{\ell}(e,q,k)$ be the
maximum chromatic number of an $\ell$-$(q,k)$-system where the number of
$q$-cliques is $e$.

Perhaps the most natural and interesting case is $\ell=k-1$ so in this case we
use the simpler terminology “$(q,k$)-system” and write
$f(e,q,k)=f_{k-1}(e,q,k)$. We are interested in $f_{\ell}(e,q,k)$ when $k$ is
fixed and both $q$ and $e$ are large. Special cases of this function have been
extensively studied in the past. For example, the celebrated Erdős-Faber-
Lovász conjecture [7, 10, 11] for graphs, which states that the maximum
chromatic number of a collection of $q$ almost disjoint $q$-cliques is $q$, is
the statement $f(q,q,2)=q$. Another example when $k>2$ is fixed, is
$f_{\ell}(e,k,k)$, the largest possible chromatic number of partial designs, a
classical question first studied by Erdős and Lovász [8], and subsequently by
Ajtai et.al. [1] whose results were sharpened by Rödl and Šiňajová [13] and
many others.

It is well-known that for $k$ fixed, every $k$-graph with $m$ edges has
chromatic number $O(m^{1/k})$. Indeed, color the vertices randomly and
independently with $O(m^{1/k})$ colors. The expected number of monochromatic
edges is $O(m^{1-(k-1)/k})=O(m^{1/k})$. Now assign new colors one by one to
some vertex inside each monochromatic edge to get a proper coloring.
Altogether we used at most $O(m^{1/k})$ colors and there are no monochromatic
edges.

An $(e,q,k)$-system has exactly $e{q\choose k}$ edges, so for fixed $k$, the
argument above yields

$f(e,q,k)=O(e^{1/k}q).$

If there is an $n$-vertex $q$-graph $H$ such that every $k$-set of vertices
lies in exactly one edge, then the chromatic number of the $(q,k)$-system
comprising the $q$-cliques of $H$ is exactly $n/(k-1)$. The number of $q$-sets
in $H$ is $e={n\choose k}/{q\choose k}=(n)_{k}/(q)_{k}$ and hence the
chromatic number of this $(q,k)$-system is of order $e^{1/k}q$. This shows
that $f(e,q,k)=\Theta(e^{1/k}q)$ for $e=(n)_{k}/(q)_{k}$. However, all known
constructions of these designs require the number of vertices, $n$, and hence
also $e$, to be exponential in $q$.

Our first result below is a similar lower bound (construction) for $f(e,q,k$)
when $e$ is polynomial in $q$. The construction combines algebraic and
probabilistic ideas, by taking a random restriction of $(q,2)$ systems
obtained from an affine plane – see also [2].

######  Theorem 2.

Fix $k\geq 2$. Suppose that $q>k$ is sufficiently large and
$2^{q}>e>(50q)^{k}$. Then there exists an $(e,q,k)$-system with chromatic
number at least $\Omega(e^{1/k}q)$. Consequently, for this choice of
parameters, $f(e,q,k)=\Theta(e^{1/k}q)$.

The case $k=2$ deserves further mention. Hindman [9] was the first to observe
that the determination of $f(q,q,2)$ is equivalent to determining the edge
chromatic number of the dual hypergraph, and using this formulation Chang and
Lawler [3] gave the following nontrivial upper bound.

######  Proposition 3.

([3]) Suppose that $2<q<e<q^{2}$. Then $e/4<f(e,q,2)<3e/2$.

The lower bound in the proposition is proved as follows: let $p$ be a prime
such that $e^{1/2}/2<p\leq e^{1/2}$ and let $A(2,p)$ be the affine plane of
order $p$. Form $H$ by enlarging each line of $A(2,p)$ by adding $q-p\geq
q-e^{1/2}\geq 0$ new vertices such that distinct lines have disjoint
enlargements. The resulting $(q,2)$-system $H$ has $p^{2}\leq e$ $q$-cliques,
and we may add disjoint $q$-sets arbitrarily so that we have exactly $e$
cliques. In a proper coloring, every two vertices in $A(2,p)$ must receive
distinct colors, and hence $\chi(H)\geq p^{2}>e/4$.

If we use the prime number theorem, then as $q\rightarrow\infty$, this
construction yields $f(e,q,2)\geq(1+o(1))e$. Kahn [10] proved an upper bound
for $f(e,q,2)$ that is asymptotically optimal in the range $e<q^{2}$ so as
$q\rightarrow\infty$,

$f(e,q,2)=(1+(1))e\qquad\hbox{ for }\qquad q\leq e\leq q^{2}.$

There is a further improvement $f(e,q,2)\leq e$ for $e$ sufficiently large
[11].

The next case $k=3$ seems wide open in the case that $e$ is small. For
$e>q^{3}$, we have $f(e,q,3)=\Theta(e^{1/3}q)$ by Theorem 2. For
$q^{3/2}<e<q^{3}$, we have the lower bound $\Omega(e^{2/3})$ by taking the
circles in an inversive plane of order $(1+o(1))e^{1/3}$ and adding disjoint
sets of new points to the circles to create $q$-sets. Any three points in the
inversive plane lie in a circle and hence an edge of our hypergraph, so the
independence number is at most two, and the chromatic number is at least half
the number of vertices in the inversive plane which is $\Theta(e^{2/3})$.
Apart from this we have no nontrivial lower or upper bounds in the range
$q<e<q^{3}$.

######  Problem 4.

Determine the order of magnitude of $f(e,q,3)$ in the range $q<e<q^{3}$.

Another interesting case is $f_{1}(e,q,k)$ when $k>2$ (the $q$-sets form a
linear $q$-graph). Here we prove the following theorem which gives bounds that
get closer as $k$ increases. The lower bound is obtained via a random greedy
algorithm. It is one of the few instances where a constrained random $q$-graph
process on $n$ vertices is analyzed where $q$ is polynomial in $n$.

######  Theorem 5.

Fix $k\geq 3$. There exist a constant $C$ such that

$e^{\frac{1}{2k-2}}q^{1-\frac{2}{k-1}+o(1)}<f_{1}(e,q,k)<C\,e^{\frac{1}{2k-2}}q$

where the lower bound holds for $e>q^{2k+2}$.

We believe that the upper bound above is sharp in order of magnitude for $e$
sufficiently large.

######  Conjecture 6.

Fix $k\geq 3$. There exists $C=C_{k}>0$ such that if $e>q^{C}$, then

$f_{1}(e,q,k)=\Theta(e^{\frac{1}{2k-2}}q)\qquad(q\to\infty).$

It is an interesting wide open problem to study the behavior of $f_{1}(e,q,k)$
for smaller values of $e$. The smallest case $k=3$ naturally gives rise to a
particular class of 1-$(e,q,3)$ systems, namely the collection of collinear
triples in lines in finite projective planes. In fact, one possible way to
obtain 1-$(q,3)$ systems is to take projective planes with few caps, and then
take a random restriction of the points. While it is not clear how to obtain
constructions in this manner that supersede the random greedy algorithm, it
does suggest another fundamental question, namely to count the number of caps
in a finite projective/affine plane.

Define $I_{q}$ to be the maximum number of caps in an affine plane of order
$q$. In a Desarguesian plane the normal rational curve yields a cap of size at
least $q+1$ and since all subsets of a cap are caps, we have at least
$2^{q+1}$ caps. However, in general affine planes, the largest known caps that
are guaranteed to exist are of order $(q\log q)^{1/2}$ giving
$I_{q}>2^{c\,(q\log q)^{1/2}}$. On the other hand, the maximum size of a cap
in any affine plane of order $q$ has size at most $q+2$, and this yields the
bound $I_{q}<{q^{2}\choose q+2}<2^{c\,q\log q}$. We give improvements to both
these bounds.

######  Theorem 7.

There is an absolute constant $c$ such that for all sufficiently large $q$ for
which $I_{q}$ is defined,

$2^{c\,q^{1/2}(\log q)^{3/2}}<I_{q}<2^{6q}.$

There is still a huge gap between our upper and lower bounds for $I_{q}$,
however, as mentioned earlier, if we restrict to the case of
Desaguesian/Galois planes, our upper bound is much closer to the truth. Define
$I^{\prime}_{q}$ to be the maximum number of caps in a Galois affine plane
$A(2,q)$. Thus $I^{\prime}_{q}\leq I_{q}$ and perhaps equality holds. Then
Theorem 7 yields $2^{q+1}<I^{\prime}_{q}<2^{6q}$.

######  Conjecture 8.

$I^{\prime}_{q}=2^{(1+o(1))q}$.

##  2 Random restrictions of Affine planes

We will use the following version of the Chernoff bounds.

######  Lemma 9 (Multiplicative Chernoff Bounds).

Suppose $X_{1},\ldots,X_{n}$ are independent random variables taking values in
$\\{0,1\\}$. Let $X$ denote their sum and let $\mu=E[X]$ denote the expected
value of $X$. Then for any $\delta>0$,

$\Pr(X\leq(1-\delta)\mu)<\exp(-\delta^{2}\mu/2)$
$\Pr(X\geq(1+\delta)\mu)<\exp(-\delta^{2}\mu/(2+\delta)).$

Proof of Theorem 2. By the prime number theorem, there is a prime number
$Q\geq q$ such that $(1/2)e<Q^{k}+Q\leq e$. Let
$V=\mathbb{F}_{Q}\times\mathbb{F}_{Q}$. Given a polynomial $p(x)$ over
$\mathbb{F}_{Q}$ let $S(p(x))=\\{p(x):x\in\mathbb{F}_{Q}\\}$. Let $H_{Q}$ be
the $Q$-graph with vertex set $V$ and edge set

$\\{S(p(x)):\deg(p(x))<k)\\}\cup\\{C_{x}:x\in\mathbb{F}_{Q}\\}$

where $C_{x}=\\{(x,y):y\in\mathbb{F}_{Q}\\}$ is the column of $x$. The number
of edges in $H_{Q}$ is $Q^{k}+Q\leq e$.

Let $W$ be a random subset of $V$ obtained by picking each element of $V$
independently with probability $p=\frac{q}{10Q}$. Given an edge $f\in H_{Q}$,
the expected size of $f\cap W$ is $q/10$ and the multiplicative Chernoff bound
with $\mu=q/10$ and $\delta=9$ implies that the probability that $|f\cap W|>q$
is at most $\exp(-81q/110)$. The number of edges $f$ in $H_{Q}$ is
$Q^{k}+Q\leq e<2^{q}$, so the union bound implies that

$\Pr(\exists f:|f\cap W|>q)<2^{q}\exp(-81q/110)<(0.96)^{q}.$

For $C$ a sufficiently large constant, the probability that $|W|<pQ^{2}/C$ is
by the multiplicative Chernoff bound (with $\mu=pQ^{2}$ and $\delta=1-1/C$) at
most

$\exp(-0.49pQ^{2})=\exp(-0.049qQ).$

Since $e>(50q)^{k}$, we have $Q>(e/4)^{1/k}\geq 25q$, and
$\exp(-0.049qQ)<\exp(-q^{2})$. Since $(0.96)^{q}+\exp(-q^{2})<1$, there is a
set $W$ such that $|f\cap W|\leq q$ for all $f$ and $|W|=\Omega(qQ)$. Let
$H^{\prime}$ be the $k$-graph with vertex set $W$ whose edges are the
$Q^{k}+Q$ cliques ${f\cap W\choose k}$.

We now prove that $\alpha(H^{\prime})\leq(k-1)^{2}+1$.

Claim. Given $(x_{1},y_{1}),\ldots,(x_{k},y_{k})$ in
$\mathbb{F}_{Q}\times\mathbb{F}_{Q}$ with the $x_{i}$s distinct, there is a
(unique) polynomial $p(x)$ of degree less than $k$ with $p(x_{i})=y_{i}$ for
$i\in[k]$.

Proof of Claim. Write $p(x)=\sum_{j=0}^{k-1}a_{j}x^{j}$. Then the conclusion
of the Claim is equivalent to the matrix equation $Ba=y$, where $B$ is the $k$
by $k$ Vandermonde matrix with parameters $x_{1},\ldots,x_{k}$,
$a=(a_{0},\ldots,a_{k-1})^{T}$ and $y=(y_{1},\ldots,y_{k})^{T}$. Since the
$x_{i}$s are distinct, $B$ is invertible and hence there is a unique solution
$a$.

Pick a set $I\subset W$ of vertices of size at least $(k-1)^{2}+1$. If $I$ has
at least $k$ vertices in some column $C_{x}$, then these $k$ vertices lie in
$C_{x}\cap W$ and hence lie in an edge of $H^{\prime}$. Therefore, by the
pigeonhole principle, $I$ has at least $k$ vertices in distinct columns. By
the Claim, these $k$ vertices lie in a unique $S(p(x))$ and hence lie in an
edge of $H^{\prime}$. This proves that $\alpha(H^{\prime})\leq(k-1)^{2}+1$.

Finally, we modify $H^{\prime}$ by adding $q-|f\cap W|$ new vertices to each
set $f\cap W$ so as to make a clique of size exactly $q$. This produces an
$(e,q,k)$-system with chromatic number at least
$|W|/k^{2}=\Omega(qQ)=\Omega(e^{1/k}q)$ as required.

##  3 The case $\ell=1$

Here we prove the upper bound in Theorem 5. Note that the number of $k$-sets
in a $(q,k)$-system where the number of $q$-cliques is $e$ is $e{q\choose k}$
so the trivial bound is $f_{1}(e,q,k)=O(e^{1/k}q)$.

######  Theorem 10.

For each fixed $k\geq 3$, we have $f_{1}(e,q,k)=O(e^{1/(2k-2)}q)$.

###### Proof.

Let $H$ be a $(q,k)$-system with $e$ edges. Put $d:=e^{1/2}q^{k-1}$. Let
$A=\\{v\in V(H):d(v)\leq d\\}$ and $B=V(H)\setminus B$. Since
$\Delta(H[A])\leq d$, the local lemma implies that there is a proper coloring
of $H[A]$ with at most $O(d^{1/(k-1)})=O(e^{1/(2k-2)}q)$ colors. Since

$ke{q\choose k}\geq\sum_{v\in B}d(v)\geq|B|d=|B|e^{1/2}q^{k-1}$

we obtain $|B|=O(e^{1/2}q)$. Now consider $v\in B$. The edges in $H$
containing $v$ that lie within $B$ are all in subsets of $q$-cliques
containing $v$. Let $A_{1},\ldots,A_{p}$ be the set of $q$-cliques containing
$v$ that have at least $k$ vertices in $B$ and let $a_{i}=|A_{i}\cap B|$. Then
the degree of $v$ in $H[B]$ is $\sum_{i}{a_{i}-1\choose k-1}$. Since
$A_{i}\cap A_{j}=\\{v\\}$, we have $\sum(a_{i}-1)<|B|=O(e^{1/2}q)$. The
quantity $\sum_{i}{a_{i}-1\choose k-1}$ subject to this constraint is
maximized when as many of the $a_{i}$ are as large as possible and the rest
are as small as possible. Since $a_{i}\leq q$, we obtain

$\sum_{i}{a_{i}-1\choose k-1}\leq\frac{|B|-1}{q-1}{q-1\choose
k-1}=O(e^{1/2}q^{k-1})=O(d).$

Hence the maximum degree of $H[B]$ is $O(d)$ and once again we can properly
color $H[B]$ with $O(e^{1/(2k-2)}q)$ colors. We always use colors that have
not been used in $H[A]$. In particular, this implies that if there is a
$k$-set that has vertices in both $A$ and $B$, then it will not be
monochromatic in our coloring. The resulting coloring is a proper coloring of
$H$ with $O(e^{1/(2k-2)}q)$ colors.

Remark. A further improvement by polylog factors can be achieved above using
more advanced results to color the vertices in $B$.

##  4 Lower bound for 1-$(q,k)$ systems using random greedy

In this section we prove the lower bound in Theorem 5:
$f(e,q,k)=\Omega^{*}(e^{1/(2k-2)}q^{1-2/(k-1)})$ for $e>q^{2k+2}$ where the
$*$ indicates some extra polylog factors in $e$.

Fix $k\geq 3$. Consider the random greedy $(q,k)$-process: We pick a $q$-set
$e_{1}$ of $[n]$ at random. Given that we have picked $e_{1},\ldots,e_{i}$, we
pick a $q$-set $e_{i+1}$ randomly (with equal probability) from all other
$q$-sets that do not intersect any of $e_{1},\ldots,e_{i}$ in more than one
point. Eventually we obtain a (random) $q$-graph $G^{q}$ with $e$ edges, and
also a random $k$-graph $H=H^{k}=\cup_{i=1}^{e}{e_{i}\choose k}$, which has
$e{q\choose k}$ edges.

Fix a $t$-set $I$ of $[n]$ and let us calculate the probability that $I$ is an
independent set in $H^{k}$. For $i\geq 0$, let

$W_{j}=\left\\{S\in{[n]\choose q}:|S\cap I|=j\right\\}$

and put $M=\cup_{j=k}^{q}W_{j}$ and $m:=|M|$. Here $M$ stands for missing
$q$-sets since these $q$-sets cannot be present in $G^{q}$ as $I$ is an
independent set in $H^{k}$. Note that $w_{j}:=|W_{j}|\leq{t\choose j}{n\choose
q-j}$. Say that $A\in W_{j}$ blocks $B\in M$ if $|A\cap B|\geq 2$ and let
$b_{j}$ be the number of sets in $M$ blocked by an $A\in W_{j}$ (it is the
same for all $A$). We write $f\gg g$ to mean that there is a (large) positive
constant $c=c_{k}$ such that $f\geq cg$. From now on, we assume that

$n\gg tq^{2}\qquad\hbox{ and }\qquad t\gg 10k\left(\frac{n^{k-2}\log
n}{q^{k-4}}\right)^{\frac{1}{k-1}}.$

We then have

$b_{0}<q^{2}t^{k}{n\choose q-k-2}$ $b_{1}\leq q{t\choose k-1}{n\choose
q-k-1}+q^{2}t^{k}{n\choose q-k-2}<qt^{k-1}{n\choose q-k-1}$

and for $2\leq j\leq k-1$,

$b_{j}\leq{j\choose 2}{t\choose k-2}{n\choose q-k}+jqt^{k-1}{n\choose
q-k-1}+q^{2}t^{k}{n\choose q-k-2}<2t^{k-2}{n\choose q-k},$

where we use $n/tq^{2}\rightarrow\infty$ in the last two displays. Note that
$m=\Theta(t^{k}{n\choose q-k})$. Let $a_{j}=m/b_{j}$ so that

$a_{0}=\Theta\left(\frac{n^{2}}{q^{4}}\right)\qquad
a_{1}=\Theta\left(\frac{tn}{q^{2}}\right)\qquad
a_{j}=\Theta(t^{2})\qquad\hbox{ for $2\leq j\leq k-1$}.$

Claim. If $I$ is an independent set, then at least $a_{j}/k$ edges of $W_{j}$
must be present in $G^{q}$ for some $0\leq j\leq k-1$.

Proof. If not, since no set of $M$ is in $G^{q}$, the number of sets in $M$
that are blocked is less than $\sum_{j=0}^{k-1}b_{j}(a_{j}/k)\leq m$. This
means that some edge of $M$ would be in $G^{q}$, contradicting the fact that
$I$ is an independent set.

Let $G_{i}=G_{i}^{q}$ be the (random) $q$-graph obtained after $i$ edges have
been added and let $e_{i}$ be the $q$-set added at step $i$. Define

$\ell:=\min\\{i:|W_{j}\cap G_{i}|\geq a_{j}/3k\hbox{ for some
$j=0,1,\ldots,k-1$}\\}.$

In words, $\ell$ is the smallest index such that $G_{i}$ contains at least
$a_{j}/3k$ edges from $W_{j}$ for some $j$.

For $0\leq j\leq k-1$, let $A_{j}$ be the event that $I$ is an independent set
and $e_{\ell}\in W_{j}$. The Claim, the definition of $\ell$, and the union
bound imply that

$\Pr(I\hbox{ is independent})\leq\sum_{j=0}^{k-1}\Pr(A_{j}).$

Let $m_{i}=|M\setminus G_{i}|$ . Since $|W_{j}\cap G_{\ell}|\leq a_{j}/3k$ for
each $j\in\\{0,1,\ldots,k-1\\}$, we have for $i\leq\ell$,

$m_{i}\geq m_{\ell}\geq m-\sum_{j=0}^{k-1}b_{j}(a_{j}/3k)\geq m-km/3k>m/2.$

For each $S\subset\\{1,\ldots,e\\}$, define the event

$A_{0}(S):=\\{G^{q}\in A_{0}:e_{i}\in W_{0}\Leftrightarrow i\in S\\}.$

These events are disjoint for distinct $S$ and hence

$\Pr(A_{0})=\sum_{S\subset[e]}\Pr(A_{0}(S)).$

If $\Pr(A_{0}(S))>0$, then since $I$ is an independent set there is a subset
$S^{\prime}\subset S$ with $|S^{\prime}|\geq a_{0}/3k$ and $m_{i}\geq m/2$ for
all $i\in S^{\prime}$. Hence we can further write

$\Pr(A_{0})=\sum_{|S|\geq a_{0}/3k}\Pr(A_{0}(S)).$

Write $w_{j,i}=|W_{j}\setminus G_{i}|$ and $r_{i}=w_{1,i}+\cdots+w_{k-1,i}$
for $j=0,1,\ldots,k-1$. Then

$\displaystyle\Pr(A_{0})$
$\displaystyle\leq\sum_{|S|\geq\frac{a_{0}}{3k}}\left(\prod_{i\in
S}\Pr(e_{i}\in W_{0})\prod_{i\not\in S}\Pr(e_{i}\in W_{1}\cup\cdots\cup
W_{k-1})\right)$ $\displaystyle=\sum_{|S|\geq\frac{a_{0}}{3k}}\prod_{i\in
S}\left(\frac{w_{0,i}}{w_{0,i}+m_{i}+r_{i}}\right)\prod_{i\not\in
S}\left(\frac{r_{i}}{w_{0,i}+m_{i}+r_{i}}\right)$
$\displaystyle=\sum_{|S|\geq\frac{a_{0}}{3k}}\prod_{i\in
S}\left(\frac{w_{0,i}}{w_{0,i}+m_{i}}\right)\left(\frac{w_{0,i}+m_{i}}{w_{0,i}+m_{i}+r_{i}}\right)\prod_{i\not\in
S}\left(\frac{r_{i}}{w_{0,i}+m_{i}+r_{i}}\right)$
$\displaystyle=\sum_{|S|\geq\frac{a_{0}}{3k}}\prod_{i\in
S}\left(1-\frac{m_{i}}{w_{0,i}+m_{i}}\right)\left(\frac{w_{0,i}+m_{i}}{w_{0,i}+m_{i}+r_{i}}\right)\prod_{i\not\in
S}\left(\frac{r_{i}}{w_{0,i}+m_{i}+r_{i}}\right)$
$\displaystyle\leq\exp\left(-\frac{ma_{0}}{6kw_{0}}\right)\sum_{|S|\geq\frac{a_{0}}{3k}}\prod_{i\in
S}\left(\frac{w_{0,i}+m_{i}}{w_{0,i}+m_{i}+r_{i}}\right)\prod_{i\not\in
S}\left(\frac{r_{i}}{w_{0,i}+m_{i}+r_{i}}\right)$
$\displaystyle\leq\exp\left(-\frac{ma_{0}}{6kw_{0}}\right)\sum_{S\subset[e]}\prod_{i\in
S}\left(\frac{w_{0,i}+m_{i}}{w_{0,i}+m_{i}+r_{i}}\right)\prod_{i\not\in
S}\left(\frac{r_{i}}{w_{0,i}+m_{i}+r_{i}}\right)$
$\displaystyle=\exp\left(-\frac{ma_{0}}{6kw_{0}}\right)\prod_{i=1}^{e}\left(\frac{w_{0,i}+m_{i}}{w_{0,i}+m_{i}+r_{i}}+\frac{r_{i}}{w_{0,i}+m_{i}+r_{i}}\right)$
$\displaystyle=\exp\left(-\frac{ma_{0}}{6kw_{0}}\right).$

We observe that ${n\choose t}\Pr(A_{0})<1/k$ since this follows from

$\frac{ma_{0}}{6kw_{0}}=\frac{m^{2}}{6kb_{0}w_{0}}>\frac{[{t\choose
k}{n\choose q-k}]^{2}}{6kq^{2}t^{k}{n\choose q-k-2}{n\choose q}}>t\log n$

which holds due to $t^{k-1}\gg 10kn^{k-2}\log n/q^{k-4}.$ Similarly,
${n\choose t}\Pr(A_{1})<1/k$ follows from

$\frac{m^{2}}{6kb_{1}w_{1}}>\frac{[{t\choose k}{n\choose
q-k}]^{2}}{6kqt^{k-1}{n\choose q-k-1}t{n\choose q-1}}\gg t\log n$

using the weaker bound $t^{k-1}\gg n^{k-2}\log n/q^{k-3}$. Finally, ${n\choose
t}\Pr(A_{j})<1/j$ for each $2\leq j\leq k-1$ follows from

$\frac{m^{2}}{6kb_{j}w_{j}}>\frac{[{t\choose k}{n\choose
q-k}]^{2}}{12kt^{k-2+j}{n\choose q-k}{n\choose q-j}}\gg t\log n.$

This is equivalent to

$t>\left(\frac{n^{k-j}\log n}{q^{k-j}}\right)^{\frac{1}{k+1-j}}.$

Using $t\gg 10k\left(\frac{n^{k-2}\log n}{q^{k-4}}\right)^{\frac{1}{k-1}}$
this follows from

$\left(\frac{n^{k-2}\log n}{q^{k-4}}\right)^{k+1-j}\gg\left(\frac{n^{k-j}\log
n}{q^{k-j}}\right)^{k-1}$

which is equivalent to $n^{j-2}\gg(\log n)^{j-2}q^{3j-2k-4}$ and this is
trivial using $n>q$ and $j<k$.

So with positive probability $\alpha(H^{k})<t$.

Let $e$ be the number of edges in $G^{q}$. Certainly $e<n^{2}/q^{2}$ since
$G^{q}$ is a $(q,k)$-system and we may add edges arbitrarily so that
$e=n^{2}/q^{2}$. Setting $n=Ctq^{2}$ for large $C$ we obtain that

$\chi(H^{k})\geq\frac{n}{t}=\Omega\left(\left(\frac{nq^{k-4}}{\log
n}\right)^{\frac{1}{k-1}}\right)=\Omega^{*}\left({e^{\frac{1}{2k-2}}q^{1-\frac{2}{k-1}}}\right).$

Consequently, $f(e,q,k)=\Omega^{*}(e^{1/(2k-2)}q^{1-2/(k-1)})$ and a short
calculation solving for $t$ and $n$ in terms of $q$ yields that this holds for
$e>q^{2k+2}$

In the proof above we used the trivial bound $e<n^{2}/q^{2}$. We do not know
that this is tight. The value of $e$ could theoretically be as low as
$n^{2}/q^{3}$ in which case our lower bound on $f(e,q,k)$ would be
$\Omega^{*}(e^{1/(2k-2)}q^{1-3/(2k-2)})$. It is a very interesting question to
study the final number of edges in the $(q,k)$-process when $q$ polynomially
related to $n$.

The random greedy process above requires $e$ large while our upper bound
$f(e,q,k)=O(e^{1/(2k-2)}q)$ applies for all $e$, so it is interesting to study
the situation for $e<q^{2k+2}$. Taking the collinear triples in a projective
plane quickly yields

$f(q^{2}+q+1,q,3)\geq(q^{2}+q+1)/(q+2)>q-1=\Omega(e^{1/4}q^{1/2})$

for $e=\Theta(q^{2})$.

##  5 Counting caps in affine/projective spaces

In this section we prove Theorem 7. We require the following lemma from [4].
Recall that $\tau(F)$ is the minimum size of a vertex subset of $F$ that
intersects every edge of $F$.

######  Lemma 11.

Suppose $F$ is an $s$-uniform hypergraph, and $z_{i}$, $i\in V(F)$ are
independent random indicator variables with $\Pr[z_{i}=1]=p$, for all $i\in
V(F)$. Let

$F^{\prime}=\\{A\in F:\forall i\in A,z_{i}=1\\}.$

Suppose there exists $\alpha>0$ such that $|F|p^{s(1-\alpha)}<1$. Then for any
$c\geq e2^{s}s\alpha$,

$\Pr[\tau(F^{\prime})>s^{2}(c/\alpha)^{s+1}]\leq s^{2}|V(F)|^{s-1}p^{c}.$

The reason we need to use the lemma above is to take care of codegrees that
may be of logarithmic size (the codegree of a pair of vertices is the number
of edges containing them both). We also need the following result from [5];
the result as stated in [5] applies to linear hypergraphs but standard methods
imply the same bound for hypergraphs with bounded maximum codegree.

######  Theorem 12 ([5], Theorem 3).

Fix $s>0$. There exists a constant $c=c_{s}>0$ such that the number of
independent sets in every $n$-vertex 3-graph with average degree $d$ and
maximum codegree $s$ is at least $2^{c\,n(\log d)^{3/2}/d^{1/2}}$.

Proof of Theorem 7. We start with the lower bound. A cherry is the 5 vertex
3-graph comprising three edges, every two of which share the same two
vertices. Let $H$ be a $(q,3)$-system with $n=q^{2}$ vertices, average degree
at most $q^{3}$, and maximum codegree at most $q$. Note that the collinear
triples of any affine plane of order $q$ can be viewed as such a
$(q,3)$-system $H$.

Our plan is to take a random induced subgraph of $H$ on $q^{3/5-\epsilon}$
vertices where there is a small set of vertices that touches every cherry. To
this end we apply Lemma 11 with $F$ being the 5-graph of copies of cherries in
$H$ and $p=q^{-7/5-\epsilon}$. Letting $\alpha$ be sufficiently small in terms
of $\epsilon$, we obtain

$|F|p^{(1-\alpha)s}<n^{2}q^{3}p^{(1-\alpha)s}<q^{7}q^{-5(1-\alpha)(7/5+\epsilon)}=o(1).$

Hence for $c$ a large constant, Lemma 11 and standard Chernoff bounds yield
that with probability greater than 0.9 say, a random induced subgraph
$H^{\prime}$ of $H$ with $p$ as above has $m=\Theta(q^{3/5-\epsilon})$
vertices, average degree $d=O(p^{2}q^{3})=O(q^{1/5-2\epsilon})$ and has a set
$S$ of $O(1)$ vertices whose removal makes it $F$-free. Since $H^{\prime}-S$
has no cherry, it has maximum codegree at most two. Theorem 12 now implies
that the number of independent sets in $H^{\prime}-S$, and hence also in $H$,
is at least $2^{c\,q^{1/2}(\log q)^{3/2}}$.

We now prove the upper bound. Let $G=(P,L,E)$ be the point line incidence
graph of the affine plane of order $q$. It is well known that $G$ satisfies
the bipartite expander mixing lemma:

$\left|e(X,Y)-\frac{d}{n}|X||Y|\right|<\sqrt{q|X||Y|}$

for all sets $X\subset P$ and $Y\subset L$. Let $I_{q,t}$ be the number of
caps of size $t$ and let us enumerate such caps in the affine plane by
choosing sequences of $t$ vertices in $P$. Note that $I_{q,t}=0$ for $t>q+2$.
The first two vertices can be chosen arbitrarily. Given that $i\geq 2$ and
vertices $v_{1},\ldots,v_{i}$ have been chosen, let $Z_{i}=\\{y\in L:\exists
x,x^{\prime}\in X,xy,x^{\prime}y\in E\\}$ be the set of common neighbors of
pairs of vertices in $S_{i}=\\{v_{1},\ldots,v_{i}\\}$. Let $X_{i}\subset P$ be
the set of nonneighbors of $Z_{i}$. The next vertex $v_{i+1}$ in the cap must
come from $X_{i}$. The expander mixing lemma now yields

$0=e(X_{i},Z_{i})\geq\frac{|X_{i}||Z_{i}|}{q}-\sqrt{q|X_{i}||Z_{i}|}=\frac{|X_{i}|{i\choose
2}}{q}-\sqrt{q|X_{i}|{i\choose 2}}.$

This yields $|X_{i}|\leq q^{3}/{i\choose 2}.$ Consequently, For $2<t\leq q+2$,

$I_{q,t}\leq\frac{q^{4}\prod_{i=2}^{t-1}\min\\{q^{2},q^{3}/{i\choose
2}\\}\\}}{t!}.$

If $t<2\sqrt{q}$ we just use the bound

$I_{q,t}\leq\frac{q^{4}\prod_{i=2}^{t-1}q^{2}}{t!}=2^{O(\sqrt{q}\log q)}.$

For $t>2\sqrt{q}$, using $n!>(n/e)^{n}$ we have

$I_{q,t}\leq\frac{2^{O(\sqrt{q}\log
q)}\prod_{i=2\sqrt{q}}^{t-1}\frac{2q^{3}}{i(i-1)}}{t!}<2^{O(\sqrt{q}\log
q)}\frac{2^{t}q^{3t}}{(t!)^{3}}<2^{O(\sqrt{q}\log
q)}\left(\frac{2^{1/3}eq}{t}\right)^{3t}.$

An easy calculus exercise shows that the maximum of $(2^{1/3}eq/t)^{3t}$ for
$2\sqrt{q}<t\leq q+2$ and $q$ sufficiently large occurs either at the endpoint
$t=q+2$ or at $t=2^{-2/3}eq$ (all logs are base 2). Checking both these points
we see that the maximum is in the latter case and is less than $2^{5.77q}$.
Consequently, $I_{q,t}<2^{5.77q+O(\sqrt{q}\log q)}$ and for $q$ sufficiently
large,

$I_{q}=q^{2}+q^{2}(q^{2}-1)+q\cdot\max_{3\leq t\leq
q+2}I_{q,t}<2^{5.77q+O(\sqrt{q}\log q)}<2^{6q}$

as desired.

## References

  * [1] M. Ajtai, J. Komló s, J. Pintz, J. Spencer, E. Szemerédi, Extremal uncrowded hypergraphs. J. Combin. Theory Ser. A 32 (1982), no. 3, 321–335.
  * [2] N. Alon, K. Mellinger, D. Mubayi, J. Verstraete. The de Bruijn-Erdős theorem for hypergraphs. Des. Codes Cryptogr. 65 (2012), no. 3, 233–245.
  * [3] W. I. Chang, E. L. Lawler, Edge coloring of hypergraphs and a conjecture of Erdős, Faber, Lovász, Combinatorica, 8 (1988) (3): 293–295.
  * [4] J. Cooper, D. Mubayi, Coloring sparse hypergraphs, SIAM J. Discrete Math. 30 (2016), no. 2, 1165–1180.
  * [5] J. Cooper, K. Dutta, D. Mubayi, Counting independent sets in hypergraphs, Combinatorics, Probability and Computing 23 (2014), no. 4, 539–550.
  * [6] P. Erdős, Problems and results in combinatorial analysis. Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1977), pp. 3–12. Congressus Numerantium, No. XIX, Utilitas Math., Winnipeg, Man., 1977.
  * [7] P. Erdős, On the combinatorial problems which I would most like to see solved. Combinatorica 1 (1981), no. 1, 25–42.
  * [8] P. Erdős, L. Lovász, Problems and results on 3-chromatic hypergraphs and some related questions. In A. Hajnal; R. Rado; V. T. Sós (eds.). Infinite and Finite Sets (to Paul Erdős on his 60th birthday). Vol. II. North-Holland. pp. 609–627.
  * [9] N. Hindman, On a conjecture of Erdős, Faber, and Lovász about $n$-colorings”, Can. J. Math. (1981), 33 (3): 563–570.
  * [10] J. Kahn, Coloring nearly-disjoint hypergraphs with $n+o(n)$ colors”, Journal of Combinatorial Theory, Series A, 59 (1992), 31–39.
  * [11] D. Y. Kang, T. Kelly, D. Kühn, A. Methuku, D. Osthus, A proof of the Erdős-Faber-Lovász conjecture: algorithmic aspects. 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science—FOCS 2021, 1080–1089.
  * [12] X. Liu, D. Mubayi, C. Reiher, Hypergraphs with many extremal configurations, to appear, Israel. J. Math. (34 pages)
  * [13] V. Rödl, E. Šiňajová, Note on independent sets in Steiner systems, Random Structures Algorithms 5 (1994), no. 1, 183–190.