virtual environment building method for teleoperation.
Robotica, 35(10):1958–1974.

[61]
Nissler, C., Büttner, S., Marton, Z., Beckmann, L., and Thomasy,
U. (2016).
Evaluation and improvement of global pose estimation with multiple
apriltags for industrial manipulators.
In 2016 IEEE 21st International Conference on Emerging
Technologies and Factory Automation, pages 1–8.

[62]
Nissler, C., Durner, M., Márton, Z.-C., and Triebel, R. (2018).
Simultaneous calibration and mapping.
In International Symposium on Experimental Robotics, Buenos
Aires, Argentina.

[63]
Oh, P., Sohn, K., Jang, G., Jun, Y., and Cho, B.-K. (2017).
Technical overview of team drc-hubo@ unlv's approach to the 2015
darpa robotics challenge finals.
Journal of Field Robotics, 34(5):874–896.

[64]
Ollero, A., Heredia, G., Franchi, A., Antonelli, G., Kondak, K.,
Sanfeliu, A., Viguria, A., Martinez-de Dios, J. R., Pierri, F.,
Cortes, J., Santamaria-Navarro, A., Trujillo Soto, M. A.,
Balachandran, R., Andrade-Cetto, J., and Rodriguez, A. (2018).
The aeroarms project: Aerial robots with advanced manipulation
capabilities for inspection and maintenance.
IEEE Robotics Automation Magazine, 25(4):12–23.

[65]
Ollero, A., Tognon, M., Suarez, A., Lee, D., and Franchi, A. (2022).
Past, present, and future of aerial robotic manipulators.
IEEE Transactions on Robotics, 38(1):626–645.

[66]
Pace, F. D., Gorjup, G., Bai, H., Sanna, A., Liarokapis, M., and Billinghurst,
M. (2021).
Leveraging enhanced virtual reality methods and environments for
efficient, intuitive, and immersive teleoperation of robots.
In 2021 IEEE International Conference on Robotics and
Automation, pages 12967–12973.

[67]
Park, J., Zhou, Q.-Y., and Koltun, V. (2017).
Colored point cloud registration revisited.
In Proceedings of the IEEE international conference on computer
vision, pages 143–152.

[68]
Pohl, C., Hitzler, K., Grimm, R., Zea, A., Hanebeck, U. D., and Asfour, T.
Affordance-based grasping and manipulation in real world
In 2020 IEEE/RSJ International Conference on Intelligent Robots
and Systems, pages 9569–9576.

[69]
Pomerleau, F., Colas, F., and Siegwart, R. (2015).
A review of point cloud registration algorithms for mobile robotics.
Foundations and Trends in Robotics, 4(1):1–104.

[70]
Ponomareva, P., Trinitatova, D., Fedoseev, A., Kalinov, I., and Tsetserukou, D.
Grasplook: a vr-based telemanipulation system with r-cnn-driven
augmentation of virtual environment.
In 2021 20th International Conference on Advanced Robotics,
pages 166–171.

[71]
Puljiz, D., Krebs, F., Bosing, F., and Hein, B. (2020).
What the hololens maps is your workspace: Fast mapping and set-up of
robot cells via head mounted displays and augmented reality.
In 2020 IEEE/RSJ International Conference on Intelligent Robots
and Systems, pages 11445–11451.

[72]
Pumarola, A., Vakhitov, A., Agudo, A., Moreno-Noguer, F., and Sanfeliu, A.
Relative localization for aerial manipulation with pl-slam.
In Aerial Robotic Manipulation, pages 239–248. Springer.

[73]
Redmon, J., Divvala, S., Girshick, R., and Farhadi, A. (2016).
You only look once: Unified, real-time object detection.
In Proceedings of the IEEE conference on computer vision and
pattern recognition, pages 779–788.

[74]
Rosenberg, L. B. (1993).
Virtual fixtures: Perceptual tools for telerobotic manipulation.
In Proceedings of IEEE Virtual Reality Annual International
Symposium, pages 76–82.

[75]
Rouček, T., Pecka, M., Čížek, P.,
Petříček, T., Bayer, J., Šalanskỳ, V., Azayev, T.,
Heřt, D., Petrlík, M., Báča, T., et al. (2022).
System for multi-robotic exploration of underground environments
ctu-cras-norlab in the darpa subterranean challenge.
Field Robotics, 2:1779–1818.

[76]
Roy, S., Unmesh, A., and Namboodiri, V. P. (2018).
Deep active learning for object detection.
In British Machine Vision Conference, volume 362, page 91.

[77]
Rusinkiewicz, S. and Levoy, M. (2001).
Efficient variants of the icp algorithm.
In Proceedings third international conference on 3-D digital
imaging and modeling, pages 145–152.

[78]
Sagardia, M. and Hulin, T. (2018).
Multimodal evaluation of the differences between real and virtual
IEEE Transactions on Haptics, 11(1):107–118.

[79]
Sanchez-Cuevas, P. J., Ramon-Soria, P., Arrue, B., Ollero, A., and Heredia, G.
Robotic system for inspection by contact of bridge beams using uavs.
Sensors, 19(2).

[80]
Sarkisov, Y. S., Kim, M. J., Bicego, D., Tsetserukou, D., Ott, C.,
Franchi, A., and Kondak, K. (2019).
Development of sam: Cable-suspended aerial manipulator.
In 2019 IEEE International Conference on Robotics and
Automation, pages 5323–5329.

[81]
Saska, M., Baca, T., Thomas, J., Chudoba, J., Preucil, L., Krajnik, T., Faigl,
J., Loianno, G., and Kumar, V. (2017).
System for deployment of groups of unmanned micro aerial vehicles in
gps-denied environments using onboard visual relative localization.
Autonomous Robots, 41(4):919–944.

[82]
Saska, M., Vakula, J., and Přeućil, L. (2014).
Swarms of micro aerial vehicles stabilized under a visual relative
In 2014 IEEE International Conference on Robotics and
Automation, pages 3570–3575.

[83]
Scaramuzza, D., Achtelik, M. C., Doitsidis, L., Friedrich, F., Kosmatopoulos,
E., Martinelli, A., Achtelik, M. W., Chli, M., Chatzichristofis, S., Kneip,
L., et al. (2014).
Vision-controlled micro flying robots: from system design to
autonomous navigation and mapping in gps-denied environments.
IEEE Robotics & Automation Magazine, 21(3):26–40.

[84]
Schmid, K., Lutz, P., Tomić, T., Mair, E., and Hirschmüller, H. (2014).
Autonomous vision-based micro air vehicle for indoor and outdoor
Journal of Field Robotics, 31(4):537–570.

[85]
Srivastava, N., Hinton, G., Krizhevsky, A., Sutskever, I., and Salakhutdinov,
R. (2014).
Dropout: a simple way to prevent neural networks from overfitting.
The Journal of Machine Learning Research, 15(1):1929–1958.

[86]
Thomas, H., Katharina, H., Carsten, P., Chun-Yi, S., Subhash, R., and
Honghai, L. (ICIRA 2012).
Interactive features for robot viewers.
In Intelligent Robotics and Applications, volume 7508.

[87]
Thrun, S., Beetz, M., Bennewitz, M., Burgard, W., Cremers, A. B., Dellaert, F.,
Fox, D., Haehnel, D., Rosenberg, C., Roy, N., et al. (2000).
Probabilistic algorithms and the interactive museum tour-guide robot
The International Journal of Robotics Research,

[88]
Tranzatto, M., Mascarich, F., Bernreiter, L., Godinho, C., Camurri, M.,
Khattak, S., Dang, T., Reijgwart, V., Loeje, J., Wisth, D., et al. (2022).
Cerberus: Autonomous legged and aerial robotic exploration in the
tunnel and urban circuits of the darpa subterranean challenge.
Field Robotics, 2:274–324.

[89]
Trujillo, M. A., Martínez-de Dios, J. R., Martín, C., Viguria, A., and
Ollero, A. (2019).
Novel aerial manipulator for accurate and robust industrial ndt
contact inspection: A new tool for the oil and gas inspection industry.
Sensors, 19(6).

[90]
Vempati, A. S., Khurana, H., Kabelka, V., Flueckiger, S., Siegwart,
R., and Beardsley, P. (2019).
A virtual reality interface for an autonomous spray painting uav.
IEEE Robotics and Automation Letters, 4(3):2870–2877.

