Further author information: (Send correspondence to R.B. and J.E.G.)
R.B.: E-mail<EMAIL_ADDRESS>Telephone: +354 765 5316
J.E.G.: E-mail<EMAIL_ADDRESS>Telephone +354 525 4625

# Vector beam mapping at millimeter wavelengths using a robot arm

Rustam Balafendiev  Science Institute, University of Iceland, 107 Reykjavik,
Iceland  Thomas Gascard  Science Institute, University of Iceland, 107
Reykjavik, Iceland  Jon Gudmundsson  Science Institute, University of Iceland,
107 Reykjavik, Iceland  The Oskar Klein Centre, Department of Physics,
Stockholm University, AlbaNova, SE-10691 Stockholm, Sweden

###### Abstract

Many experimental efforts are striving to provide deep maps of the cosmic
microwave background (CMB) to shed light on key questions in modern cosmology.
The primary science goal for some of these experiments is to further constrain
the energy scale of cosmic inflation. It has been shown that these experiments
are particularly sensitive to optical systematics. Near-field vector beam
mapping, or holography, is now employed in a variety of CMB-focused
experimental efforts due to the technique’s ability to provide full details of
electromagnetic field propagation through complex systems. In this proceeding,
we describe the development of a measurement bench for millimeter-wave phase-
sensitive beam mapping with the goal of characterizing optical components for
CMB experiments. We discuss the testing of a beam scanner based on a 6-axis
robot arm, the related custom control software, the readout architecture, and
the overall validation of the system through various testing procedures.
Dynamic range of $70\text{\,}\mathrm{dB}$ is demonstrated for the presented
setup. With the current mechanical setup, we derive an upper limits of
$45\text{\,}\mathrm{\SIUnitSymbolMicro m}$ on the absolute positioning error
and $10\text{\,}\mathrm{\SIUnitSymbolMicro m}$ on positional repeatability.

###### keywords:

Beam mapping, Holography, mm-wave, Cosmic microwave background, Instrument
characterization

##  1 INTRODUCTION

Measurements of the cosmic microwave background (CMB) that meet the science
goals of upcoming experiments call for strict requirements on various
instrument performance metrics.[1] This is particularly true for experiments
that search for primordial B-mode polarisation,[2] where a detailed
understanding of optical performance is critical to success.[3] For CMB
experiments in particular, coherent mm-wave measurements of both optical
components and full telescope assemblies can provide valuable data to inform
instrument models used for cosmological analysis. This technique is currently
employed, both at room and cryogenic temperatures, to advance the
understanding of the optical performance of instruments currently in
development.[4, 5, 6] In this paper we describe a system for coherent mm-wave
measurements which uses a commercial 6-axis industrial robot to perform the
scanning instead of a system composed of multiple linear and rotation stages.

Robot arms have already been used for phase-sensitive microwave measurements
[7, 8, 9]. The use of robot arms offers some advantages over more traditional
linear translation methods frequently used for the characterization of optical
components [4, 10]. This includes ease of calibration and improved workspace
flexibility. In this paper we describe such a system, demonstrate its
usefulness for a measurement of a far field of a horn antenna, specifically
stressing the ease of calibrating for cross-polarisation, and attempt to
benchmark the positional accuracy of the robot arm using the measured phase
data. We also present custom open source software that can both be used to
perform similar measurements in the future and be adapted for other
measurement setups.

Figure 1: The 6-axis Kuka robot with a ZRX110 W-band reciever attached to a
custom aluminum mounting plate that bolts to the flange of the robot. The
Cartesian directions of movement are marked near the aperture of the horn,
with Z being the aperture normal. Angle $\phi$, positioned in the XY plane and
marked in yellow is used for polarisation modulation. Azimuth (YZ, magenta)
and elevation (XZ, cyan) are used to characterise the far field beam profiles
of the receiver horn.

##  2 System parameters and the control software

The system presented in this paper consists of a R&S ZNA26A Vector Network
Analyzer (VNA), W-band (75-$110\text{\,}\mathrm{GHz}$) ZC110 and ZRX110
frequency extension modules from R&S, and a KUKA KR 6 R900-2 6-axis robot arm
(Fig. 1). The ZRX110 receiver is attached to the robot arm flange and aligned
along the optical axis of the ZC110 transceiver placed approximately
$1.8\text{\,}\mathrm{m}$ away. The position of the center of the horn aperture
is used as the initial Tool Center Point (TCP) within the RoboDK[11] software,
a simulation environment used to preemptively visualise the planned scan and
send simple movement commands in its Python API to the robot controller. A
filter bandwidth of $1\text{\,}\mathrm{kHz}$ and no averaging are used in the
VNA data processing.

Figure 2: An example of how the user interface of the developed software looks
in the process of taking data. A detailed description of the numbered sections
is presesnted in section 2.

Manual and automated movements of the robot and parameters for the frequency
sweep are handled and passed through to the VNA and robot controller via a
custom software programmed in Python and available in the following GitHub
repository. The control software further offers a PyQT-based GUI overlay,
simplifying the manual control of the robot and the scan setup. Presently, two
choices of scanning trajectories are implemented: a scan in the Cartesian XYZ
coordinates relative to the TCP and an angular scan which sweeps the receiver
horn along elevation and azimuth around the TCP. The starting position of the
scan and orientation of the horn can be manually adjusted. The software also
communicates with the VNA in order to synchronize the movements of the robot
with the data acquisition and to obtain the raw complex-valued frequency
spectrum at the scanned points, which is then written to a 4D ($x,y,z,f$)
Numpy array.[12] The GUI also allows for live monitoring of the scan via a 2D
colormesh plot and 1D slices, comparing the experimental data with ones
obtained numerically and post-processing of the data directly in the software.
Currently, the post-processing capabilities include a 2D Fourier transform of
the scan and back-propagation of the obtained vector fields along the
Z-direction (see Figure 1). An example of the user interface in the process of
taking data is shown in Figure 2 with various sections labeled. The workflow
is divided into three main window tabs (1): the first one is used to establish
the connection with the VNA and the robot, the second allows for manual
control of the robot position as well as polarisation modulation and the third
one houses the scan settings. Various fields at the top of the scanning tab
are (2) used to set the initial point, orientation, span and resolution of the
scanned volume or plane. The section right after (3) houses the field used for
setting the settling time, an initial estimation of the scan duration and the
”Start scan” button.

An accurate estimation of the scan duration, visualised with a progress bar
(4), is made by extrapolating the average length of time required to move to
and measure a single point. Below is the drop-down menu for selection of
different scanning modes (5) and the buttons (6) for saving and loading the
measured data as well as loading the simulated results for comparison. The
lower half of the main window houses the fields for changing the VNA settings
(7), buttons for switching between running the scan in the software and
running it on the physical robot (8), live position monitoring (9) and the
message log (10). The detachable windows on the right display various plots
(11) of the measured data, depending on the chosen tab (12). Currently the
three options are: live monitoring of the traces from the VNA, a colormap of
the scanned surface and a 1D slice of the same surface through the user-
selected slice. The colormap tab presented in the figure has a few controls at
the bottom. First is the drop-down menu (13) for selecting the format of the
data: magnitude (linear or dB), phase, real and imaginary parts. A toggle for
calculating the Fourier image of the data shown is positioned to the right.
Next are various elements for controlling the displayed slice of the 4D
($x,y,z,f$) array (14). And last is the toggle for propagating the measured
field backward by the distance set by the slider (15). Various settings, such
as VNA and scan parameters can be saved and loaded using .toml files.

Figure 3: Angular far field scan results at $75\text{\,}\mathrm{GHz}$ for the
co- (top) and cross-polarisation (bottom) cases. a) Phase distribution of co-
polarisation. Some skew is noticeable due to fault in alignment, but overall
the phase variation remains within a $None$ range over the $None$ of azimuth
that are covered by the scan. b) Normalised magnitude distribution of co-
polarisation, in dB. A slice at $None$ of elevation is shown in dark red in
Fig. 4. c) Phase distribution of cross-polarisation. While there is some
warping, the characteristic cross-polarisation pattern of the phase having
discontinuities at $None$ of elevation and $None$ of azimuth can be observed.
b) Normalised magnitude distribution of cross-polarisation, in dB. A slice at
$None$ of elevation is shown in light red in Fig. 4.

##  3 Results

###  3.1 Dynamic range, far sidelobes and polarization modulation

In order to determine the dynamic range of the system we have performed a scan
within a range of angles in the Ludwig 2 azimuth-over-elevation coordinate
system[13]. Filter bandwidth of $10\text{\,}\mathrm{kHz}$ and no averaging
were used during the measurement. Each frequency sweep was comprised of 201
samples spanning the entire W-band (75-$110\text{\,}\mathrm{GHz}$), taking
about 0.02 seconds to complete. Angles in the range of $None$ to $None$ along
the azimuth and $None$ to $None$ along elevation were scanned by rotating the
horn around its phase center. Within RoboDK this is represented by the
position target being rotated around its X- and Y-axes respectively. The
optimal position of the phase center relative to the horn aperture, which
matches the position of the tool center point in RoboDK software, is found by
repeating this scan while varying the position of the rotation center and
minimising the measured change in phase. A 6-axis robot enables the required
rotations without the need of additional mechanical systems. By developing
software that enables synchronization between the robot control and the signal
readout, we enable automated calibration routines which will be the subject of
future work.

