Zach Hunter
YOU?
Author Swipe
An improved construction for the triangle removal lemma Open
We construct $n$-vertex graphs $G$ where $εn^2$ edges must be deleted to become triangle-free, which contain less than $ε^{(C_{\text{new}}-o(1))\log_2 1/ε}n^3$ triangles for $C_{\text{new}}= \frac{1}{4\log_2(4/3)} \approx 1.6601$. Previous…
$C_4$-free subgraphs of high degree with geometric applications Open
The Zarankiewicz problem, a cornerstone problem in extremal graph theory, asks for the maximum number of edges in an $n$-vertex graph that does not contain the complete bipartite graph $K_{s,s}$. While the problem remains widely open in th…
Lower bounds for Ramsey numbers of bounded degree hypergraphs Open
We prove that, for all $k \ge 3,$ and any integers $Δ, n$ with $n \ge Δ,$ there exists a $k$-uniform hypergraph on $n$ vertices with maximum degree at most $Δ$ whose $4$-color Ramsey number is at least $\mathrm{tw}_k(c_k Δ) \cdot n$, for s…
Lower bounds for multicolor van der Waerden numbers Open
We give an exponential improvement to the diagonal van der Waerden numbers for r ≥ 5 colors.
Induced Subdivisions in <i>K</i> <i>s,s</i>-Free Graphs With Polynomial Average Degree Open
In this paper we prove that for every $s\geqslant 2$ and every graph $H$ the following holds. Let $G$ be a graph with average degree $\Omega _{H}(s^{A|H|^{2}})$, for some absolute constant $A>0$, then $G$ either contains a $K_{s,s}$ or an …
On the diameter of finite Sidon sets Open
We prove that the diameter of a Sidon set (also known as a Babcock sequence, Golomb ruler, or $$B_2$$ set) with $$k$$ elements is at least $$k^2-b k^{3/2}-O(k)$$ where $$b\le 1.96365$$ , a comparatively large improvement on past results. E…
Kővári-Sós-Turán theorem for hereditary families Open
The celebrated Kővári-Sós-Turán theorem states that any n-vertex graph containing no copy of the complete bipartite graph Ks,s has at most Os(n2−1/s) edges. In the past two decades, motivated by the applications in discrete geometry and st…
Almost-full transversals in equi-$n$-squares Open
In 1975, Stein made a wide generalisation of the Ryser-Brualdi-Stein conjecture on transversals in Latin squares, conjecturing that every equi-$n$-square (an $n\times n$ array filled with $n$ symbols where each symbol appears exactly $n$ t…
Monochromatic odd cycles in edge-coloured complete graphs Open
It is easy to see that every $q$-edge-colouring of the complete graph on $2^q+1$ vertices must contain a monochromatic odd cycle. A natural question raised by Erdős and Graham in $1973$ asks for the smallest $L(q)$ such that every $q$-edge…
Long induced paths in $K_{s, s}$-free graphs Open
More than 40 years ago, Galvin, Rival and Sands showed that every $K_{s, s}$-free graph containing an $n$-vertex path must contain an induced path of length $f(n)$, where $f(n)\to \infty$ as $n\to \infty$. Recently, it was shown by Duron, …
Disjoint pairs in set systems and combinatorics of low rank matrices Open
We study and solve several problems in two closely related settings: set families in $2^{[n]}$ with many disjoint pairs of sets and low rank matrices with many zero entries. - More than 40 years ago, Daykin and Erdős asked for the maximum …
Blowups of triangle-free graphs Open
A highly influential result of Nikiforov states that if an $n$-vertex graph $G$ contains at least $γn^h$ copies of a fixed $h$-vertex graph $H$, then $G$ contains a blowup of $H$ of order $Ω_{γ,H}(\log n)$. While the dependence on $n$ is o…
Improving Behrend's construction: Sets without arithmetic progressions in integers and over finite fields Open
We prove new lower bounds on the maximum size of subsets $A\subseteq \{1,\dots,N\}$ or $A\subseteq \mathbb{F}_p^n$ not containing three-term arithmetic progressions. In the setting of $\{1,\dots,N\}$, this is the first improvement upon a c…
Induced Ramsey problems for trees and graphs with bounded treewidth Open
The induced $q$-color size-Ramsey number $\hat{r}_{\text{ind}}(H;q)$ of a graph $H$ is the minimal number of edges a host graph $G$ can have so that every $q$-edge-coloring of $G$ contains a monochromatic copy of $H$ which is an induced su…
Kővári-Sós-Turán theorem for hereditary families Open
The celebrated Kővári-Sós-Turán theorem states that any $n$-vertex graph containing no copy of the complete bipartite graph $K_{s,s}$ has at most $O_s(n^{2-1/s})$ edges. In the past two decades, motivated by the applications in discrete ge…
Lunar Rover Convertible Mobility System Open
The Lunar Rover Convertible Mobility System (LRCMS) is a convertible chassis designed to be used for lunar missions into permanently shadowed regions (PSRs) of the moon, primarily consisting of steep lunar craters. This design utilizes fle…
On the Diameter of Finite Sidon Sets Open
We prove that the diameter of a Sidon set (also known as a Babcock sequence, Golomb ruler, or $B_2$ set) with $k$ elements is at least $k^2-b k^{3/2}-O(k)$ where $b\le 1.96365$, a comparatively large improvement on past results. Equivalent…
Induced subdivisions in $K_{s,s}$-free graphs with polynomial average degree Open
In this paper we prove that for every $s\geq 2$ and every graph $H$ the following holds. Let $G$ be a graph with average degree $Ω_H(s^{C|H|^2})$, for some absolute constant $C>0$, then $G$ either contains a $K_{s,s}$ or an induced subdivi…
An asymptotically tight lower bound for superpatterns with small alphabets Open
A permutation \(\sigma \in S_n\) is a \(k\)-superpattern (or \(k\)-universal) if it contains each \({\tau \in S_k}\) as a pattern. This notion of "superpatterns" can be generalized to words on smaller alphabets, and several questions about…
On off-diagonal Ramsey numbers for vector spaces over $\mathbb{F}_{2}$ Open
For every positive integer $d$, we show that there must exist an absolute constant $c > 0$ such that the following holds: for any integer $n \geq cd^{7}$ and any red-blue coloring of the one-dimensional subspaces of $\mathbb{F}_{2}^{n}$, t…
On a method of Alweiss Open
Recently, Alweiss settled Hindman's conjecture over the rationals. In this paper, we provide our own exposition of Alweiss' result, and show how to modify his method to also show that sums of distinct products are partition regular over th…
Induced $C_4$-free subgraphs with large average degree Open
We prove that there exists a constant $C$ so that, for all $s,k \in \mathbb{N}$, if $G$ has average degree at least $k^{Cs^3}$ and does not contain $K_{s,s}$ as a subgraph then it contains an induced subgraph which is $C_4$-free and has av…
A notion of twins Open
Given a combinatorial structure, a ``twin'' is a pair of disjoint substructures which are isomorphic (or look the same in some sense). In recent years, there have been many problems about finding large twins in various combinatorial struct…
Lower bounds for multicolor van der Waerden numbers Open
We give an exponential improvement to the diagonal van der Waerden numbers for $r\ge 5$ colors.
A new upper bound to (a variant of) the pancake problem Open
The "pancake problem" asks how many prefix reversals are sufficient to sort any permutation $π\in \mathcal{S}_k$ to the identity. We write $f(k)$ to denote this quantity. The best known bounds are that $\frac{15}{14}k -O(1) \le f(k)\le \fr…
Corner-free sets via the torus Open
A corner is a triple of points in $\Bbb{Z}^2$ of the form $(x,y),(x+d,y),(x,y+d)$ where $d\neq 0$. One can think of them as being 2D-analogues to 3-term arithmetic progressions. In this short note, we extend ideas of Green-Wolf from this l…
A short proof that $w(3,k) \ge (1-o(1))k^2$ Open
Here we present a short proof that the two-color van der Waerden number $w(3,k)$ is bounded from below by $(1-o(1))k^2$. Previous work has already shown that a superpolynomial lower bound holds for $w(3,k)$. However, we believe our result …
A note on large induced subgraphs with prescribed residues in bipartite graphs Open
It was proved by Scott that for every $k\ge2$, there exists a constant $c(k)>0$ such that for every bipartite $n$-vertex graph $G$ without isolated vertices, there exists an induced subgraph $H$ of order at least $c(k)n$ such that $\textrm…
Optimally reconstructing caterpillars Open
For a graph $G$, the $\ell$-deck of $G$ is the multiset of induced subgraphs on $G$ having $\ell$ vertices. Recently, Groenland et al. proved that any tree can be reconstructed from its $(8/9+o(1))n$-deck. For the particular case of caterp…
Improved lower bounds for van der Waerden numbers Open
Recently, Ben Green proved that the two-color van der Waerden number $w(3,k)$ is bounded from below by $k^{b_0(k)}$ where $b_0(k) = c_0\left(\frac{\log k }{\log \log k}\right)^{1/3}$. We prove a new lower bound of $k^{b(k)}$ with $b(k) = \…