[91]
Wagner, D. and Schmalstieg, D. (2007).
Artoolkitplus for pose tracking on mobile devices.
In Proceedings of 12th Computer Vision Winter Workshop, page

[92]
Wang, J. and Olson, E. (2016).
AprilTag 2: Efficient and robust fiducial detection.
In 2016 IEEE/RSJ International Conference on Intelligent Robots
and Systems, pages 4193–4198.

[93]
Wang, Y. and Solomon, J. M. (2019).
Deep closest point: Learning representations for point cloud
In Proceedings of the IEEE/CVF International Conference on
Computer Vision, pages 3523–3532.

[94]
Weiss, S., Achtelik, M. W., Lynen, S., Chli, M., and Siegwart, R. (2012).
Real-time onboard visual-inertial state estimation and
self-calibration of mavs in unknown environments.
In 2012 IEEE international conference on robotics and
automation, pages 957–964.

[95]
Whitney, D., Rosen, E., Phillips, E., Konidaris, G., and Tellex, S. (2020).
Comparing robot grasping teleoperation across desktop and virtual
reality with ros reality.
Robotics Research, pages 335–350.

[96]
Wonsick, M. and Padir, T. (2020).
A systematic review of virtual reality interfaces for controlling and
interacting with robots.
Applied Sciences, 10(24):9051.

[97]
Wu, Y., Song, J., Sun, J., Zhu, F., and Chen, H. (2018).
Aerial grasping based on vr perception and haptic control.
In 2018 IEEE International Conference on Real-time Computing and
Robotics (RCAR), pages 556–562.

[98]
Yashin, G. A., Trinitatova, D., Agishev, R. T., Ibrahimov, R., and Tsetserukou,
D. (2019).
Aerovr: Virtual reality-based teleoperation with tactile feedback for
aerial manipulation.
In 2019 19th International Conference on Advanced Robotics,
pages 767–772.

[99]
Zhang, J. and Singh, S. (2017).
Low-drift and real-time lidar odometry and mapping.
Autonomous Robots, 41(2):401–416.

[100]
Zhang, Z., Dai, Y., and Sun, J. (2020a).
Deep learning based point cloud registration: an overview.
Virtual Reality & Intelligent Hardware, 2(3):222–246.

[101]
Zhang, Z., Zhu, Y., and Zhu, S.-C. (2020b).
Graph-based hierarchical knowledge representation for robot task
transfer from virtual to physical world.
In 2020 IEEE/RSJ International Conference on Intelligent Robots
and Systems, pages 11139–11145.

[102]
Zhou, Q.-Y., Park, J., and Koltun, V. (2016).
Fast global registration.
In European Conference on Computer Vision, pages 766–782.

§ PLATFORM DESIGN, CONTROL, TELEOPERATION AND IT ARCHITECTURES

In this section, we present the details about platform design and control, teleoperation system and IT architectures.

§.§ Platform Control

The control framework of SAM. Propeller-based oscillation damping and yaw controller, torque controller for robotic manipulator, and feedforward position controller for the winches are depicted. Oscillation damping and yaw controller use propeller-based actuation to stabilize the platform while SAM is performing manipulation task. IMU provides feedback signals. Impedance-based torque control is performed for the robotic arm, where joint encoders and torque sensing are used as feedback. The three winches can adjust the length of the cable suspending the platform.

The control framework of SAM is depicted in Figure <ref>. It includes three separate controllers for three sets of actuators. Each of these blocks are to fulfill three different control tasks. The first controller is a propeller-based oscillation damping and yaw motion control using IMU as a single main sensor. The main task herein is to damp out oscillations and control yaw motion. Oscillations occur due to the forces and moments caused by the robotic arm, which interacts with the environments. In outdoor settings, severe wind, motion of the carrier, and other external disturbances cause such oscillations. Damping out these undesired motions are to perform precise manipulation tasks with the robotic arm. Similarly, yaw motion controller is to change the orientation of the platform, which can position the manipulator in a convenient pose. To do so, the robot actuation is performed by eight propellers attached to each BLDC motors. The Electronic Speed Controllers (ESCs) regulates BLDC motors to rotate at specific speed. The used sensors are again a single IMU attached to a fixed point of the platform. The control signals are generated by the propeller controller, which is essentially a PID control algorithm. These control signals are mapped to PWM signals per each motors using the known configurations of motors and propellers. The frequency rate is 200Hz in a real-time computer. Secondly, a feedforward position controller is used to control three winches. These winches are connected to cables that suspend the platforms. Maxon motors are used without any feedback signals. The main feature is to control the length of the cables. With these, the pitch and the roll orientation of the platform can be adjusted with slower dynamics. Another advantage is to move the platform up and down, without moving the carrier. Here, a simple feedforward position controller is integrated where desired relative cable length are converted into the motor movements. The frequency rate of the controller is again 200Hz in a real-time computer. Lastly, the robotic arm attached to the platform, is controlled using impedance-based torque control algorithm. Torque control is the current golden standards for such robotic arms. The main task here is to perform grasping and manipulation tasks, using the torque control capabilities of the robot. This means that, in teleoperation mode, the robotic arm must follow the command from the human operator, while autonomously taking care of local redundancy of the joints. Joint encoders and torque sensors provide such feedback signals. The manipulator's internal joint torque controller uses sampling rate of 3kHz.

§.§ Teleoperation System

Teleoperation architecture based on Time-Domain Passivity Approach (TDPA). The TDPA approach ensures stability under imperfect communication between the haptic device and the  robot, and consists of two components, namely passivity observer and passivity controller. The proposed telepresence system also includes haptic guidance, robotic perception and virtual reality for 3D visual feedback.

The used bilateral teleoperation system is depicted in Figure <ref>. The main challenge is ensuring a stable bilateral teleoperation with force feedback. Instabilities can be caused by time delays, packet loss and jitters, which are characteristics of imperfect communication.

In the paper, a two channel architecture with time-domain passivity approach is used, which works as follows. The human operator sends both position $v_m(t)$ (velocity analogously) from the haptic device device to the robot at time t. Due to the time-delay T, the robot receives them as $v_{sd}(t) = v_m(t-T)$ where $G_h$ is a scaling factor that can be tuned to match both system dynamics. A local impedance controller then generate reference force $f_{s}(t)$ based on command position. If K terms represent controller gains and $x_s$, $v_{s} \in \mathbb{R}^2$ are the respective feedback signals from the robot which enables position tracking, then the total commanded force can be written as:

\begin{equation}
\label{tdpa:eq:1}
f_s(t) = K_{ds}(v_{sd}(t)-v_s(t)) + K_{ps}(x_{sd}(t)-x_s(t)).
\end{equation}

The computed force $f_{m0}(t) = G_sf_{s}(t-T)$ and measured forces at the end effector $f_{me}(t) = G_ef_e(t-T)$ are sent back to the haptic device resulting in the force feedback term $f_m(t)$ in Equation <ref> where we additionally add a feedforward term with $v_m(t)$. The feedforward terms add transparency to the system and is known to be advantageous over a 2-channel architecture:

\begin{equation}
\label{tdpa:eq:2}
f_m(t) = f_{m0}(t) + f_{me}(t) + K_{dm}v_m(t).
\end{equation}

As the signals pass through communication channels, time-delays, jitter and packet losses are typically present and can cause instability of overall system. To cope with this issue, we use TDPA which constitutes two components namely Passivity Observer (PO) and Passivity Controller (PC). Briefly speaking, PO monitors the energy flow of a network whereas PC dissipates the energy introduced by the network. A key underlying idea is PC's control law ensures passivity of the system by damping out the energy that is more than the stored amount. Since passivity is a sufficient condition for stability, TDPA ensures stability in trade-off to performance. Therefore, POPCs are placed for delayed signals at the robot side $v_m(t-T)$, and haptic device side $f_{s}(t-T)$. For brevity, let us denote the haptic device signals received and sent as $u_m(k-D)$ and $y_m(k)$, and the robot input and output signals as $u_s(k-D)$ and $y_s(k)$. Here, k is a discrete time and D is a discrete time delay. Then,