The same scan was then repeated with the horn rotated $None$ around the
$Z$-axis in order to obtain the cross-polarisation far-field characteristic of
the receiver horn. The addition of $None$ on top of the $None$ rotation on
$\phi$, directly controlled by the flange axis of the robot, was informed by
varying $\phi$ to minimize the cross-polarisation signal when both the
receiver and the transmitter are supposedly co-linear, thus excluding the co-
polarisation contribution to the measured cross-polarisation signal. As can be
seen in Figures 3b and 4, the measured co-polarization beam cut closely
matches the simulated beam down to the $40\text{\text{-}}\mathrm{dB}$ range,
barring some standing wave contributions visible at the sidelobes. The maximum
of the co-polarisation beam is a few degrees off-center. This, combined with
the slant of the phase distribution visible in Fig. 3a, suggests that these
result can be further improved with a better alignment. The cross-polarisation
measurement suggests that the dynamic range of the system is around
$70\text{\,}\mathrm{dB}$ (see Figures 3d and 4). In order to verify the
robustness of this result, 40 more identical measurements were performed. The
obtained 3$\sigma$ deviation margins are plotted as semi-transparent regions
for both co- and cross-polarisation in Figure 4. Their low value at several
points around the $-70\text{\,}\mathrm{dB}$ mark supports this evaluation of
the dynamic range.

Figure 4: Comparison of $None$ of elevation slices for the cross-polarisation
measurement and co-polarisation measurement and simulation. A 3$\sigma$
deviation envelope obtained from 40 identical measurements is plotted over the
experimental data. The simulated data has been obtained using a model of the
horn in CST MWS.[14] A rotation $None$ was added to $\phi$ in the process of
minimising the cross-polarisation response. The measured result matches well
with the simulated one, with notable discrepancies being due to standing waves
between the transmitter and the receiver and some degree of non-ideality of
alignment. The normalised cross-polarisation measurement averages at about
$-54\text{\,}\mathrm{dB}$, with some points going as low as
$-70\text{\,}\mathrm{dB}$. This suggests a comparable dynamic range of about
$-70\text{\,}\mathrm{dB}$ for this system.

###  3.2 Positional repeatability

Traditionally, the positional accuracy and repeatability of a 6-axis robot can
be evaluated using a laser tracker or a set of micrometre dial gauges.[15]
Since the robot is equipped with a phase-sensitive mm-wave receiver, we can
instead use the data that we obtain with the receiver to extract robot
positional information with high accuracy.

Generally, the relationship between the position of the receiver and the
measured phase of a wavefront $Ae^{i\theta}=Ae^{i(\textbf{kr}+\omega t)}$
propagating through free space can be expressed as:

$|\textbf{r}|=\frac{\theta}{|\textbf{k}|}=\frac{\theta}{k_{0}}=\frac{\theta
c}{2\pi f},$ (1)

where r is the spatial coordinate, k is the wave vector, $k_{0}$ is the
wavenumber in free space, $\theta$ is the phase and $f$ is the frequency. If
the receiver is positioned in the far field and is aligned with the
transmitter on the Z-axis, then the measured wavefront can be approximated as
a plane wave $Ae^{i(k_{z}z+\omega t)}$. As long as this is the case, the
position of the receiver can be found as:

$z=\frac{\theta}{k_{z}}=\frac{\theta c}{2\pi f}.$ (2)

The following discussion assumes the initial position of the robot to be at
$z$ = $0\text{\,}\mathrm{mm}$. By keeping track of phase information, we see
that positional errors stay well within one wavelength. We note that this
method does not offer a way to distinguish between the change of phase
stemming from a change in position and a change of phase stemming from unknown
sources.

In order to test the positional repeatability of the robot arm we have run a
series of linear scans along the Z-direction, repeating measurements at 80
locations linearly sampled along a $8\text{\text{-}}\mathrm{mm}$ span. These
measurements were repeated 200 times over a period of about 4 hours. Due to
the inertia of the robot arm, there is some initial vibration that the flange
experiences after reaching the programmed point. The amplitude of this
vibration is stated to be within $300\text{\,}\mathrm{\SIUnitSymbolMicro m}$
after $0.1\text{\,}\mathrm{s}$. To minimise its impact, a settling time of
$1.0\text{\,}\mathrm{s}$ has been set for the scan. When a settling time of
$0.5\text{\,}\mathrm{s}$ is used, the first 20 measurements need to be
discarded due to the robot arm having much lower positional accuracy while
warming up. This is consistent with statements made in the robot user manual.
Future work will look into optimization of the scan parameters to maximize
mapping speed.

Since the frequency is known, phase information obtained from these scans can
then be converted to an offset relative to the initial position. The absolute
positional accuracy has been calculated by converting phase data to positional
offsets after detrending the phase timestreams with a linear fit to minimize
the effect of the phase drift, a contribution to the phase that affects all
measurements and slowly changes over time, such as an ambient change in
temperature or humidity. The result of this is presented in Fig. 5a. The
relative positioning error was calculated as root mean square of these values.
Its values across coordinates are presented in Fig. 5b as well as shown in
Fig. 5a as semitransparent regions near the traces. If the phase at the first
point is assumed to correspond to $z=$0\text{\,}\mathrm{mm}$$, the absolute
positioning error for this particular case seems to be at most about
$40\text{\,}\mathrm{\SIUnitSymbolMicro m}$, with the positional repeatability
being around $4\text{\,}\mathrm{\SIUnitSymbolMicro m}$ on average. While this
falls well within the bounds of $200\text{\text{-}}\mathrm{\SIUnitSymbolMicro
m}$ absolute pose accuracy and $20\text{\text{-}}\mathrm{\SIUnitSymbolMicro
m}$ pose repeatability claimed on the KUKA robot datasheet[16], it only covers
a very narrow use case (single linear motion, extremely small steps) and does
not necessarily demonstrate that these values can be assumed for the entire
range of motion of the robot.

Figure 5: Position error as a function of coordinate for two directions of
movement measured at the highest and the lowest frequencies. a) Absolute
positional error with the semitransparent regions marking the $1\sigma$
standard deviation envelope. b) Positional repeatability as calculated by the
$1\sigma$ standard deviation from 100 samples at each of the 80 locations
samples along the $8\text{\text{-}}\mathrm{mm}$ range. Figure 6: Positional
repeatability of a scan over a $31\times 31$ point grid with a span of
$60\times$60\text{\,}\mathrm{cm}$$ at the lowest frequency of
$75\text{\,}\mathrm{GHz}$, calculated by the $1\sigma$ standard deviation from
50 samples at each point.

We also performed a test at $75\text{\,}\mathrm{GHz}$ with the robot scanning
through a $31\times 31$ point grid in the XY plane with a span of
$60\times$60\text{\,}\mathrm{cm}$$. Each scan lasted for 33 minutes and was
repeated 100 times for an overall measurement duration of approximately 55
hours. Since statistical errors that are not related to XYZ position errors,
including tip and tilt pointing errors, will contribute to the overall phase
error that is measured at each location, the following result represents an
upper bound on the relative error of position. The phase error calculated
across this grid is shown in Fig. 6. The maximum $1\sigma$ error is
approximately $None$, which suggests an upper limit of
$47\text{\,}\mathrm{\SIUnitSymbolMicro m}$ in relative position error. The
mean value across the array is $None$ which corresponds to about
$11.7\text{\,}\mathrm{\SIUnitSymbolMicro m}$. No phase drift correction was
implemented in generating these results and measurements were conducted in a
typical laboratory setting with multiple candidates for spurious reflections.

##  4 Conclusions and discussion

We have presented a phase-sensitive microwave measurement setup involving a
6-axis robot and demonstrated its capabilities by mapping the beam of a W-band
horn antenna. The preliminary results shown can be improved by stricter
alignment of the optical components and better control of the standing waves
in the system. This, as well as further improvements to the software through
better scanning strategies, automated calibration routines, optimised scanning
parameters and new post-processing options, will be explored in future
efforts.

An open-source control software with a graphical user interface which allows
for controlling the robot and synchronizing with the vector network analyzer
for data acquisition has been developed and made available in a public
repository. The software also supports typical data processing and
visualization options, including field propagation and data slicing.

Wide-angle far field measurements have been performed with the cross-
polarisation results demonstrating $70\text{\,}\mathrm{dB}$ of accessible
dynamic range in the context of our laboratory setup. Taking
$350\text{\,}\mathrm{G}\mathrm{H}\mathrm{z}$ as a reference - the higher limit
of a frequency band of high interest for CMB observations, as a reference [1]
\- the positional accuracy has an upper limit at
$45\text{\,}\mathrm{\SIUnitSymbolMicro m}$, or 6% wavelength, whilst the
positional repeatability sits within $10\text{\,}\mathrm{\SIUnitSymbolMicro
m}$, or 1% wavelength.

Relying on the high accuracy, repeatability and versatility the 6-axis robot
arm offers, the holography measurement bed discussed in this work presents an
attractive alternative to a setup relying on traditional stage. This scanner
can carry precise beam holography of optical components for upcoming CMB
instruments.

