A code $\mathcal{C}:\{0,1\}^{k} \rightarrow\{0,1\}^{n}$ is a q-query locally decodable code (q-LDC) if one can recover any chosen bit $b_{i}$ of the message $b \in\{0,1\}^{k}$ with good confidence by querying a corrupted string $\tilde{x}$ of the codeword $x=\mathcal{C}(b)$ in at most q coordinates. For 2 queries, the Hadamard code is a 2-LDC of length $n=2^{k}$, and this code is in fact essentially optimal [1], [2]. For $q \geq 3$, there is a large gap in our understanding: the best constructions achieve $n=\exp \left(k^{o(1)}\right)$, while prior to the recent work of [3], the best lower bounds were $n \geq \tilde{\Omega}\left(k^{\frac{q}{q-2}}\right)$ for q even and $n \geq \tilde{\Omega}\left(k^{\frac{q+1}{q-1}}\right)$ for q odd. The recent work of [3] used techniques from semirandom XOR refutation to prove a lower bound of $n \geq \tilde{\Omega}\left(k^{3}\right)$ for q = 3, thus achieving the “ $k^{\frac{q}{q-2}}$ bound” for an odd value of q. However, their proof does not extend to any odd $q \geq 5$. In this paper, we prove a q-LDC lower bound of $n \geq \tilde{\Omega}\left(k^{\frac{q}{q-2}}\right)$ for any odd q. Our key technical idea is the use of an imbalanced bipartite Kikuchi graph, which gives a simpler method to analyze spectral refutations of odd arity XOR without using the standard “Cauchy-Schwarz trick” ― a trick that typically produces random matrices with nontrivially correlated entries and makes the analysis for odd arity XOR significantly more complicated than even arity XOR.

Abstract. In 1984, Erdős conjectured that the number of pentagons in any triangle-free graph on [Formula: see text] vertices is at most [Formula: see text], which is sharp by the balanced blow-up of a pentagon. This was proved by Grzesik, and independently by Hatami et al. As an extension of this result for longer cycles, we prove that for each odd [Formula: see text], the balanced blow-up of [Formula: see text] (uniquely) maximizes the number of [Formula: see text]-cycles among [Formula: see text]-free graphs on [Formula: see text] vertices, as long as [Formula: see text] is sufficiently large. We also show that this is no longer true if [Formula: see text] is not assumed to be sufficiently large. Our result strengthens results of Grzesik and Kielak who proved that for each odd [Formula: see text], the balanced blow-up of [Formula: see text] maximizes the number of [Formula: see text]-cycles among graphs with a given number of vertices and no odd cycles of length less than [Formula: see text]. We further show that if [Formula: see text] and [Formula: see text] are odd and [Formula: see text] is sufficiently large compared to [Formula: see text], then the balanced blow-up of [Formula: see text] does not asymptotically maximize the number of [Formula: see text]-cycles among [Formula: see text]-free graphs on [Formula: see text] vertices. This disproves a conjecture of Grzesik and Kielak.

In this paper we study the fundamental problem of finding small dense subgraphs in a given graph. For a real number s > 2, we prove that every graph on n vertices with average degree at least d contains a subgraph of average degree at least s on at most vertices. This is optimal up to the polylogarithmic factor, and resolves a conjecture of Feige and Wagner. * The full version of the paper can be accessed at https://arxiv.org/abs/2207.02170

Abstract The long-standing Erdős–Faber–Lovász conjecture states that every n-uniform linear hypergaph with n edges has a proper vertex-coloring using n colors. In this paper we propose an algebraic framework to the problem and formulate a corresponding stronger conjecture. Using the Combinatorial Nullstellensatz, we reduce the Erdős–Faber–Lovász conjecture to the existence of non-zero coefficients in certain polynomials. These coefficients are in turn related to the number of orientations with prescribed in-degree sequences of some auxiliary graphs. We prove the existence of certain orientations, which verifies a necessary condition for our algebraic approach to work.

The $r$-blowup of a graph $F$, denoted by $F[r]$, is the graph obtained by replacing the vertices and edges of $F$ with independent sets of size $r$ and copies of $K_{r,r}$, respectively. For bipartite graphs $F$, very little is known about the order of magnitude of the Turán number of $F[r]$. In this paper we prove that ${ex}(n,C_6[2])=O(n^{5/3})$ and, more generally, for any positive integer $t$, ${ex}(n,\theta_{3,t}[2])=O(n^{5/3})$. This is tight when $t$ is sufficiently large.

For a graph $F$, the $k$-subdivision of $F$, denoted $F^k$, is the graph obtained by replacing the edges of $F$ with internally vertex-disjoint paths of length $k$. In this paper, we prove that ${ex}(n,K_{s,t}^k)=O(n^{1+\frac{s-1}{sk}})$, which is tight for $t$ sufficiently large. This settles a conjecture of Conlon--Janzer--Lee, and improves on a substantial body of work by Conlon--Janzer--Lee and Jiang--Qiu.