\begin{equation}
\label{tdpa:eq:3}
u_{m,c}(k) =\left\{\begin{matrix}
u_m(k-D) & \text{if} \ \  W_m(k)> 0 \\
u_m(k-D) - \frac{W_m(k)}{T_s y_m^2(k)}y_m(k) & \text{else}
\end{matrix}\right.
\end{equation}

is the governed control law at haptic device. The same rationale applies at the robot side. In equation <ref>, $T_s$ is the sampling time and $W_m(k)$ is the energy flow at haptic device, which is observed by the PO. In this way, PC modifies the delayed signal so that passivity condition $W_m(k) \geq 0$ for all k is met:

\begin{equation}
\begin{array}{lll}
\label{tdpa:eq:4}
\centering
W_m(k)  &=&  E_{\text{s,in}}(k-D)-E_{\text{m,out}}(k)+E_{\text{m,PC}}(k) \\
E_{\text{s,in}}(k-D) &=& E_{\text{s,in}}(k-D-1) + T_s P_{\text{s,in}}(k-D) \\
5E_{\text{m,out}}(k) &=& E_{\text{m,out}}(k-1)+T_sP_{\text{m,out}}(k).
\end{array}
\end{equation}

PO essentially estimates $W_m(k)$ for PCs control law. This is achieved by Equation <ref> which uses the delayed energy $E_{\text{s,in}}(k-D)$ input from the robot side, the energy exiting at the haptic device side $E_{\text{m,out}}(k)$ and the dissipated energy by PC $E_{\text{m,PC}}(k)$. As the signals being exchanged are velocities $v$ and forces $f$, the energy can be computed by inner products and sampling time. The power contributions should take into account the direction of energy flow. For example, $P_{\text{s,in}} = 0$ if $P_{\text{s,in}} \leq 0)$ and otherwise, $P_{\text{s,in}} = f_s(k)(-v_m(n-D))$. Taking into account time-delays, jitter and packet-loss, TDPA works on energy level and it ensures stability in teleoperation.

Besides, the presented perception algorithms are executed in the robot, providing the information about the object poses. This information is feed into the ground station for creating virtual reality. Another usage of perception is haptic guidance via virtual fixtures. Virtual fixtures [12] are artificial walls that, by means of force feedback, helps the human operator for high performance task execution. Once the human operator is trying to move outside the artifical walls, certain computed forces are activated and sent to the haptic device through TDPA. This then limits the motion of the human operator by inserting certain forces and moments in the haptic device. Because these artificial walls are obtained from the perception system of the robot, the proposed telepresence system supports the haptic guidance. More details about virtual fixtures and other means of haptic guidances are presented by 86, 78, 56.

Wrench forces and moments from the peg-in-hole experiments. The poses of the end-effector are alternatively depicted in Figure <ref>. In $F_z$, between 50s and 60s, a drop in force is observed due to the successful peg-in-hole insertion.

Wrench forces and moments from the pick-and-place experiments. The corresponding poses of the end-effector are depicted in Figure <ref>. In $Mz$, the haptic guidance activation can be seen, which leads to correction of yaw angle.

§.§ IT Architectures

SAM's IT architecture. The broad division is between the ground station and the robot. The ground station hosts haptic device, VR and the human operator. WiFi routers are used to communicate to the robot, which simulates the real teleoperation scenarios with imperfect communication and delays. The robot hosts computers, actuators, sensors and other auxiliary components such as power distribution, battery, etc. SAM has three computers. The robot control unit (RCU) deals with the control of robotic manipulator and hosts real-time linux as its operating system. The flight control computers (FCC) deals with platform control, including propellers, winches and additional servo motors as landing gear. FCC hosts QNX real-time linux system. Lastly, NVIDIA Jetson TX2 is used as a vision processing unit. The TX2 hosts non real-time linux (ubuntu tegra) but has a GPU for deploying the deep learning models.

In Figure <ref>, an overview of the used IT architecture is shown. Broadly, the set-up can be divided into the ground station components and the robot itself. To emulate real industrial scenarios of telepresence robots, the connection between the robot and the ground station is established through a WiFi router. The ground station constitutes of a laptop (Dell Latitude 5591), a haptic device (Force dimension Lambda or DLR SpaceJoystick Ryo), VR headset (Meta occulus) and a computer monitor. VR headset is optionally used. From the robot side, the Flight Control Computer (FCC) is employed, which is a product from the DLR aerial robotic spin-off Elektra UAS. FCC is a QNX based real-time system () and contains  a field-programmable gate array (FPGA) based safety switch. FCC is connected to winches, servo motors (Futaba S3152) and ESCs with custom written drivers. Oscillation damping controller, yaw controller and on-and-off of servos are executed within FCC. This modules read data from IMU (Xsens MTi 100-Series). In addition, FCC is also connected to the manual command transmitter via a radio link. The robot control unit (RCU) is based on Kontron KTH81 Flex board and uses real-time linux patch of open suse operating system.  Ethernet for Control Automation Technology (EtherCAT) protocol is used to communication with the robotic arm. We note that EtherCAT is a standardized real-time bus that enables synchronous actuation of all the joint motors. RCU executes TDPA, haptic guidance and impedance controller, while reading joint and torque information from the robotic arm. The last computing module is NVIDIA Jetson TX2 which contains all the sensor drivers, perception software stacks, and other GPU processing modules for running deep learning models. The sensors are all connected via Ethernet interface. For this, Cogswell carrier board is employed, which supports five Ethernet ports with Power of Ethernet (PoE) functionality. With this, Mako camera is easily powered. The carrier board also handles high data throughput from all these sensors. The robot is additionally equipped with safety switch for the robotic arm, power distribution system and battery. All the computers and WiFi routers are connected via an Ethernet switch (Netgear GS105). The communication between the ground station and the robot is through the point-to-point communication channel by opening an access point. Ubiquiti Bullet M5 is employed for the access point.


# Erasure list-decodable codes and Turán hypercube problems

Noga Alon Princeton University, Princeton, NJ, USA and Tel Aviv University,
Tel Aviv, Israel. Email<EMAIL_ADDRESS>Research supported in part
by NSF grant DMS-2154082.

###### Abstract

We observe that several vertex Turán type problems for the hypercube that
received a considerable amount of attention in the combinatorial community are
equivalent to questions about erasure list-decodable codes. Analyzing a recent
construction of Ellis, Ivan and Leader, and determining the Turán density of
certain hypergraph augemntations we obtain improved bounds for some of these
problems.

##  1 Introduction and results

###  1.1 Erasure codes and Turán hypercube problems

A set ${\cal C}$ of binary vectors of length $n$ is a $(d,L)$-list decodable
erasure code of length $n$ (a $(d,L,n)$-code, for short) if for every codeword
$w$, after erasing any $d$-bits of $w$, the remaining part of the vector has
at most $L$ possible completions into codewords of ${\cal C}$. Erasure list-
decodable codes are considered in [6], see also [2] and the references
therein. These papers deal with codes of rate smaller than $1$, that is, the
cardinality of ${\cal C}$ is exponentially smaller than $2^{n}$.

Here we consider much denser codes, where the cardinality of ${\cal C}$ is a
constant fraction of all $2^{n}$ vectors. This range of the parameters is not
very natural from the information theoretic point of view, but it is
equivalent to a problem that received a considerable amount of attention in
the combinatorial community, see [11], [8], [1], [7], [3], [10], [5], [4].
Indeed, ${\cal C}$ is a $(d,L,n)$-code if and only if it is a subset of
vertices of the discrete $n$-cube $Q_{n}$ that contains at most $L$ vertices
of any $d$-dimensional subcube of $Q_{n}$. In this language, for example, the
result of [11], proved independently in [8], is that the maximum possible
cardinality of a $(2,3,n)$-code is $\lceil 2^{n+1}/3\rceil$.

###  1.2 $(d,2^{d}-1,n)$-codes

An intriguing special case of the general problem of determining or estimating
the maximum possible cardinality of $(d,L,n)$-codes is the cases $L=2^{d}-1$
corresponding to codes ${\cal C}$ that contain no full copy of a $d$-subcube.
Here it is more natural to consider the complement and denote by $g(n,d)$ the
smallest cardinality of a subset of the vertices intersecting every
$d$-subcube. Let $\gamma_{d}$ denote the limit
$\lim_{n\mapsto\infty}g(n,d)/2^{n}$ (it is easy to see that the limit exists
as for any fixed $d$, $g(n,d)/2^{n}$ is a monotone increasing function of
$n$). Trivially, $\gamma_{1}=1/2$, and the result of [11] and [8] mentioned
above is that $\gamma_{2}=1/3$. In [1] it is shown that
$\gamma_{d}\geq\log_{2}(d+2)/2^{d+2}$. It has been a folklore conjecture (see
[3]) that $\gamma_{d}=1/(d+1)$ but this is refuted in a very strong sense in a
recent paper of Ellis, Ivan and Leader [4], where it is shown that
$(\gamma_{d})^{1/d}\leq 2^{-1/8+o(1)})$. As mentioned in [4] we observed that
their argument can be improved to show that $(\gamma_{d})^{1/d}\leq
2^{-1/2+o(1)}$. This is stated in the following proposition.