###### Acknowledgements.

Funded by the European Union (ERC, CMBeam, 101040169). Views and opinions
expressed are however those of the author(s) only and do not necessarily
reflect those of the European Union or the European Research Council Executive
Agency. Neither the European Union nor the granting authority can be held
responsible for them. We acknowledge support from The Icelandic Research Fund
(Grant number: 2410656-051), the Swedish Research Council (Reg. no.
2019-03959), and the Swedish National Space Agency (SNSA/Rymdstyrelsen).

## References

  * [1] Abitbol, M. H., Ahmed, Z., Barron, D., Basu Thakur, R., Bender, A. N., Benson, B. A., Bischoff, C. A., Bryan, S. A., Carlstrom, J. E., Chang, C. L., Chuss, D. T., Crowley, K. T., Cukierman, A., de Haan, T., Dobbs, M., Essinger-Hileman, T., Filippini, J. P., Ganga, K., Gudmundsson, J. E., Halverson, N. W., Hanany, S., Henderson, S. W., Hill, C. A., Ho, S.-P. P., Hubmayr, J., Irwin, K., Jeong, O., Johnson, B. R., Kernasovskiy, S. A., Kovac, J. M., Kusaka, A., Lee, A. T., Maria, S., Mauskopf, P., McMahon, J. J., Moncelsi, L., Nadolski, A. W., Nagy, J. M., Niemack, M. D., O’Brient, R. C., Padin, S., Parshley, S. C., Pryke, C., Roe, N. A., Rostem, K., Ruhl, J., Simon, S. M., Staggs, S. T., Suzuki, A., Switzer, E. R., Tajima, O., Thompson, K. L., Timbie, P., Tucker, G. S., Vieira, J. D., Vieregg, A. G., Westbrook, B., Wollack, E. J., Yoon, K. W., Young, K. S., and Young, E. Y., “CMB-S4 Technology Book, First Edition,” arXiv e-prints , arXiv:1706.02464 (June 2017).
  * [2] Kamionkowski, M. and Kovetz, E. D., “The Quest for B Modes from Inflationary Gravitational Waves,” Annual Review of Astronomy and Astrophysics 54(Volume 54, 2016), 227–269 (2016).
  * [3] Hanson, D., Lewis, A., and Challinor, A., “Asymmetric beams and CMB statistical anisotropy,” Physical Review D 81, 103003 (May 2010).
  * [4] Chesmore, G. E., Harrington, K., Sierra, C. E., Gallardo, P. A., Sutariya, S., Alford, T., Adler, A. E., Bhandarkar, T., Coppi, G., Dachlythra, N., Golec, J., Gudmundsson, J., Haridas, S. K., Johnson, B. R., Kofman, A. M., Iuliano, J., McMahon, J., Niemack, M. D., Orlowski-Scherer, J., Sarmiento, K. P., Puddu, R., Silva-Feaver, M., Simon, S. M., Robe, J., Wollack, E. J., and Xu, Z., “Simons Observatory: characterizing the Large Aperture Telescope Receiver with radio holography,” Appl. Opt. 61, 10309–10319 (Dec 2022).
  * [5] Nakano, R., Takakura, H., Sekimoto, Y., Inatani, J., Sugimoto, M., Oguri, S., and Matsuda, F., “Holographic phase-retrieval method of near-field antenna pattern measurement for bolometer-array-equipped millimeter-wave telescopes,” Journal of Astronomical Telescopes, Instruments, and Systems 9(2), 028003 (2023).
  * [6] Takakura, H., Sekimoto, Y., Inatani, J., Kashima, S., Sugimoto, M., Nakano, R., and Nagata, R., “Wide-field polarization angle measurements of a LiteBIRD low-frequency telescope scaled antenna,” Journal of Astronomical Telescopes, Instruments, and Systems 9(2), 024003 (2023).
  * [7] Novotny, D. R., Gordon, J. A., Allman, M. S., Guerrieri, J. R., and Curtin, A. E., “Three antenna ranges based on articulated robotic arms at the national institute of standards and technology: Usability for over-the-air and standard near-field measurements,” in [2017 IEEE Conference on Antenna Measurements & Applications (CAMA) ], 1–4 (2017).
  * [8] Matos, C., Li, J., and Ghalichechian, N., “Robotically Controlled Pattern Measurements of 60 GHz Phased Array Antenna,” in [2019 Antenna Measurement Techniques Association Symposium (AMTA) ], 1–2 (2019).
  * [9] Boehm, L., Boegelsack, F., Hitzler, M., and Waldschmidt, C., “Enhancements in mm-wave antenna measurements: automatic alignment and achievable accuracy,” IET Microwaves, Antennas & Propagation 11(12), 1676–1680 (2017).
  * [10] Gascard, T., Pisano, G., Doyle, S., Thompson, J., Shitvov, A., Austermann, J., Beall, J., Hubmayr, J., Raymond, B., Halverson, N., Jaehnig, G., McKenney, C. M., and Suzuki, A., “Experimental characterization of a planar phase-engineered metamaterial lenslet for millimeter astronomy,” Appl. Opt. 62, 2906–2916 (Apr 2023).
  * [11] “RoboDK.”  v5.6.8, RoboDK Inc.
  * [12] Harris, C. R., Millman, K. J., van der Walt, S. J., Gommers, R., Virtanen, P., Cournapeau, D., Wieser, E., Taylor, J., Berg, S., Smith, N. J., Kern, R., Picus, M., Hoyer, S., van Kerkwijk, M. H., Brett, M., Haldane, A., del Río, J. F., Wiebe, M., Peterson, P., Gérard-Marchant, P., Sheppard, K., Reddy, T., Weckesser, W., Abbasi, H., Gohlke, C., and Oliphant, T. E., “Array programming with NumPy,” Nature 585, 357–362 (Sept. 2020).
  * [13] Ludwig, A., “The definition of cross polarization,” IEEE Transactions on Antennas and Propagation 21(1), 116–119 (1973).
  * [14] “CST Studio Suite 2023.”  v2023.05,  Dassault Systemes Deutschland GmbH.
  * [15] Novotny, D., Gordon, J., Coder, J., Francis, M., and Guerrieri, J. R., “Performance evaluation of a robotically controlled millimeter-wave near-field pattern range at the nist,” The 7th European Conference on Antennas and Propagation , GOTHENBURG, SE (2013-04-07 04:04:00 2013).
  * [16] KUKA KR 6 R900-2 datasheet.


# On the order of Erdős-Rogers functions

###### Abstract

For an integer $n\geq 1$, the Erdős-Rogers function $f_{s}(n)$ is the maximum
integer $m$ such that every $n$-vertex $K_{s+1}$-free graph has a $K_{s}$-free
subgraph with $m$ vertices. It is known that for all $s\geq 3$,
$f_{s}(n)=\Omega(\sqrt{n\log n}/\log\log n)$ as $n\rightarrow\infty$. In this
paper, we show that for all $s\geq 3$,

$f_{s}(n)=O(\sqrt{n}\,\log n).$

This improves previous bounds of order $\sqrt{n}(\log n)^{2(s+1)^{2}}$ by
Dudek, Retter and Rödl.

##  1 Introduction

For an integer $s\geq 2$, the Erdős-Rogers function $f_{s}(n)$ is the maximum
integer $m$ such that every $n$-vertex $K_{s+1}$-free graph has a $K_{s}$-free
subgraph with $m$ vertices. The determination of $f_{2}(n)$ is almost
equivalent to determining the triangle-complete graph Ramsey numbers, since
$r(3,f_{2}(n))\leq n<r(3,f_{2}(n)+1)$. These quantities $r(3,t)$ are known to
within a constant factor [1, 4, 7, 11, 18], and from this one deduces
$f_{2}(n)$ has order of magnitude $\sqrt{n\log n}$ as $n\rightarrow\infty$. As
observed by Dudek and the first author, the arguments for lower bounds for
$f_{2}(n)$ generalize to $f_{s}(n)$ for $s\geq 3$. Shearer [19] showed that
any $n$-vertex $K_{s+1}$-free graph of maximum degree $d$ has an independent
set of size $\Omega((n\log d)/(d\log\log d))$, and the neighborhood of a
vertex of degree $d$ is a $K_{s}$-free induced subgraph. Therefore for all
$s\geq 3$,

$f_{s}(n)=\Omega\Bigl{(}\frac{\sqrt{n\log n}}{\log\log n}\Bigr{)}.$ (1)

Wolfovits [21] proved $f_{3}(n)=O(\sqrt{n}(\log n)^{120})$, and it was shown
by Dudek, Retter, Rödl [6] that $f_{3}(n)=O(\sqrt{n}\,(\log n)^{32})$ and more
generally that $f_{s}(n)=O(\sqrt{n}\,(\log n)^{2(s+1)^{2}})$. In this short
paper, we significantly improve these bounds on the Erdős-Rogers functions
$f_{s}(n)$ as follows:

######  Theorem 1.

For each fixed $s\geq 3$,

$f_{s}(n)\;\;=\;\;O(\sqrt{n}\,\log n).$ (2)

The proof of Theorem 1 involves a combination of the ideas of Wolfovits [21]
and Dudek, Retter, Rödl [6] with the construction of Mattheus and the second
author [14], but does not make use of the method of containers as in [14] or
[10]. We did not expend too much effort in optimizing the implicit constant in
the bound on $f_{s}(n)$ in Theorem 1; from the proof one may obtain
$f_{s}(n)\leq 2^{100s}\sqrt{n}\log n$ for $n\geq 2$, which shows
$f_{s}(n)=n^{1/2+o(1)}$ for $s=o(\log n)$.

Notation. For a graph $G$, we write $V(G)$ for the vertex set of $G$ and
$E(G)$ for the edge set of $G$. For a set $X\subseteq V(G)$, let $G[X]$ denote
the subgraph of $G$ induced by $X$, namely the graph with vertex set $X$ and
edge set $\\{e\in E(G):e\subseteq X\\}$.

##  2 Tools from probability

We refer to the book by Alon and Spencer [2] for a reference on probabilistic
methods in combinatorics. The first result we need is the Chernoff Bound (see
Alon and Spencer [2]) for concentration of binomial random variables.

######  Proposition 1.

(Chernoff Bound) Let $Z$ be a binomial random variable with mean $\mu$. Then
for any real $\epsilon\in[0,1]$,

$\displaystyle\begin{split}\Pr(Z>(1+\epsilon)\mu)&\leq\exp\Bigl{(}-\frac{\epsilon^{2}\mu}{4}\Bigr{)}\quad\quad\mbox{\rm
and }\\\
\Pr(Z<(1-\epsilon)\mu)&\leq\exp\Bigl{(}-\frac{\epsilon^{2}\mu}{2}\Bigr{)}\end{split}$
(3)

The next proposition is derived from Janson’s inequality [2, 9]. Let $\chi$ be
a coloring of an $n$-element set $Y$ with $s$ colors, with color classes
$Y_{1},Y_{2},\dots,Y_{s}$. Then the random $s$-partite graph
$G_{n,\rho}(\chi)$ samples edges independently with probability $\rho$ from
the complete multipartite graph with parts $Y_{1},Y_{2},\dots,Y_{s}$. The
following technical proposition is derived in a standard way from Janson’s
inequality [2, 9], and we give a proof in the appendix:

######  Proposition 2.

(via Janson’s inequality) Let $s\geq 3$, $n\geq 2^{40s}$ and
$\rho=(8s/n)^{2/s}$, and let $\chi$ be an $s$-coloring of an $n$-element set
whose color classes have size at least $n/2s$ each. Then

$\Pr(K_{s}\not\subseteq G_{n,\rho}(\chi))\leq\exp(-2^{2s-4}n).$ (4)

We shall finally require the Lovász local lemma [2, 13] in the following form.
We write $\overline{A}$ for the complement of an event $A$ in a probability
space.

######  Proposition 3.

(Lovász local lemma) Let $A_{1},A_{2},\dots,A_{n}$ be events in some
probability space and suppose that for some set
$J_{i}\subset\\{1,2,\dots,n\\}$, $A_{i}$ is mutually independent of
$\\{A_{j}:j\not\in J_{i}\cup\\{i\\}\\}$. If there exist real numbers
$\gamma_{i}\in[0,1)$ such that

$\Pr(A_{i})\leq\gamma_{i}\prod_{j\in J_{i}}(1-\gamma_{j}),$ (5)

then

$\Pr\Bigl{(}\bigcap_{i=1}^{n}\overline{A_{i}}\Bigr{)}>0.$

##  3 Hermitian unitals and O’Nan configurations

The proof of Theorem 1 appeals to a construction from projective geometry. We
briefly describe the geometry here and the tools from probabilistic
combinatorics that we use. Further geometric background is given in Barwick
and Ebert [3], Brouwer and van Maldeghem [5] and Piper [17].

###  3.1 Hermitian unitals in brief

For a partial linear space $\mathcal{H}$, we let $P(\mathcal{H})$ denote the
set of points of $\mathcal{H}$ and $L(\mathcal{H})$ denote the set of lines of
$\mathcal{H}$. A unital in the projective plane $\mathrm{PG}(2,q^{2})$ is a
set $\mathcal{U}$ of $q^{3}+1$ points such that every line of
$\mathrm{PG}(2,q^{2})$ intersects $\mathcal{U}$ in $1$ or $q+1$ points – the
latter are referred to as secants. A classical or Hermitian unital
$\mathcal{H}_{q}$ is a partial linear space described in homogeneous co-
ordinates as the following set of one-dimensional subspaces of
$\mathbb{F}_{q^{2}}^{3}$:

$P(\mathcal{H}_{q})=\\{\left<x,y,z\right>\subset\mathbb{F}_{q^{2}}^{3}:x^{q+1}+y^{q+1}+z^{q+1}=0\\}.$

Here arithmetic is in the finite field $\mathbb{F}_{q^{2}}$, and
$\left<x,y,z\right>$ is the one-dimensional subspace of
$\mathbb{F}_{q^{2}}^{3}$ generated by $(x,y,z)$. Then $L(\mathcal{H}_{q})$
consists of the intersections of secant lines with $P(\mathcal{H}_{q})$, so
that there are $q^{2}(q^{2}-q+1)$ lines in $\mathcal{H}_{q}$, each containing
exactly $q+1$ points of $\mathcal{H}_{q}$.

###  3.2 O’Nan configurations and fans

One of the remarkable features of the Hermitian unital is that it does not
contain the so-called O’Nan configuration, namely the configuration of four
lines and six points in the left figure below:

O’Nan configuration and $s$-fan

######  Definition 1.

($\boldsymbol{s}$-fan) For $s\geq 3$, an $s$-fan is a set of $s$ pairwise
intersecting lines such that $s-1$ of the lines are concurrent with a point
whereas the remaining line is not concurrent with that point. For $s\geq 4$,
the unique point contained in $s-1$ lines is the point of concurrency of the
$s$-fan.

An illustration of an $s$-fan is shown in the right figure above. The fact
that $\mathcal{H}_{q}$ does not contain the figure on the left was first
proved by O’Nan [16] (see Mattheus and the second author for a short linear-
algebraic proof [14]). The following lemma is a straightforward consequence:

######  Lemma 1.

If $s\geq 3$ lines in $\mathcal{H}_{q}$ pairwise cross, then they are
concurrent with some point of $\mathcal{H}_{q}$ or they form an $s$-fan.

###### Proof.

Let $K\subseteq L(\mathcal{H}_{q})$ be a configuration of $s$ pairwise
crossing lines. In the case $s=3$, if the lines are not all concurrent with
some point, then they form a triangle, with is an $s$-fan. The case $s=4$
follows from the fact that $\mathcal{H}_{q}$ contains no O’Nan configuration.
If $s>4$, then at least three of the lines $\ell_{1},\ell_{2},\ell_{3}\in K$
are concurrent with some point $p\in\mathcal{H}_{q}$. Suppose for a
contradiction that two of the lines $\ell_{4},\ell_{5}\in K$ are not
concurrent with $p$. Then three of $\ell_{1},\ell_{2},\ell_{4},\ell_{5}$ are
concurrent with some $p^{\prime}\in P(\mathcal{H}_{q})\backslash\\{p\\}$. This
implies $\ell_{1},\ell_{2},\ell_{3},\ell_{4},\ell_{5}$ are concurrent with
$p^{\prime}$, contradicting that $\ell_{4},\ell_{5}$ are concurrent with $p$.
∎

##  4 Random sampling

To prove Theorem 1, we require for $s\geq 3$ an $n$-vertex $K_{s+1}$-free
graph $H$ such that every induced subgraph of $H$ with subtantially more than
about $\sqrt{n}\log n$ vertices contains a copy of $K_{s}$. The overview of
the construction of $H$ is as follows, where asymptotic notation is with
respect to a growing prime power $q$.

First we randomly sample points from the Hermitian unital $\mathcal{H}_{q}$
with probability roughly $\Theta(\log q/(q+1))$ for to obtain a partial linear
space $\mathcal{H}$. We show in Section 4.1 via the Chernoff bound,
Proposition 1, that with positive probability,
$|P(\mathcal{H})|=\Theta(q^{2}\log q)$, $|L(\mathcal{H})|=q^{2}(q^{2}-q+1)$,
each line in $L(\mathcal{H})$ has size $\Theta(\log q)$, and the number of
$(s+1)$-fans containing any given pair of intersecting lines in $\mathcal{H}$
is $\Theta(\log q)^{s}$.

We define the intersection graph $G$ whose vertex set is $L(\mathcal{H})$ and
whose edges are pairs of intersecting lines of $\mathcal{H}$. The graph $G$
has $q^{2}(q^{2}-q+1)$ vertices and every edge of $G$ is contained in
$\Theta(\log q)^{s}$ copies of $K_{s+1}$ in $G$. Most importantly,

the vertex set of each $K_{s+1}\subseteq G$ is either an $(s+1)$-fan in
$\mathcal{H}$ or is a set of lines of $\mathcal{H}$ all concurrent with some
point in $\mathcal{H}$. (A)