######  Proposition 1.1.

For every large $k$ and every $n$ there is a subset of less than a fraction of
$2^{-k}$ of the vertices of the $n$-cube that intersects the set of vertices
of any cube of dimension $d=2k+3\log_{2}k$.

###  1.3 Codes of positive density

Another range of the parameters of $(d,L,n)$-codes that has been studied in
quite a few combinatorial papers deals with the minimum possible $L=L(d)$ so
that there exists infinitely many $(d,L,n)$-codes of positive density. More
precisely, let $L(d)$ denote the smallest possible $L$ so that there exists an
${\varepsilon}={\varepsilon}(d)>0$ such that for every $n$ there is a
$(d,L,n)$-code of cardinality at least ${\varepsilon}2^{n}$. The problem of
determining or estimating $d(L)$ is considered in [10] (where it is denoted by
$\mu(d)$.) A conjecture suggested in [3] asserts that $L(d)={d\choose{\lfloor
d/2\rfloor}}$. It is easy to see that this is always an upper bound for
$L(d)$, and that it holds as equality for $d\leq 3$. However, somewhat
surprisingly this conjecture too is refuted by the recent construction of [4]
which shows that $L(d)$ is at most $(5/6){d\choose{\lfloor d/2\rfloor}}$ for
every $d\geq 4$. The authors of [10] proved a lower bound for $L(d)$, showing
that it is at least $t_{2}(d)$ \+ $t_{3}(d)$, where $t_{2}(d)$ is $0$ if
$\lceil d/3\rceil$ is odd and $1$ otherwise, and $t_{3}(d)$ is $3^{d/3}$ for
$d\equiv 0\bmod 3$, is $4\cdot 3^{(d-4)/3}$ for $d\equiv 1\bmod 3$ and is
$2\cdot 3^{(d-2)/3}$ for $3\equiv 2\bmod 3$. In particular, this shows that

$L(5)\geq 7,L(6)\geq 10,L(7)\geq 12,L(8)\geq 18,L(9)\geq 27,L(10)\geq 37.$

Here we improve the lower bounds for all $d\geq 5$, proving, in particular,
the following

######  Proposition 1.2.

$L(5)\geq 8,L(6)\geq 12,L(7)\geq 20,L(8)\geq 32,L(9)\geq 48,L(10)\geq 80.$

For large $d$ we prove that $L(d)\geq d\cdot 3^{(d-6)/3}$ for $d$ divisible by
$3$ and obtain a similar bound for $d$ that is not divisible by $3$. The
improved lower bounds are obtained by applying the simple result about graph
and hypergraph augmentations described in the following subsection.

We also improve the upper bounds as follows:

######  Theorem 1.3.

$L(5)=8,L(6)\leq 16,L(7)\leq 28$

and for large $d$,

$L(d)\leq(c+o(1)){d\choose{\lfloor d/2\rfloor}}$

where

$c=\lim_{t\mapsto\infty}\frac{(2^{t}-2)(2^{t}-4)\ldots(2^{t}-2^{t-1})}{(2^{t}-1)^{t-1}}$

is roughly $0.29$.

Note that by the results above the exact values of $L(d)$ for $1\leq d\leq 5$
are given by the sequence $1,2,3,5,8$.

###  1.4 Graph and hypergraph augmentations

For a graph $G=(V,E)$ and an integer $r\geq 2$, let the $r$-augmentation of
$G$, denoted by $G(r)$, be the $r$-uniform hypergraph $(V\cup S,\\{e\cup
S:e\in E\\})$, where $S\cap V=\emptyset$ and $|S|=r-2$. Thus $G(r)$ is
obtained from $G$ by adding the same set of $r-2$ vertices to each edge of
$G$. This set is called the stem of $G(r)$. More generally, for a $k$-uniform
hypergraph $H=(V,E)$ and an integer $r\geq k$, let the $r$-augmentation of
$H$, denoted $H(r)$, be the $r$-uniform hypergraph $(V\cup S,\\{e\cup S:e\in
E\\})$, where $S\cap V=\emptyset$ and $|S|=r-k$.

For a fixed $r$-uniform hypergraph $F$ and for an integer $n$ let $ex(n,F)$
denote the maximum possible number of edges in an $r$-uniform hypergraph on
$n$ vertices that contains no copy of $F$. The Turán density $\pi(F)$ of $F$
is the limit, as $n$ tends to infinity, of the ratio $ex(n,F)/{n\choose r}$
(it is easy to see that this limit always exists, and lies in $[0,1]$.)

The recent construction of Ellis, Ivan and Leader in [4] implies that if the
chromatic number of a graph $G$ satisfies $\chi(G)\geq 4$, then the Turán
density of $G(r)$ is at least $0.29$ for every $r$. (The construction in [4]
is described for $G=K_{4}$, but it is not difficult to check that it works for
every graph $G$ of chromatic number at least $4$).

Here we observe that if $\chi(G)\leq 3$ then the Turán density of $G(r)$ tends
to zero as $r$ tends to infinity. This gives a full characterization of all
the fixed graphs $G$ that must appear as links in any $r$-uniform hypergraph
of positive density (with at least $2r+1$ vertices, say), provided $r$ is
sufficiently large. This result has been proved independently by Robert
Johnson [9]

######  Proposition 1.4.

For every fixed graph $G$ with chromatic number at most $3$, the limit of the
Turán density of $G(r)$ as $r$ tends to infinity is $0$.

The argument easily extends to augmentations of hypergraphs, giving the
following

######  Proposition 1.5.

For any fixed $k$-uniform hypergraph $H$ in which the set of vertices is the
disjoint union of $k+1$ subsets, so that every edge contains at most one
vertex in each subset, the Turán density of $H(r)$ tends to $0$ as $r$ tends
to infinity

Remark: By averaging over $r$, Proposition 1.4 implies that for every fixed
${\varepsilon}>0$ and every fixed graph $G$ of chromatic number at most $3$,
if $n>n_{0}(G,{\varepsilon})$ then any family of at least ${\varepsilon}2^{n}$
subsets of $[n]=\\{1,2,\ldots,n\\}$ contains a copy of $G(r)$ for some $r$.
Here, too, the construction in [4] implies that this is false for graphs $G$
of chromatic number at least $4$. Similarly, Proposition 1.5 implies the
corresponding result for the hypercube.

##  2 Proofs

###  2.1 Augmentations

In this subsection we describe the short proof of Proposition 1.4. The proof
of Proposition 1.5 is essentially identical.

Fix an ${\varepsilon}>0$, suppose $n\geq 2r+1$ and let $H$ be an $r$-uniform
hypergraph on $n$ vertices with at least ${\varepsilon}{n\choose r}$ edges. By
averaging there is a subset $U$ of $2r+1$ vertices so that $H$ contains at
least ${\varepsilon}{{2r+1}\choose r}$ edges in $U$. Let $W$ be a random
subset of size $r+1$ of $U$. The expected number of edges contained in $W$ is
at least ${\varepsilon}(r+1)$. If $W$ contains $k\geq 3$ edges, then any
collection of $3$ of them gives a copy of $K_{3}(r)$. Thus we get ${k\choose
3}$ such copies on the set of vertices $W$. By convexity (assuming, say,
${\varepsilon}(r+1)>10$) this implies that the total number of copies of
$K_{3}(r)$ that are contained in $U$ is at least

${{2r+1}\choose{r+1}}\cdot{{{\varepsilon}(r+1)}\choose 3}.$

By averaging over the ${{2r+1}\choose{r-2}}$ possible stems we get that there
is one common stem for at least

$\frac{{{2r+1}\choose{r+1}}}{{{2r+1}\choose{r-2}}}\cdot{{{\varepsilon}(r+1)}\choose
3}>\frac{{\varepsilon}^{3}}{2}{r\choose 3}$