We eliminate the copies of $K_{s+1}\subseteq G$ corresponding to $s+1$ lines
of $\mathcal{H}$ concurrent with a point $p$ of $\mathcal{H}$ by randomly
$s$-coloring the set $\mathcal{H}_{p}$ of lines concurrent with $p$,
independently over different points of $\mathcal{H}$, and retaining only those
edges $\\{\ell,\ell^{\prime}\\}$ of $G$ such that $\ell$ and $\ell^{\prime}$
have different colors in the coloring of $\mathcal{H}_{p}$ where
$p=\ell\cap\ell^{\prime}$. By (A), this graph $G_{\chi}$ has the following
property:

the vertex set of each $K_{s+1}\subseteq G_{\chi}$ is an $(s+1)$-fan. (B)

We eliminate the copies of $K_{s+1}$ in $G$ which correspond to $(s+1)$-fans
in $\mathcal{H}$ by randomly sampling edges of $G$ independently with suitable
probability $\rho=\Theta(\log q)^{-2/s}$ to obtain a random graph
$G_{\rho}\subseteq G$. Let $H$ be the intersection of $G_{\rho}$ and
$G_{\chi}$, that is, $V(H)=V(G)$ and $E(H)=E(G_{\rho})\cap E(G_{\chi})$. We
apply the Lovász local lemma (Proposition 3) in Section 5 to show that with
positive probability, the graph $H$ is $K_{s+1}$-free and, for a constant $C$
depending only on $s$, every set of $Cq^{2}\log q$ vertices of $H$ induces a
subgraph of $H$ containing $K_{s}$. Then $|V(H)|=n=q^{2}(q^{2}-q+1)$ and so
$f_{s}(n)\leq Cq^{2}\log q$. The distribution of primes $q$ allows us to
deduce $f_{s}(n)=O(\sqrt{n}\log n)$ for all $n$.

###  4.1 Randomly sampling points

The first step in our construction is to randomly sample points from
$\mathcal{H}_{q}$ to obtain a partial linear space $\mathcal{H}$ with the
properties listed below, which essentially uses only the Chernoff Bound,
Proposition 1.

######  Lemma 2.

For any integers $s\geq 3$ and $a\geq 128$ and any prime power $q\geq a\log
q$, there exists a partial linear space $\mathcal{H}=\mathcal{H}_{a,q,s}$ such
that

(i) |  The line set $L$ of $\mathcal{H}$ has size $q^{2}(q^{2}-q+1)$.
---|---
(ii) |  The point set $P$ of $\mathcal{H}$ has size at most $2aq^{2}\log q$ and at least $a(q^{2}\log q)/2$.
(iii) |  Each line of $\mathcal{H}$ has at least $(a\log q)/2$ points.
(iv) |  The number of $(s+1)$-fans in $\mathcal{H}$ containing a pair of lines in $L$ is at most $k=(2a\log q)^{s}$.
(v) |  Every $s+1$ pairwise intersecting lines in $\mathcal{H}$ is concurrent with a point or is an $(s+1)$-fan.

###### Proof.

Sample points of $\mathcal{H}_{q}$ randomly and independently with probability
$(a\log q)/(q+1)$ and let $\mathcal{H}$ be the partial linear space whose
point set is the set $P$ of sampled points and whose line set is
$L=\\{\ell\cap P:\ell\in L(\mathcal{H}_{q})\\}$. Since we are sampling points,
$|L(\mathcal{H}_{q})|=|L|$ and so (i) holds, and (v) follows from Lemma 1.

By the Chernoff bound (Proposition 1) with $\epsilon=1/2$, the probability
that $|P|$ is larger than $2aq^{2}\log q$ or less than $(aq^{2}\log q)/2$ is
at most $2\exp(-(aq^{2}\log q)/16)<1/3$, and the number of sampled points on a
given line $\ell\in L(\mathcal{H}_{q})$ is at most $(a\log q)/2$ with
probability at most $\exp(-(a\log q)/8)=q^{-a/8}<q^{-8}$. Since
$|L(\mathcal{H}_{q})|\leq q^{4}<q^{8}/3$, the probability that (iii) fails is
less than 1/3.

If the number of $(s+1)$-fans on some pair of lines $\ell$ and $\ell^{\prime}$
is more than $k$, then we claim some line had more than $2a\log q$ points
sampled on it. This happens with probability at most $\exp(-(a\log
q)/4)<q^{-8}$ by the Chernoff Bound (Proposition 1) with $\epsilon=1$. Since
the number of pairs of intersecting lines in $\mathcal{H}_{q}$ is at most
$(q^{3}+1)\cdot{q^{2}\choose 2}\leq q^{8}/3$, (iv) then fails with probability
less than 1/3. We then conclude (ii) – (iv) hold simultaneously with positive
probability.

To prove the claim, fix distinct lines $\ell$ and $\ell^{\prime}$ in
$\mathcal{H}_{q}$. For each $(s+1)$-fan in $\mathcal{H}$ containing $\ell$ and
$\ell^{\prime}$, either $\\{p\\}=\ell\cap\ell^{\prime}$ is the point of
concurrency or some other point of $\ell\cup\ell^{\prime}\backslash\\{p\\}$ is
the point of concurrency. If $p$ is the point of concurrency, then we must
pick a point on $\ell$ and a point in $\ell^{\prime}$ to define a line
$\ell^{\prime\prime}$ through the remaining points of the $(s+1)$-fan. There
are at most $(2a\log q)^{2}$ choices for those two points, and then since
$\ell^{\prime\prime}$ has at most $2a\log q$ points sampled, there are at most
$(2a\log q)^{s-2}$ choices for the remaining $s-2$ points of the $(s+1)$-fan.
If $p$ is not the point of concurrency, then the point of concurrency is
picked from $\ell\cup\ell^{\prime}\backslash\\{p\\}$ in at most $2(2a\log q)$
ways. Then we must pick the remaining $s-1$ points of the $(s+1)$-fan from
$\ell$ or from $\ell^{\prime}$, in at most $2(2a\log q)^{s-1}$ ways. So the
number of $(s+1)$-fans containing $\ell$ and $\ell^{\prime}$ is at most
$4(2a\log q)^{s}\leq(2a\log q)^{s}=k$. ∎

For a point $p\in P$ and a set $X\subseteq L$, let $X_{p}$ denote the set of
lines $X$ concurrent with the point $p$. It is convenient for a positive
integer $b$ and $X\subseteq L$ to define

$P_{X}=P_{X,b}=\\{p\in P:|X_{p}|\geq b\\}.$

######  Lemma 3.

Let $b\geq 1$, $a\geq 128$ and $q\geq a\log q$. Then for any $X\subseteq L$,

$\sum_{p\in P_{X}}|X_{p}|>\frac{1}{2}(a\log q)\cdot|X|-2abq^{2}\log q.$ (6)

###### Proof.

As $|P|\leq 2aq^{2}\log q$ from Lemma 2.ii,

$\sum_{p\in P\backslash P_{X}}|X_{p}|<b|P|\leq 2abq^{2}\log q.$

Each line in $X$ is incident with at least $(a\log q)/2$ points by Lemma
2.iii. Therefore

$\sum_{p\in P}|X_{p}|=\sum_{\ell\in X}|\ell\cap P|\geq\frac{1}{2}(a\log
q)\cdot|X|.$

Subtracting the first inequality from the second gives the lemma. ∎

###  4.2 Random sampling of pairs of lines

We use the partial linear space $\mathcal{H}=\mathcal{H}_{a,q,s}$ in Lemma 2
for $a\geq 128$ and $q\geq a\log q$ to construct the intersection graph
$G=G_{a,q,s}$ of lines in $\mathcal{H}$ as follows: the vertex set of $G$ is
$L$ and the edge set is
$\\{\\{\ell,\ell^{\prime}\\}:\ell\cap\ell^{\prime}\neq\emptyset\\}$. We use
the words line and vertex interchangeably to refer to the vertices of $G$.
From Lemma 2, for each prime power $q\geq a\log q$, the graph $G$ has
$|L|=q^{2}(q^{2}-q+1)$ vertices, and most importantly, for $s\geq 3$,

the vertex set of each $K_{s+1}\subseteq G$ is either an $(s+1)$-fan in
$\mathcal{H}$ or is a set of lines of $\mathcal{H}$ all concurrent with some
point in $\mathcal{H}$. (A)

For each point $p\in P$, the set of lines concurrent with $p$ induces a clique
of size $q^{2}$ in $G$, and any two of these cliques are edge-disjoint. Fixing
a set $X\subseteq L$ and a point $p\in P$, recall $X_{p}\subseteq X$ is the
set of lines in $X$ concurrent with $p$, and in particular for
$X_{p}\neq\emptyset$ the subgraphs $G[X_{p}]$ are edge-disjoint cliques for
$p\in P$.

Then let $G_{\chi}\subseteq G$ be obtained from $G$ by taking independently
for each $p\in P$ a random vertex-coloring $\chi_{p}$ of all the lines in $G$
concurrent with $p$ and removing all edges of $G$ whose ends have the same
color. This removes from $G$ all copies of $K_{s+1}$ induced by $s+1$ lines
concurrent with a single point. We conclude by (A), for $s\geq 3$:

the vertex set of each $K_{s+1}\subseteq G_{\chi}$ is an $(s+1)$-fan. (B)

We now define the random graph $G_{\rho}\subseteq G$. Let $b\geq 1$ and
$\rho\in[0,1]$ satisfy $b\geq 2^{40s}$ and $\rho=(8s/b)^{2/s}$, and define
$G_{\rho}$ to be the random graph obtained by sampling edges of $G$
independently with probability $\rho$. We let $H$ be the intersection of
$G_{\rho}$ and $G_{\chi}$, namely, the graph with vertex set $V(G)$ and edge
set $E(G_{\rho})\cap E(G_{\chi})$. Our next task is to consider copies of
$K_{s}\subseteq H$ whose vertices are contained in some set of lines
concurrent with a single point. Unsurprisingly, this makes strong use of
Janson’s inequality for the probability that a random $s$-partite graph is
$K_{s}$-free, in the form of Proposition 2.

###  4.3 The event $A_{X}$

In this section, for each set $X$ of lines, we define an event $A_{X}$ whose
non-occurrance implies $H[X]$ contains a copy of $K_{s}$, and we find an upper
bound on $\Pr(A_{X})$. For a set $X\subseteq L$ and a point $p\in P_{X}$, fix
a family $\Pi_{p}(X)=\Pi_{p}$ of $r_{p}(X)=\lfloor|X_{p}|/b\rfloor$ disjoint
subsets of $X_{p}$ of size $b$ each. Then $X_{p}$ is bad if for $Y\in\Pi_{p}$,
none of $H[Y]$ contains a $K_{s}$, and we let $A_{X,p}$ be the event that
$X_{p}$ is bad. We say $X$ is bad if all $X_{p}:p\in P_{X}$ are bad. In other
words, if $A_{X}$ is the event that $X$ is bad, then

$A_{X}=\bigcap_{p\in P_{X}}A_{X,p}.$

If $A_{X}$ does not occur, then by definition $H[X]$ contains a copy of
$K_{s}$.

######  Lemma 4.

Let $s\geq 3$, $b\geq 2^{40s}$ and $\rho\in[0,1]$ satisfy $\rho=(8s/b)^{2/s}$.
Then for any $X\subseteq L$,

$\Pr(A_{X})\leq\exp\Bigl{(}-\frac{1}{32s}\sum_{p\in P_{X}}|X_{p}|\Bigr{)}.$
(7)

###### Proof.

Since the colorings $\chi_{p}$ are independent over $p\in P_{X}$, the events
$A_{X,p}$ are independent over $p\in P_{X}$. For $Y\in\Pi_{p}=\Pi_{p}(X)$, the
events $A_{Y}$ that $H[Y]$ does not contain $K_{s}$ are independent. By the
Chernoff bound (Proposition 1), the probability that $\chi_{p}$ assigns some
color fewer than $b/2s$ times to vertices of $Y$ is at most $\exp(-b/8s)$. Fix
a coloring $\chi$ of $Y$ where every color appears at least $b/2s$ times. Then
the graph $H[Y]$ is a random $s$-partite graph which we denoted in Section 2
by $G_{b,\rho}(\chi)$. By Proposition 2, for any such coloring $\chi$,

$\Pr(K_{s}\not\subseteq G_{b,\rho}(\chi))\leq\exp(-2^{2s-4}b).$

As there are at most $s^{b}$ choices of $\chi$, the union bound over
$s$-colorings $\chi$ gives

$\Pr(A_{Y})\leq\exp\Bigl{(}-\frac{b}{8s}\Bigr{)}+s^{b}\exp(-2^{2s-4}b).$

Since $s\geq 3$, $2^{2s-4}b\geq 2b\log s\geq 2b$ and therefore

$\Pr(A_{Y})\leq\exp\Bigl{(}-\frac{b}{8s}\Bigr{)}+\exp(-b)\leq
2\exp\Bigl{(}-\frac{b}{8s}\Bigr{)}\leq\exp\Bigl{(}-\frac{b}{16s}\Bigr{)}.$

Here we used $b\geq 16s$. Since $|\Pi_{p}|=r_{p}(X)$, we obtain

$\displaystyle\Pr(A_{X})$ $\displaystyle=$ $\displaystyle\prod_{p\in
P_{X}}\Pr(A_{X,p})$ $\displaystyle=$ $\displaystyle\prod_{p\in
P_{X}}\prod_{Y\in\Pi_{p}}\Pr(A_{Y})\;\;\leq\;\;\prod_{p\in
P_{X}}\exp\Bigl{(}-\frac{b}{16s}\cdot r_{p}(X)\Bigr{)}.$

Recall $|X_{p}|\geq b$ for $p\in P_{X}$, so $b\cdot r_{p}(X)\geq|X_{p}|/2$,
and therefore

$\Pr(A_{X})\leq\prod_{p\in
P_{X}}\exp\Bigl{(}-\frac{|X_{p}|}{32s}\Bigr{)}=\exp\Bigl{(}-\frac{1}{32s}\sum_{p\in
P_{X}}|X_{p}|\Bigr{)}.$

This proves the lemma. ∎

##  5 Proof of Theorem 1

To prove Theorem 1, for each $s\geq 3$ let $G=G_{a,q,s}$ be the intersection
graph defined in Section 4.2, where $a=2^{10}s$ and $q$ is a prime power
satisfying $q\geq a\log q$. Let $H\subseteq G$ denote the random graph defined
in Section 4.2, which is the intersection of the two random graphs $G_{\chi}$
and $G_{\rho}$, with parameters

$b=2^{40s}\cdot 2a\log q\qquad\mbox{ and
}\qquad\rho=\Bigl{(}\frac{8s}{b}\Bigr{)}^{\frac{2}{s}}.$

For convenience we omit rounding and assume $b$ is an integer. Let
$\mathcal{K}$ be the family of sets of $s+1$ lines $K\subseteq L$ forming an
$(s+1)$-fan in $G$, so $G[K]$ is a complete graph of order $s+1$, and let
$A_{K}$ be the event $G[K]\subseteq G_{\rho}$. Let $\mathcal{X}=\\{X\subseteq
L:|X|=8bq^{2}\\}$ and $A_{X}$ be the event $X$ is bad, as in Section 4.3. Due
to (B),

if none of the events $A_{K}:K\in\mathcal{K}$ or $A_{X}:X\in\mathcal{X}$
occur, then $H$ is $K_{s+1}$-free and $K_{s}\subseteq H[X]$ for all
$X\in\mathcal{X}$. (C)

Specifically, (C) implies every set of $8bq^{2}$ vertices of $H$ induces a
subgraph containing $K_{s}$. This shows for any prime power $q\geq a\log q$,

$f_{s}(q^{2}(q^{2}-q+1))\leq 8bq^{2}.$

By Bertrand’s postulate, there exists a prime between any positive integer and
its double, so letting $q\geq a\log q$ be a prime between $n^{1/4}$ and
$2n^{1/4}$, we find for $s\geq 3$ and $n\geq 2$,

$\displaystyle f_{s}(n)$ $\displaystyle\leq$ $\displaystyle 8bq^{2}\leq 8\cdot
2^{40s}\cdot 2^{11}s\cdot q^{2}\cdot\log q$ $\displaystyle\leq$ $\displaystyle
2^{100s}\cdot\sqrt{n}\log n.$

It remains to prove (C) holds with positive probability, via the local lemma
(Proposition 3).

Dependencies. For the dependencies between the events $A_{K}:K\in\mathcal{K}$
and $A_{X}:X\in\mathcal{X}$, we note $A_{X}$ is determined by the following
set of edges of $G$:

$\hat{E}(X)=\bigcup_{p\in P_{X}}\bigcup_{Y\in\Pi_{p}}E(G[Y]).$

Since $|Y|=b$ for each $Y\in\Pi_{p}$, and
$r=r_{p}(X)=|\Pi_{p}|=\lfloor|X_{p}|/b\rfloor$,

$\displaystyle|\hat{E}(X)|$ $\displaystyle=$ $\displaystyle\sum_{p\in
P_{X}}\sum_{i=1}^{r}{b\choose 2}$ (8) $\displaystyle=$
$\displaystyle\sum_{p\in
P_{X}}\Big{\lfloor}\frac{|X_{p}|}{b}\Big{\rfloor}{b\choose
2}\;\;\leq\;\;\frac{1}{2}b\sum_{p\in P_{X}}|X_{p}|.$

For convenience, let $\hat{E}(K)$ also denote $E(G[K])$ if $K\in\mathcal{K}$.
It is important here that since $G_{\rho}$ samples edges of $G$ independently
with probability $\rho$, for any $\mathcal{J}\subseteq\mathcal{K}$ and
$K\in\mathcal{K}$, we observe

the event $A_{K}$ is mutually independent with
$\\{A_{K^{\prime}}:K^{\prime}\in\mathcal{J}\\}$ if
$\bigcup_{K^{\prime}\in\mathcal{J}}E(K^{\prime})\cap E(K)=\emptyset.$

Let $k=(2a\log q)^{s}$. By Lemma 2.iv, each edge of $G$ is contained in at
most $k$ cliques $K\in\mathcal{K}$. Fixing any $K\in\mathcal{K}$, there are at
most

$\kappa={s+1\choose 2}\cdot k\leq bk$ (9)