copies of $K_{3}(r)$, where here we assumed, say, $r>10/{\varepsilon}$. This
gives the existence of a graph $F$ on a subset of $r+3$ vertices of $U$ so
that $F$ contains more than $\frac{{\varepsilon}^{3}}{2}{r\choose 3}$
triangles and our hypergraph contains a copy of $F(r)$. By the known results
about the Turán density of $3$-uniform, $3$-partite hypergraphs first proved
in [12], for every $s$ and every sufficiently large
$r>r_{0}({\varepsilon},s)$, $F$ contains a complete $3$-partite graph $T$ with
$s$ vertices in each vertex class. Since $F(r)$ contains $T(r)$ this completes
the proof of the proposition. $\Box$

###  2.2 Hitting subcubes

In this subsection we describe the proof of Proposition 1.1. The proof is
identical to the one in [4] with one modification, replacing a naive estimate
for the maximum possible number of $k$-wise independent vectors in $F_{2}^{s}$
by the Plotkin bound [15], which is a classical result in the theory of Error
Correcting Codes.

For simplicity we omit all floor and ceiling signs whenever these are not
crucial. All logarithms are in base $2$ unless otherwise specified.

Following the notation in [4], for integers $t>s$ and $r>s$, let $D_{r}(s,t)$
denote the $r$-uniform hypergraph obtained by adding a stem of size $r-s$ to
every edge of the complete $s$-uniform hypergraph $T$ on $t$ vertices. In the
notation of the previous subsection $D_{r}(s,t)$ is $T(r)$. In [4], Theorem 6,
it is proved that for every fixed $k$ and every (large) $r$, the Turán density
of $D_{r}(k,8k+1)$ is at least $1-O(2^{-k})$. The following lemma provides a
quantitative improvement.

######  Lemma 2.1.

For every fixed (large) integer $k$ and every (large) $r$, the Turán density
of $D_{r}(k+2\log k,2k+3\log k)$ is larger than $1-2^{-k}$.

###### Proof.

Suppose $r$ is large and consider the hypergraph on a set of $2^{r+k}-1$
vertices indexed by the nonzero vectors in $F_{2}^{r+k}$, where an $r$-set
forms an edge iff it is linearly independent. It is easy to see that the
density of this hypergraph is larger than $1-2^{-k}$. We claim that it
contains no copy of $D_{r}(s,t)$ where $s=k+2\log k,t=2k+3\log k$. Indeed, as
in the proof in [4], the existence of such a set would give a collection of
$t$ binary vectors in $F_{2}^{k+s}$ so that every subset of $s$ of them is
linearly independent. Let $A$ be the $k+s$ by $t$ matrix whose columns are
these $t$ vectors and consider the linear code whose parity check matrix is
$A$. This is the code consisting of all binary vectors of length $t$ that are
orthogonal to every row of $A$. The dimension of this code is at least
$t-(k+s)=\log k$ and hence the number of vectors in it is at least $k$.
However, the minimum distance of this code is at least $s+1$, since every set
of $s$ columns of $A$ is linearly independent. By the Plotkin bound it follows
that the number of vectors in the code cannot exceed
$2\frac{(s+2)}{2s+2-t}<k$, contradiction. Therefore this hypergraph contains
no copy of $D_{r}(s,t)$. The assertion of the lemma follows by considering
blow ups of this hypergraph, which for large $r$ hardly change the density. ∎

Returning to the proof of Proposition 1.1 we apply the lemma and take the
union of the complement of the construction it provides in every (large) layer
$r$ of the hypercube. In the small layers we simply take all vertices. This
gives a set of vertices of the $n$-cube that contains less than a fraction of
$2^{-k}$ of the vertices and intersects every copy of $D_{r}(k+2\log
k,2k+3\log k)$. Since every subcube $Q_{d}$ of $Q_{n}$ of dimension
$d=2k+3\log k$ fully contains a copy of some $D_{r}(k+2\log k,2k+3\log k)$
this completes the proof of the proposition. $\Box$

###  2.3 List Erasure Codes

In this subsection we describe the proofs of the improved upper and lower
bounds for $L(d)$. The lower bounds follow easily from the results about graph
and hypergraph augmentations proved in subsection 2.1. The upper bounds
combine the construction in [4] with simple tools from linear algebra and a
computation of the Lagrangians of appropriately defined $t$-uniform
hypergraphs.

Starting with the proof of the lower bound define, for any integer $d\geq 2$,
$g(d)$ to be the maximum possible value of the expression

$\sum_{i=1}^{k+1}\prod_{j\in[k+1]-i}a_{j}$

where the maximum is taken over all integers $k\geq 1$ and over all partitions
of $d$ of the form $d=a_{1}+a_{2}+\cdots+a_{k+1}$, where $a_{i}\geq 0$ are
integers. Thus, for example, $g(2)=2$ as demonstrated by the partition
$2=2+0$, $g(5)=8$ using the partition $5=2+2+1$ and $g(10)=80$ using the
partition $10=2+2+2+2+2$.

######  Lemma 2.2.

For every $d\geq 2$, $L(d)\geq g(d).$

###### Proof.

Fix a small ${\varepsilon}>0$ and let ${\cal C}$ be a collection of at least
${\varepsilon}\cdot 2^{n}$ vertices of $Q_{n}$. For a fixed $d\geq 2$ let
$g(d)=\sum_{i=1}^{k+1}\prod_{j\in[k+1]-\\{i\\}}a_{j}$ where $a_{j}\geq 0$ are
integers. Note that this number is exactly the number of edges of the
$k$-uniform hypergraph $H$ on $k+1$ vertex classes of sizes
$a_{1},a_{2},\ldots,a_{k+1}$ whose edges are all $k$-tuples containing at most
$1$ vertex of each class. (This holds even if some of the numbers $a_{i}$ are
$0$). By the remark following Propositions 1.4 and 1.5 if $n$ is sufficiently
large as a function of $d$ and ${\varepsilon}$, then ${\cal C}$ must contain
$H(r)$ for some $r$. The desired result follows as this $H(r)$ is fully
contained in some subcube of dimension $d$ in $Q_{n}$. ∎

The assertion of Proposition 1.2 follows easily from that of the last lemma.
The bounds for $L(d)$ for $5\leq d\leq 10$ are obtained by computing the value
of $g(d)$ for these values of $d$. For large $d$ divisible by $3$, say
$d=3(k+1)$, it is not difficult to check that the value of $g(d)$ is obtained
by the partition $a_{1}=a_{2}=\ldots=a_{k+1}=3$, implying that
$L(d)\geq(k+1)3^{k}=d\cdot 3^{(d-6)/3}$. $\Box$

We proceed with the proof of the upper bounds for $L(d)$ stated in Theorem
1.3, starting with several preliminary lemmas. For an integer $t\geq 1$, let
$P(t)$ denote the probability that $t$ binary vectors
$v_{1},v_{2},\ldots,v_{t}$ in $F_{2}^{t}$, each chosen randomly, uniformly and
independently among all $2^{t}-1$ nonzero vectors in $F_{2}^{t}$, are linearly
independent over $F_{2}$, that is, form a basis of $F_{2}^{t}$. Clearly
$P(1)=1$. Choosing the vectors one by one and multiplying the conditional
probabilities that each vector is not spanned by the previously chosen ones
assuming these are linearly independent, it follows that

$P(t)=(\frac{2^{t}-2}{2^{t}-1})\cdot(\frac{2^{t}-4}{2^{t}-1})\cdots(\frac{2^{t}-2^{t-1}}{2^{t}-1})=\frac{(2^{t}-2)(2^{t}-4)\cdots(2^{t}-2^{t-1})}{(2^{t}-1)^{t-1}}.$
(1)

It is not difficult to check that for any $t>1$

$P(t)=(\frac{2^{t}-2)}{2^{t}-1})^{t-1}P(t-1).$ (2)

This implies that for any $k$

$c=\lim_{t\mapsto\infty}P(t)=\mbox{inf}_{t}P(t)\geq
P(k)(1-O(\frac{k}{2^{k}})).$ (3)

The equality (2) can be verified by induction on $t$, using (1). It can also
be proved by the following combinatorial argument that will be useful later
too.