choices of $K^{\prime}\in\mathcal{K}$ such that
$\hat{E}(K^{\prime})\cap\hat{E}(K)\neq\emptyset$, and any other set of events
$A_{K^{\prime}}$ are mutually independent with $A_{K}$ by the observation
above. We assume all $A_{X}$ are mutually dependent with any given event
$A_{K}$.

Since each edge of $G$ is in at most $k$ cliques in $\mathcal{K}$, by (8), for
each $X\in\mathcal{X}$ there are at most

$\displaystyle\lambda$ $\displaystyle=$ $\displaystyle k\cdot|\hat{E}(X)|$
(10) $\displaystyle\leq$ $\displaystyle\frac{1}{2}bk\cdot\sum_{p\in
P_{X}}|X_{p}|$

choices of $K\in\mathcal{K}$ such that
$\hat{E}(K)\cap\hat{E}(X)\neq\emptyset$, and any set of other events $A_{K}$
are mutually independent with $A_{X}$. We assume all $A_{X^{\prime}}$ are
mutually dependent with any given event $A_{X}$.

Local lemma inequalities. Let $N=|\mathcal{X}|$. The local lemma (Proposition
3) implies the probability that (C) holds is positive if (5) holds, i.e. there
are reals $\gamma,\delta\in[0,1)$ such that for all $K\in\mathcal{K}$ and all
$X\in\mathcal{X}$,

$\Pr(A_{K})\leq\gamma(1-\gamma)^{\kappa}(1-\delta)^{N}\quad\quad\mbox{ and
}\quad\quad\Pr(A_{X})\leq\delta(1-\gamma)^{\lambda}(1-\delta)^{N}.$

We claim that these inequalities are satisfied if we select $\delta=1/(N+1)$
and $\gamma=1/32sbk$.

First inequality. We have $\Pr(A_{K})=\rho^{{s+1\choose 2}}$ and
$(1-\delta)^{N}\geq 1/e$. By (9), $(1-\gamma)^{\kappa}\geq
1-\kappa\gamma>1/2$, so it is sufficient to show $2e\Pr(A_{K})/\gamma\leq 1$
for the first inequality to hold. Since $\rho=(8s/b)^{2/s}$,

$\rho^{{s+1\choose 2}}=\Bigl{(}\frac{8s}{b}\Bigr{)}^{s+1}.$

Since $b=2^{40s}\cdot 2a\log q=2^{40s}k^{1/s}$, and $s\geq 3$,

$\displaystyle\frac{2e}{\gamma}\Pr(A_{K})$ $\displaystyle=$ $\displaystyle
64esbk\cdot\rho^{{s+1\choose 2}}$ $\displaystyle\leq$
$\displaystyle\frac{64esk(8s)^{s+1}}{b^{s}}$ $\displaystyle=$
$\displaystyle\frac{64esk(8s)^{s+1}}{2^{40s^{2}}k}$ $\displaystyle<$
$\displaystyle\frac{64esk(8s)^{s+1}}{64^{s^{2}}k}$ $\displaystyle=$
$\displaystyle es\cdot\Bigl{(}\frac{8s}{64^{s-1}}\Bigr{)}^{s+1}$
$\displaystyle<$ $\displaystyle\frac{es}{8^{s+1}}\;\;<\;\;1.$

Here we used $64^{s-1}>64s$ and $es<8^{s+1}$ for $s\geq 3$. This verifies the
first inequality.

Second inequality. For the second inequality, we use
$1-\gamma\geq\exp(-2\gamma)$, which is valid since $\gamma\leq 1/2$. Recalling
$(1-\delta)^{N}\geq 1/e$, it is enough to show

$e\cdot\Pr(A_{X})\leq\exp(-\log(N+1)-2\gamma\lambda).$

By Lemma 4,

$\Pr(A_{X})\leq\exp\Bigl{(}-\frac{1}{32s}\sum_{p\in P_{X}}|X_{p}|\Bigr{)}.$

Using $|L|=|V(G)|=q^{2}(q^{2}+q+1)$,

$\log(N+1)=\log\Bigl{[}{q^{2}(q^{2}-q+1)\choose
8bq^{2}}+1\Bigr{]}\leq\log{q^{4}\choose 8bq^{2}}-1\leq 32bq^{2}\log q-1.$

Due to the upper bound on $\lambda$ given by (10), it is enough to show

$\exp\Bigl{(}-\frac{1}{32s}\sum_{p\in
P_{X}}|X_{p}|\Bigr{)}\leq\exp\Bigl{(}-32bq^{2}\log q+\frac{1}{64s}\sum_{p\in
P_{X}}|X_{p}|\Bigr{)}.$

Therefore we require

$\exp\Bigl{(}-\frac{1}{64s}\sum_{p\in
P_{X}}|X_{p}|\Bigr{)}\leq\exp(-32bq^{2}\log q).$

Applying (6) and using $a=2^{10}s$, we find

$\displaystyle\frac{1}{64s}\sum_{p\in P_{X}}|X_{p}|$ $\displaystyle\geq$
$\displaystyle\frac{1}{64s}\Bigl{(}\frac{1}{2}(a\log q)\cdot|X|-2abq^{2}\log
q\Bigr{)}$ $\displaystyle=$
$\displaystyle\frac{1}{64s}\Bigl{(}\frac{1}{2}(a\log q)\cdot
8bq^{2}-2abq^{2}\log q\Bigr{)}$ $\displaystyle=$
$\displaystyle\frac{1}{64s}\cdot 2abq^{2}\log q\;\;=\;\;32bq^{2}\log q.$

This proves the second inequality. ∎

## Concluding remarks

$\bullet$ In this paper, we proved $f_{s}(n)=O(\sqrt{n}\log n)$ by suitable
random sampling of points and lines from Hermitian unitals. A part of the
proof essentially involves the union bound over all sets $X$ of lines of size
$8bq^{2}$ – we implicitly assumed in our application of the local lemma in
Section 5 that the events $A_{X}$ depend on all other such events. We first
sampled points randomly from the Hermitian unital with probability of order
$(\log q)/q$. If we sampled points with a lower probability $o(\log q)/q$,
then the union bound no longer works: for large $q$ there are
$N\geq\exp(bq^{2}\log q)$ sets of size $8bq^{2}$ to consider – see Section 5 –
whereas if all the sets $X_{p}:p\in P_{X}$ have size roughly $b$, then the
probability that every $X_{p}$ is $(s-1)$-colored in a random $s$-coloring is
$\exp(-o(bq^{2}\log q))$. We believe it may be possible using randomized
greedy algorithms akin to the Rödl semirandom method or more recent iterative
absorption methods to circumvent this issue and obtain a bounds
$f_{s}(n)=o(\sqrt{n}\log n)$, but did not investigate this technical
direction.

$\bullet$ It is plausible that when $s\geq 3$, $f_{s}(n)=\Omega(\sqrt{n}(\log
n)^{\alpha})$ for some $\alpha>1/2$. The current lower bound of order
$n\sqrt{\log n}/\log\log n$ is achieved by finding an induced $K_{s}$-free
subgraph of size $d$ (the neighborhood of a vertex of degree $d$) or an
independent set of size $n(\log d)/d(\log\log d)$ in a $K_{s+1}$-free graph
with maximum degree $d$. The latter seems potentially wasteful, in that we
could perhaps find for $s\geq 3$ an induced $K_{s}$-free subgraph of size much
larger than $n(\log d)/d(\log\log d)$ in a $K_{s+1}$-free graph. In addition,
it is believable that the $\log\log d$ term is superfluous; perhaps every
$K_{s+1}$-free graph with maximum degree $d$ has an independent set of order
at least $n(\log d)/d$.

##  6 Appendix : Proof of Proposition 2

To prove Proposition 2, we require some notation and preliminaries. Recall for
$s\geq 3$, $n\geq 1$, $\rho\in[0,1]$ and an $s$-coloring $\chi$ of an
$n$-element set with color classes $Y_{1},Y_{2},\dots,Y_{s}$,
$G_{n,\rho}(\chi)$ is obtained by independently and randomly sampling edges of
the complete $s$-partite graph with parts $Y_{1},Y_{2},\dots,Y_{s}$ with
probability $\rho$. The expected number of $K_{s}\subseteq G_{n,\rho}(\chi)$
is precisely

$\mu(\chi)=\rho^{{s\choose 2}}\prod_{i=1}^{s}|Y_{i}|$ (11)

and the variance is defined by

$\triangle(\chi)=\sum_{S\subset[s]}\rho^{2{s\choose 2}-{|S|\choose
2}}\prod_{i\in S}|Y_{i}|\prod_{j\not\in
S}|Y_{j}|(|Y_{j}|-1)=\sum_{S\subset[s]}\rho^{2{s\choose 2}-{|S|\choose
2}}\prod_{i=1}^{n}|Y_{i}|\prod_{j\not\in S}(|Y_{j}|-1),$ (12)

where the sum is over sets $S$ with $2\leq|S|\leq s-1$. From Janson’s
inequality [2, 9] one obtains for any $\rho\in[0,1]$ and $n\geq 1$:

$\Pr(K_{s}\not\subseteq
G_{n,\rho}(\chi))\leq\exp\Bigl{(}-\frac{1}{2}\mu(\chi)\Bigr{)}.$ (13)

provided $\triangle(\chi)\leq\mu(\chi)$.

Proof of Proposition 2. For Proposition 2, $\chi$ is an $s$-coloring with
color classes $Y_{1},Y_{2},\dots,Y_{s}$ satisfying $|Y_{i}|\geq n/2s$ for all
$i\in[s]$. The product in (11) is minimized when $|Y_{i}|=n/2s$ for all but
one value of $i\in[s]$, and the remaining color class has size
$n-(s-1)n/2s>n/2$. Therefore

$\displaystyle\mu(\chi)$ $\displaystyle>$ $\displaystyle\rho^{{s\choose
2}}\Bigl{(}\frac{n}{2s}\Bigr{)}^{s-1}\cdot\frac{n}{2}$ $\displaystyle=$
$\displaystyle\Bigl{(}\frac{8s}{n}\Bigr{)}^{s-1}\Bigl{(}\frac{n}{2s}\Bigr{)}^{s-1}\cdot\frac{n}{2}\;\;=\;\;2^{2s-3}\cdot
n.$

So if $\triangle(\chi)\leq\mu(\chi)$ when $\rho=(8s/n)^{2/s}$ and $n\geq
2^{40s}$, then Proposition 2 follows from (13):

$\Pr(K_{s}\not\subseteq
G_{n,\rho}(\chi))\leq\exp\Bigl{(}-\frac{1}{2}\mu(\chi)\Bigr{)}\leq\exp(-2^{2s-4}n).$

It remains to prove $\triangle(\chi)\leq\mu(\chi)$ when $\rho=(8s/n)^{2/s}$
and $n\geq 2^{40s}$.

By (11) and (12),

$\frac{\triangle(\chi)}{\mu(\chi)}=\sum_{S\subset[s]}\rho^{{s\choose
2}-{|S|\choose 2}}\prod_{j\not\in S}(|Y_{j}|-1).$

The sum is over subsets $S$ of $[s]$ where $2\leq|S|\leq s-1$. By the
inequality of geometric and arithmetic means,

$\prod_{j\not\in S}(|Y_{j}|-1)\leq\prod_{j\not\in
S}|Y_{j}|\leq\Bigl{(}\frac{1}{s-|S|}\sum_{j\not\in
S}|Y_{j}|\Bigr{)}^{s-|S|}\leq\Bigl{(}\frac{n}{s-|S|}\Bigr{)}^{s-|S|}.$

We conclude

$\frac{\triangle(\chi)}{\mu(\chi)}\leq\sum_{i=2}^{s-1}\rho^{{s\choose
2}-{i\choose 2}}\Bigl{(}\frac{n}{s-i}\Bigr{)}^{s-i}{s\choose i}.$

By definition of $\rho$,

$\rho^{{s\choose 2}-{i\choose
2}}=\Bigl{(}\frac{8s}{n}\Bigr{)}^{\frac{(s-i)(s+i-1)}{s}}.$

Therefore

$\displaystyle\frac{\triangle(\chi)}{\mu(\chi)}$ $\displaystyle\leq$
$\displaystyle\sum_{i=2}^{s-1}\Bigl{(}\frac{8s}{n}\Bigr{)}^{\frac{(s-i)(s+i-1)}{s}}\Bigl{(}\frac{n}{s-i}\Bigr{)}^{s-i}{s\choose
i}\;\;=\;\;\sum_{i=2}^{s-1}\Bigl{(}\frac{(8s)^{\frac{s+i-1}{s}}}{(s-i)n^{\frac{i-1}{s}}}\Bigr{)}^{s-i}{s\choose
i}.$

We break the sum into two pieces. First, for $2\leq i\leq\lfloor
s/\log(8s)\rfloor\leq s/2$,

$(s-i)n^{\frac{i-1}{s}}\geq\frac{s}{2}\cdot n^{\frac{1}{s}}\geq 2^{9}s$

since $n\geq 2^{40s}\geq 2^{10s}$. Therefore each term in the sum is at most

$\Bigl{(}\frac{8s\cdot(8s)^{\frac{1}{\log(8s)}}}{2^{9}s}\Bigr{)}^{s-i}{s\choose
i}\leq\Bigl{(}\frac{8es}{2^{9}s}\Bigr{)}^{s-\frac{s}{\log(8s)}}\cdot
2^{s}\leq\Bigl{(}\frac{1}{16}\Bigr{)}^{\frac{s}{2}}\cdot 2^{s}\leq 2^{-s}.$

Second, for $\lfloor s/\log(8s)\rfloor+1<i\leq s-1$, $(i-1)/s\geq 1/2\log(8s)$
and so using $n\geq 2^{40s}$ and $s\geq 3$,

$(s-i)n^{\frac{i-1}{s}}\geq n^{\frac{1}{2\log(8s)}}\geq
2^{\frac{20s}{\log(8s)}}\geq 128s^{3}.$

Therefore each term in the sum is at most

$\Bigl{(}\frac{(8s)^{\frac{s+i-1}{s}}}{128s^{3}}\Bigr{)}^{s-i}{s\choose
i}\leq\Bigl{(}\frac{(8s)^{2}}{128s^{3}}\Bigr{)}^{s-i}{s\choose
i}=\Bigl{(}\frac{1}{2s}\Bigr{)}^{s-i}{s\choose i}.$

We conclude

$\displaystyle\frac{\triangle(\chi)}{\mu(\chi)}$ $\displaystyle\leq$
$\displaystyle\sum_{i=2}^{s-1}\Bigl{(}\frac{1}{2s}\Bigr{)}^{s-i}{s\choose
i}+\sum_{i=2}^{s-1}2^{-s}$ $\displaystyle\leq$
$\displaystyle\Bigl{(}1+\frac{1}{2s}\Bigr{)}^{s}-1+(s-2)2^{-s}\;\;\leq\;\;\sqrt{e}-1+(s-2)2^{-s}.$

Evidently $(s-2)2^{-s}\leq 1/8$ and therefore

$\sqrt{e}-1+(s-2)2^{-s}\leq 0.773\ldots<1.$

We conclude $\triangle(\chi)<\mu(\chi)$, as required. ∎

## References

  * [1] M. Ajtai, J. Komlós, and E. Szemerédi, A note on Ramsey numbers, J. Combin. Theory Ser. A 29 (1980), no. 3, 354–360.
  * [2] N. Alon and J. Spencer, The probabilistic method, (Third Edition) John Wiley and Sons, New York, 2008.
  * [3] S. G. Barwick, G. L. Ebert, Unitals in projective planes, Springer Monographs in Mathematics. Springer, New York, 2008. xii+193 pp.
  * [4] T. Bohman and P. Keevash, The early evolution of the $H$-free process, Invent. Math., 181 (2010), 291–336.
  * [5] A. E. Brouwer, and H. Van Maldeghem, Strongly Regular Graphs, Cambridge Univ. Press, 2022.
  * [6] A. Dudek, T. Retter, and V. Rödl, On generalized Ramsey numbers of Erdős and Rogers, J. Combin. Theory Ser. B 109 (2014), 213–227.
  * [7] G. Fiz Pontiveros, S. Griffiths and R. Morris The triangle-free process and the Ramsey numbers, Mem. Amer. Math. Soc., 263 (2020), 125pp.
  * [8] O. Janzer, T. Gowers, Improved bounds for the Erdős-Rogers function, Advances in Combinatorics, 2020 (3), 27 pp.
  * [9] S. Janson, T. Łuczak, and A. Ruciński, Random graphs, Wiley (2000).
  * [10] O. Janzer, B. Sudakov, Improved bounds for the Erdős-Rogers $(s,s+2)$-problem, Preprint at https://arxiv.org/abs/2307.05441.
  * [11] J. H. Kim, The Ramsey number $R(3,t)$ has order of magnitude $t^{2}/\log t$, Random Struct. Alg. 7 (1995), 173–207.
  * [12] M. Krivelevich, Bounding Ramsey numbers through large deviation inequalities, Random Struct. Alg, 7 (1995), no.2, 145–155.
  * [13] 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.
  * [14] S. Mattheus, and J. A. Verstraëte, The asymptotics of $r(4,t)$, to appear, Annals of Math.
  * [15] D. Mubayi, and J. A. Verstraete, A note on pseudorandom Ramsey graphs, to appear, J. Eur. Math. Soc. (JEMS) (10 pages).
  * [16] M. E. O’Nan, Automorphisms of unitary block designs, J. Algebra 20 (1972), 495–511.
  * [17] F. C. Piper, Unitary block designs, pp. 98–105 in: Graph Theory and Combin. (Proc. Milton Keynes, 1978), R. J. Wilson (ed.), Res. Notes in Math. 34, Pitman, Boston, 1979. (p. 85)
  * [18] J. B. Shearer, A note on the independence number of triangle-free graphs, Discrete Math., 46 (1983), 83–87.
  * [19] J. B. Shearer, On the independence number of sparse graphs, Random Struct. Alg. 7 (1995), no. 3, 269–271.
  * [20] M. Talagrand, Concentration of measure and isoperimetric inequalities in product spaces, Publications Mathématiques de l’IHÉS. Springer-Verlag (1995) 81, 73–205.
  * [21] G. Wolfovitz, $K_{4}$-free graphs without large induced triangle-free subgraphs, Combinatorica 33 (2013), no. 5, 623–631.