The nonzero vectors $v_{1},v_{2},\ldots,v_{t}$ form a basis iff the following
two events $E_{1}$ and $E_{2}$ hold. The event $E_{1}$ is that each $v_{i}$
for $i\geq 2$ is not chosen to be equal to $v_{1}$. It is clear that its
probability is exactly $(\frac{2^{t}-2)}{2^{t}-1})^{t-1}$. Given the choice of
$v_{1}$, each nonzero vector $v$ in $F_{2}^{t}$ has a unique expression as
$v=x_{v}+y_{v}$, where $x_{v}\in\\{0,v_{1}\\}$ lies in the space generated by
$v_{1}$, and $y_{v}$ is orthogonal to this space. Let $E_{2}$ be the event
that the vectors $y_{v_{2}},y_{v_{3}},\ldots,y_{v_{t}}$ form a basis of the
$(t-1)$-dimensional subspace of $F_{2}^{t}$ orthogonal to $v_{1}$.
Conditioning on the event $E_{1}$, each nonzero vector of this
$(t-1)$-dimensional space is selected with uniform probability among these
$2^{t-1}-1$ possible vectors. These vectors span the space with probability
$P(t-1)$, that is $Prob[E_{2}|E_{1}]=P(t-1)$. This implies (2) and hence also
gives that the sequence $P(t)$ is monotone decreasing and thus approaches a
limit, which is denoted by $c$ in Theorem 1.3. It is easy to check that this
limit is roughly $0.29$.

We need the following simple result.

######  Lemma 2.3.

Let $t\geq 1$ and let $\\{p_{v}:v\in F_{2}^{t}-\\{0\\}~{}\\}$ be an arbitrary
probability distribution on the nonzero vectors in $F_{2}^{t}$. Then

$\sum_{v\in
F_{2}^{t}-\\{0\\}}p_{v}(1-p_{v})^{t-1}\leq(\frac{2^{t}-2}{2^{t}-1})^{t-1}.$

Equality holds for the uniform distribution $p_{v}=1/(2^{t}-1)$ for all $v\in
F_{2}^{t}-\\{0\\}$.

###### Proof.

The assertion is trivial for $t=1$. For $t\geq 2$ put $g(z)=z(1-z)^{t-1}$. For
$t=2$ the second derivative of this function is $-2<0$ and hence it is concave
in $[0,1]$, implying the desired result by Jensen’s inequality. For $t\geq 3$
the derivative and second derivative of $g(z)$ are given by
$g^{\prime}(z)=(1-z)^{t-2}(1-tz)$ and
$g^{\prime\prime}(z)=(1-z)^{t-3}(-2t+2+t(t-1)z)$. Therefore, in $[0,1]$ the
function $g(z)$ is increasing in $[0,1/t)$, attains its maximum at $z=1/t$,
and is decreasing in $[1/t,1]$. It is concave in $[0,2/t)$ and convex in
$[2/t,1]$. Suppose that the sum $\sum_{v}g(p_{v})$ considered in the lemma
attains its maximum at $(p_{v}:v\in F_{2}^{t}-\\{0\\})$ (the maximum is
clearly attained, by compactness). If there is some $p_{v}>1/t$ then since
$2^{t}-1>t$ there is also some $p_{v^{\prime}}<1/t$. Decreasing $p_{v}$ by
${\varepsilon}$ and increasing $p_{v^{\prime}}$ by ${\varepsilon}$, for a
sufficiently small ${\varepsilon}>0$, strictly increases both $g(p_{v})$ and
$g(p_{v^{\prime}})$, contradicting maximality. Therefore $0\leq p_{v}\leq 1/t$
for all $v$. Since the function $g(z)$ is concave in $[0,1/t]$ the maximum
value of $\sum_{v}g(p_{v})$ is obtained when all the values $p_{v}$ are equal,
by Jensen’s Inequality. ∎

######  Corollary 2.4.

Let $t\geq 1$ and let $\\{p_{v}:v\in F_{2}^{t}-\\{0\\}~{}\\}$ be an arbitrary
probability distribution on the nonzero vectors in $F_{2}^{t}$. Then the
probability that a sequence $v_{1},v_{2},\ldots,v_{t}$ of $t$ random vectors,
where each $v_{i}$ is chosen randomly and independently according to this
distribution, forms a basis of $F_{2}^{t}$ is at most $P(t)$, where $P(t)$ is
defined in (1). This is tight and obtained by the uniform distribution on
$F_{2}^{t}-\\{0\\}$.

###### Proof.

We apply induction of $t$ together with the reasoning described in the
derivation of (2) from (1). The result is trivial for $t=1$. Assuming it holds
for $t-1$ we prove it for $t\geq 2$. Choosing the vectors
$v_{1},v_{2},\ldots,v_{t}$ one by one, suppose $v_{1}=v$ (this happens with
probability $p_{v}$.) The vectors $v_{1},v_{2},\ldots,v_{t}$ form a basis iff
no $v_{i}$ for $i\geq 2$ is equal to $v_{1}=v$ (denote this event by $E_{1}$),
and the projections of the vectors $v_{2},\ldots,v_{t}$ on the subspace
orthogonal to $v$ form a basis of this subspace (denote this event by
$E_{2}$). The probability that $v_{1}=v$ and $E_{1}$ holds is
$p_{v}(1-p_{v})^{t-1}$. The conditional probability that given this $E_{2}$
holds is, by the induction hypothesis, at most $P(t-1)$. Summing over $v$ we
conclude that the probability that $v_{1},v_{2},\ldots,v_{t}$ form a basis of
$F_{2}^{t}$ is at most

$(\sum_{v\in F_{2}^{v}-\\{0\\}}p_{v}(1-p_{v})^{t-1})\cdot P(t-1).$

The first factor is at most $(\frac{2^{t}-2}{2^{t}-1})^{t-1}$, by Lemma 2.3.
This and (2) establish the desired inequality for $t$, completing the proof of
the induction step and of the corollary. ∎

For integers $1\leq k\leq d$ let $B(k,d)$ denote the maximum possible number
of non-singular $k$ by $k$ submatrices in a $k$ by $d$ matrix over $F_{2}$.
Therefore, $B(k,d)/{d\choose k}$ is the maximum possible probability that a
set of $k$ distinct columns of such a matrix forms a basis of $F_{2}^{k}$.

######  Lemma 2.5.

  1. 1.

For any fixed $k$ the function $B(k,d)/{d\choose k}$ is monotone decreasing in
$d$ for all $d\geq k$, and is at least $P(k)$ for every admissible $d$.

  2. 2.

For any $1\leq k<d$, $B(k,d)=B(d-k,d)$.

  3. 3.

For $d\geq k^{2}$

$(P(k)\leq)\frac{B(k,d)}{{d\choose k}}\leq\frac{P(k)d^{k}}{k!{d\choose k}}\leq
P(k)(1+\frac{k^{2}}{d-k}).$

  4. 4.

For any $2\leq k\leq d$,

$B(k,d)\leq\lfloor\frac{dB(k-1,d-1)}{k}\rfloor.$

###### Proof.

  1. 1.

Suppose $k\leq d^{\prime}<d$. Let $A$ be a $k$ by $d$ matrix over $F_{2}$
which maximizes the probability that a random set of $k$ of its columns forms
a basis. This probability is the average, over all choices of a $k$ by
$d^{\prime}$ submatrix $A^{\prime}$ of $A$, of the probability that a random
set of $k$ columns of $A^{\prime}$ forms a basis. The fact that

$\frac{B(k,d^{\prime})}{{{d^{\prime}}\choose k}}\geq\frac{B(k,d)}{{{d}\choose
k}}$

follows by considering the submatrix $A^{\prime}$ maximizing this probability.
To prove the inequality $B(k,d)/{d\choose k}\geq P(k)$ consider a random $k$
by $d$ matrix $A$ over $F_{2}$ whose columns are chosen uniformly and
independently in $F_{2}-\\{0\\}$. Each subset of $k$ columns of $A$ is a basis
with probability $P(k)$ and the desired inequality follows by linearity of
expectation.

  2. 2.

For a $k$ by $d$ matrix $A$ of rank $k$ over $F_{2}$, let $A^{\prime}$ denote
the $(k-d)$ by $d$ matrix whose rows form a basis of the subspace orthogonal
to the row-space of $A$. If a set $I^{\prime}$ of $(d-k)$ columns of
$A^{\prime}$ is of rank smaller than $d-k$ then there is a nonzero linear
combination of the rows of $A^{\prime}$ which vanishes on these columns. This
nonzero linear combination is orthogonal to the rows of $A$, providing a
nontrivial linear relation of the columns $I=[d]-I^{\prime}$ of $A$. This
shows that if a set $I^{\prime}$ of $d-k$ columns of $A^{\prime}$ is not
linearly independent, then the set $I=[d]-I^{\prime}$ of $k$-columns of $A$ is
not linearly independent. By symmetry the converse holds as well, and the
desired result follows by considering the matrices realizing $B(k,d)$ and
$B(d-k,d)$.

  3. 3.

Let $A$ be a $k$ by $d$ matrix over $F_{2}$ with $B(k,d)$ nonsingular $k$ by
$k$ submatrices. It is clear that $A$ does not contain the $0$-column (as it
is easy to replace it and increase the number of nonsingular $k$ by $k$
submtarices). Let $\\{p_{v}:v\in F_{2}^{k}-\\{0\\}\\}$ be the probability
distribution assigning to each column of $A$ the same probability $1/d$. By
Corollary 2.4 if we select $k$ columns of $A$ according to this probability
distribution (with repetition), the probability we get a basis is at most
$P(k)$. On the other hand this probability is exactly $k!(B(k,d)/d^{k}$.
Therefore $\frac{k!B(k,d)}{d^{k}}\leq P(k)$ implying that

$\frac{B(k,d)}{{d\choose k}}\leq\frac{P(k)d^{k}}{k!{d\choose k}}\leq
P(k)e^{k(k-1)/2(d-k+1)}\leq P(k)[1+\frac{k^{2}}{d-k}].$

Here we used the fact that $\prod_{i=0}^{k-1}(d/d-i)<e^{k(k-1)/2(d-k+1)}$ and
that $e^{x}\leq 1+2x$ for $x<1$.

  4. 4.

Let $A$ be a $k$ by $d$ matrix with $B(k,d)$ $k$ by $k$ nonsingular
submatrices. Every fixed column $c$ of $A$ can be contained in at most
$B(k-1,d-1)$ such nonsigular matrices corresponding to the $(k-1)$ by $(k-1)$
nonsingular submatrices of the $(k-1)$ by $(d-1)$ matrix obtained from $A$ by
removing $c$ and by replacing each column by its projection on the subspace
orthogonal to $c$. The result thus follows by double counting.

∎

######  Corollary 2.6.

Put $B(d)=\max\\{B(k,d):k\leq d$. Then $B(5)=5$, $B(6)=16$, $B(7)=28$ and
$B(d)=(c+o(1)){d\choose\lfloor d/2\rfloor}$, where $c$ is as in Theorem 1.3
and the $o(1)$-term tends to $0$ as $d$ tends to infinity.

###### Proof.

By Lemma 2.5, part 2, $B(d)=B(k,d)$ for some $k\leq d/2$. For $d=5$ it is
clear that $B(1,5)\leq{5\choose 1}=5<8$. $B(2,5)$ is the number of pairs of
distinct columns of a $2$ by $5$ binary matrix in which every column is one of
the three nonzero vectors of $F_{2}^{2}-\\{0\\}$. This is clearly $8$. The
computation of $B(6)=B(3,6)$ and of $B(7)=B(3,7)$ is also simple and is
obtained by any matrix with distinct columns in $F_{2}^{3}-\\{0\\}$. (The
upper bounds for these quantities also follow by Lemma 2.5, part 4 and the
fact that $B(2,4)=5$).

To estimate $B(d)$ for large $d$ observe, first, that by Lemma 2.5, part 1

$B(d)\geq B(\lfloor d/2\rfloor,d)\geq P(\lfloor d/2\rfloor){d\choose{\lfloor
d/2\rfloor}}>c{d\choose{\lfloor d/2\rfloor}}.$

Next, note that for, say $k<d/4$, $B(k,d)\leq{d\choose{d/4}}$ is (much)
smaller than $c{d\choose{\lfloor d/2\rfloor}}$, so $B(d)=B(k,d)$ for some
$d/4\leq k\leq d/2$. By Lemma 2.5, parts 1, 2 and 3, for any such $k$ (and
$d\geq k+\log k$):

$\frac{B(k,d)}{{d\choose k}}\leq\frac{B(k,k+\log k)}{{{k+\log k}\choose
k}}=\frac{B(\log k,k+\log k)}{{{k+\log k}\choose{\log k}}}\leq P(\log
k)(1+\frac{\log^{2}k}{k})$ $\leq c(1+O(\frac{\log
k}{k}))(1+\frac{\log^{2}k}{k})\leq c(1+O(\frac{\log^{2}d}{d})),$

where in the penultimate inequality we used (3).

Therefore for each $k$ in this range

$B(k,d)\leq c{d\choose k}(1+O(\frac{\log^{2}d}{d})),$

completing the proof. ∎

We are now ready to prove Theorem 1.3.

###### Proof.

The relevant erasure codes are the ones constructed in [4], the novelty here
is only in their analysis. Here is the description of the codes for a given
length $n$. Let $C_{0}$ be the set consisting of the unique vector of weight
$0$ of $Q_{n}$. For each fixed $r$, $1\leq r\leq n$, assign to each coordinate
$i\in[n]$ a uniformly chosen random vector $v_{i}$ in $F_{2}^{r}-\\{0\\}$. Let
$C_{r}$ denote the set of all binary vectors $x$ of length $n$ and Hamming
weight $r$ for which the $r$ vectors $v_{i}$ corresponding to all coordinates
$i$ with $x_{i}=1$ form a basis of $F_{2}^{r}$. Note that the expected
cardinality of $C_{r}$ is ${n\choose r}P(r)>c{n\choose r}$, where $c$ is the
limit defined in Theorem 1.3 (which is roughly $0.29$).

Fix a choice of vectors $v_{i}$ for each $r$ so that the resulting set $C_{r}$
is of cardinality larger than $c{n\choose r}$ and let ${\cal C}$ be the union
of all these sets. Thus $|{\cal C}|>c\cdot 2^{n}$.

Given $d<n$, partition ${\cal C}$ into $d+1$ pairwise disjoint sets, where for
each $0\leq i\leq d$ the $i$-th sets consists of all vectors of ${\cal C}$
whose Hamming weight is $i\bmod(d+1)$. Let ${\cal C}(d)$ denote the largest
among those. Note that $|{\cal C}(d)|>(c/(d+1))2^{n}$ contains a constant
fraction of all binary vectors of length $n$. To complete the proof we prove
an upper bound for the number of vectors of ${\cal C}(d)$ in any subcube of
dimension $d$ of $Q_{n}$.

Fix a subcube $D$ of dimension $d$, and let $I\subset[n]$ be the set of the
$d$ coordinates that vary in the subcube. Observe that by the choice of the
Hamming weights of the vectors in ${\cal C}(d)$, $D$ can contain only vectors
of ${\cal C}(d)$ of one specific Hamming weight. Denote this weight by $r$.
Let $x$ be the common projection of all points of $D$ on $[n]-I$ and suppose
its Hamming weight is $r-k$. Thus, each of the projections $y$ of all the
vectors of ${\cal C}(d)$ that lie in $D$ on $I$ has weight $k$. Let
$v_{1},v_{2},\ldots,v_{r-k}$ be the binary vectors in $F_{2}^{r}-\\{0\\}$ that
correspond to the indices $i$ where $x_{i}=1$. Then, by the construction of
$C(r)$, these vectors are linearly independent. Moreover, for any vector $y$
that appears as a projection above, the set of $k$ vectors $v_{j}\in
F_{2}^{r}-\\{0\\}$ that correspond to the coordinates $j$ in which $y_{j}=1$
complete the vectors $v_{1},v_{2},\ldots,v_{r-k}$ to a basis of $F_{2}^{r}$.
This means that these vectors form a basis of the space of cosets of
$W=\mbox{span}(v_{1},v_{2},\ldots,v_{r-k})$ in $F_{2}^{r}$. This space is
isomorphic to $F_{2}^{k}$. It follows that the number of such projections $y$
is at most $B(k,d)$.

We have thus proved that the number of vectors of ${\cal C}(d)$ that lie in
$D$ is at most the maximum, over $k\leq d$, of the quantity $B(k,d)$, that is,
at most $B(d)$. The desired upper bound thus follows from the last Corollary.
∎

###  2.4 Lagrangians

Some of the discussion in the previous subsection is equivalent to the
computation of the Lagrangians of certain natural hypergraphs. Although this
is not needed for the results here, we briefly describe the connection which
may be of independent interest.

The Lagrangian Polynomial of a $t$-uniform hypergraph $H=(V,E)$ on a vertex
set $V=\\{1,2,\ldots,n\\}$ is the polynomial

$P_{H}(x_{1},x_{2},\ldots,x_{n})=\sum_{e\in E}\prod_{j\in e}x_{j}.$

The Lagrangian $\lambda(H)$ of $H$ is the maximum value of
$P_{H}(x_{1},\ldots,x_{n})$ over the simplex $\\{x_{i}\geq
0,\sum_{i}x_{i}=1\\}$ (this maximum is attained as the simplex is compact).

Lagrangians of hypergraphs were first considered by Frankl and Füredi [13] and
by Sidorenko [16], extending the application of this notion for graphs,
initiated by Motzkin and Straus [14].

For each $t\geq 1$ let $B_{t}$ denote the $t$-uniform hypergraph on the vertex
set $V=F_{2}^{t}-\\{0\\}$ of the $2^{t}-1$ nonzero elements of the vector
space of dimension $t$ over $F_{2}$, whose edges are all bases of this vector
space. Let $\lambda(B_{t})$ denote the Lagrangian of this hypergraph.
Trivially $\lambda(B_{1})=1$ and $\lambda(B_{2})=1/3$. By Corollary 2.4 for
every fixed $t$, the value of the Lagrangian of $B_{t}$ satisfies
$\lambda(B_{t})=P(t)/t!$. Therefore $\lambda(B_{t})=(c+o(1))/t!$ where $c$ is
as in Theorem 1.3 and the $o(1)$-term tends to $0$ as $t$ tends to infinity.

##  3 Concluding remarks

  * •

By Theorem 1.3 $L(5)=8$. Therefore, for any arbitrarily small
${\varepsilon}>0$, any set of at least an ${\varepsilon}$-fraction of the
vertices of the $n$-cube for $n>n({\varepsilon})$ contains at least $8$
vertices in some $5$-dimensional subcube. On the other hand, there is a set of
at least $c/6>0.04$-fraction of the vertices that does not contain more than
$8$ vertices of each such subcube. It is easy to improve this lower bound to
$c/4>0.07$, since we can take the union of the subsets $C(r)$ for all Hamming
weights $r$ congruent to a constant modulo $4$, instead of a constant modulo
$6$. It is easy to check that this still contains at most $8$ vertices of any
$5$-subcube, since the sum of cardinalities of any two quantitites $B(k,5)$
for values of $k$ that differ by at least $4$ is at most $8$. Similarly, for
large $d$ and any small ${\varepsilon}>0$, the code containing all collections
$C(r)$ for Hamming weights $r$ congruent to a constant modulo
$b({\varepsilon})\sqrt{d}$ has a fraction of
$\Omega_{{\varepsilon}}(1/\sqrt{d})$ of all vertices of the cube and contains
at most $(c+{\varepsilon}){d\choose{\lfloor d/2\rfloor}}$ vertices each
$d$-subcube.

  * •

As mentioned in the proof of Corollary 2.6 it is not difficult to find the
exact values of $B(6)=16$ and $B(7)=28$. With a bit more work one can
determine $B(d)$ precisely for larger (small) values of $d$, but since there
is no reason to believe that these provide a tight bound for $L(d)$ we have
not done that.

  * •

The problem of determining the precise value of $L(d)$ for $d>5$ remains open.
It will be interesting to close the gap between the upper and lower bounds for
these quantities. Another problem is the estimation of the largest possible
cardinality of a $(d,L(d),n)$-code. As mentioned above, for $d=5$ there is a
$(5,8,n)$-code containing more than $c/4\cdot 2^{n}>0.07\cdot 2^{n}$ of the
binary vectors of length $n$, but there is no reason to believe that this is
tight. The analogous problem for $d=4$, that is, determining the maximum
possible fraction of the set of $n$-vectors in a $(4,5,n)$-code, is also open.
The lower bound here is $c/3>0.09$ and the trivial upper bound is $5/16$. For
smaller values of $d$ the analogous problem is not difficult. The even vectors
are $1/2$ of the vectors, and form a $(1,1,n)$-code and also a $(2,2,n)$-code,
and $1/2$ is clearly optimal here. For $d=3$ the collection of all vectors of
Hamming weight constant modulo $3$ provide a $(3,3,n)$-code with at least
$1/3$ of all vectors. This $1/3$ is asymptotically optimal by the following
argument. Let ${\cal C}$ be a collection of binary vectors of length $n$. If
there are more than $2^{n-1}/n$ binary vectors $v$ of length $n-1$ so that
both $v0$ and $v1$ are in ${\cal C}$, then there are two such vectors
$v,v^{\prime}$ which differ by at most $2$ coordinates, and in this case
$\\{v0,v1,v^{\prime}0,v^{\prime}1\\}$ all lie in the same $3$-cube, showing
that ${\cal C}$ is not a $(3,3,n)$-code. If not, and, say, $|{\cal
C}|/2^{n}>(1/3+1/n)$ then the projection of ${\cal C}$ on the first
$(n-1)$-coordinates is of cardinality exceeding $\lceil 2^{n}/3\rceil$. By the
result of [11] and [8] this projection contains a full $2$-cube, implying that
${\cal C}$ contains at least $4$ points in a $3$-cube and showing it is not a
$(3,3,n)$-code.

Acknowledgment I would like to thank Matija Bucić, Maria-Romina Ivan and
Robert Johnson for helpful comments.

## References

  * [1] Noga Alon, Anja Krech and Tibor Szabó, Turán’s theorem in the hypercube, SIAM J. on Disc. Math. 21 (2007), 66-72.
  * [2] Avraham Ben-Aroya, Dean Doron and Amnon Ta-Shma Near-Optimal Erasure List-Decodable Codes, Proc. CCC 2020, 1:1–1:27
  * [3] Béla Bollobás, Imre Leader and Claudia Malvenuto, Daisies and other Turán problems, Combin. Probab. Comput. 20 (2011), no. 5, 743–747.
  * [4] David Ellis, Maria-Romina Ivan and Imre Leader, Turań densities for daisies and hypercubes. arXiv:2401.16289, 2024.
  * [5] David Ellis and Dylan King, Lower bounds for the Turán densities of daisies, Electron. J. Combin. 30 (2023), no. 4, Paper No. 4.4, 11 pp.
  * [6] Venkatesan Guruswami, List decoding from erasures: Bounds and code constructions, IEEE Transactions on Information Theory, 49(11):2826-2833, 2003.
  * [7] Heiko Harborth and Hauke Nienborg, Some further vertex Turán numbers for cube graphs, Utilitas Math. 75 (2008), 83–87.
  * [8] Karen Anne Johnson and Roger Entringer, Largest induced subgraphs of the n-cube that contain no 4-cycles, J. Combin. Theory Ser. B 46 (1989), no. 3, 346–355.
  * [9] Robert Johnson, Private communication, 2024.
  * [10] Robert Johnson and John Talbot, Vertex Turán problems in the hypercube, J. Combin. Theory Ser. A 117 (2010), no. 4, 454-465.
  * [11] Alexandr Kostochka, Piercing the edges of the n-dimensional unit cube, (in Russian), Diskret. Analiz 1976, 55–64.
  * [12] Paul Erdős, On extremal problems of graphs and generalized graphs, Israel J. Math. 2 (1964), 183–190.
  * [13] Peter Frankl and Zoltán Füredi, Extremal problems and the Lagrange function for hypergraphs, Bull. Inst. Math. Acad. Sinica 16 (1988), no. 4, 305–313.
  * [14] Theodore S. Motzkin and Ernst Gabor Straus, Maxima for graphs and a new proof of a theorem of Turán, Canadian J. Math. 17 (1965), 533–540.
  * [15] Morris Plotkin, Binary codes with specified minimum distance, IRE Transactions on Information Theory 6 (4) (1960), 445–450.
  * [16] Alexander Sidorenko, On the maximal number of edges in a homogeneous hypergraph that does not contain prohibited subgraphs (Russian), Mat. Zametki 41 (1987), no. 3, 433–455.