 Award ID(s):
 1839918
 NSFPAR ID:
 10395453
 Date Published:
 Journal Name:
 The Electronic Journal of Combinatorics
 Volume:
 29
 Issue:
 4
 ISSN:
 10778926
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

One of the most intruguing conjectures in extremal graph theory is the conjecture of Erdős and Sós from 1962, which asserts that every $n$vertex graph with more than $\frac{k1}{2}n$ edges contains any $k$edge tree as a subgraph. Kalai proposed a generalization of this conjecture to hypergraphs. To explain the generalization, we need to define the concept of a tight tree in an $r$uniform hypergraph, i.e., a hypergraph where each edge contains $r$ vertices. A tight tree is an $r$uniform hypergraph such that there is an ordering $v_1,\ldots,v_n$ of its its vertices with the following property: the vertices $v_1,\ldots,v_r$ form an edge and for every $i>r$, there is a single edge $e$ containing the vertex $v_i$ and $r1$ of the vertices $v_1,\ldots,v_{i1}$, and $e\setminus\{v_i\}$ is a subset of one of the edges consisting only of vertices from $v_1,\ldots,v_{i1}$. The conjecture of Kalai asserts that every $n$vertex $r$uniform hypergraph with more than $\frac{k1}{r}\binom{n}{r1}$ edges contains every $k$edge tight tree as a subhypergraph. The recent breakthrough results on the existence of combinatorial designs by Keevash and by Glock, Kühn, Lo and Osthus show that this conjecture, if true, would be tight for infinitely many values of $n$ for every $r$ and $k$.The article deals with the special case of the conjecture when the sought tight tree is a path, i.e., the edges are the $r$tuples of consecutive vertices in the above ordering. The case $r=2$ is the famous ErdősGallai theorem on the existence of paths in graphs. The case $r=3$ and $k=4$ follows from an earlier work of the authors on the conjecture of Kalai. The main result of the article is the first nontrivial upper bound valid for all $r$ and $k$. The proof is based on techniques developed for a closely related problem where a hypergraph comes with a geometric structure: the vertices are points in the plane in a strictly convex position and the sought path has to zigzag beetwen the vertices.more » « less

Abstract May the triforce be the 3uniform hypergraph on six vertices with edges {123′, 12′3, 1′23}. We show that the minimum triforce density in a 3uniform hypergraph of edge density δ is δ 4– o (1) but not O ( δ 4 ). Let M ( δ ) be the maximum number such that the following holds: for every ∊ > 0 and $G = {\mathbb{F}}_2^n$ with n sufficiently large, if A ⊆ G × G with A ≥ δ  G  2 , then there exists a nonzero “popular difference” d ∈ G such that the number of “corners” ( x , y ), ( x + d , y ), ( x , y + d ) ∈ A is at least ( M ( δ )–∊) G  2 . As a corollary via a recent result of Mandache, we conclude that M ( δ ) = δ 4– o (1) and M ( δ ) = ω ( δ 4 ). On the other hand, for 0 < δ < 1/2 and sufficiently large N , there exists A ⊆ [ N ] 3 with  A  ≥ δN 3 such that for every d ≠ 0, the number of corners ( x , y , z ), ( x + d , y , z ), ( x , y + d , z ), ( x , y , z + d ) ∈ A is at most δ c log(1/ δ ) N 3 . A similar bound holds in higher dimensions, or for any configuration with at least 5 points or affine dimension at least 3.more » « less

Abstract Let
denote the matrix multiplication tensor (and write$M_{\langle \mathbf {u},\mathbf {v},\mathbf {w}\rangle }\in \mathbb C^{\mathbf {u}\mathbf {v}}{\mathord { \otimes } } \mathbb C^{\mathbf {v}\mathbf {w}}{\mathord { \otimes } } \mathbb C^{\mathbf {w}\mathbf {u}}$ ), and let$M_{\langle \mathbf {n} \rangle }=M_{\langle \mathbf {n},\mathbf {n},\mathbf {n}\rangle }$ denote the determinant polynomial considered as a tensor. For a tensor$\operatorname {det}_3\in (\mathbb C^9)^{{\mathord { \otimes } } 3}$ T , let denote its border rank. We (i) give the first handcheckable algebraic proof that$\underline {\mathbf {R}}(T)$ , (ii) prove$\underline {\mathbf {R}}(M_{\langle 2\rangle })=7$ and$\underline {\mathbf {R}}(M_{\langle 223\rangle })=10$ , where previously the only nontrivial matrix multiplication tensor whose border rank had been determined was$\underline {\mathbf {R}}(M_{\langle 233\rangle })=14$ , (iii) prove$M_{\langle 2\rangle }$ , (iv) prove$\underline {\mathbf {R}}( M_{\langle 3\rangle })\geq 17$ , improving the previous lower bound of$\underline {\mathbf {R}}(\operatorname {det}_3)=17$ , (v) prove$12$ for all$\underline {\mathbf {R}}(M_{\langle 2\mathbf {n}\mathbf {n}\rangle })\geq \mathbf {n}^2+1.32\mathbf {n}$ , where previously only$\mathbf {n}\geq 25$ was known, as well as lower bounds for$\underline {\mathbf {R}}(M_{\langle 2\mathbf {n}\mathbf {n}\rangle })\geq \mathbf {n}^2+1$ , and (vi) prove$4\leq \mathbf {n}\leq 25$ for all$\underline {\mathbf {R}}(M_{\langle 3\mathbf {n}\mathbf {n}\rangle })\geq \mathbf {n}^2+1.6\mathbf {n}$ , where previously only$\mathbf {n} \ge 18$ was known. The last two results are significant for two reasons: (i) they are essentially the first nontrivial lower bounds for tensors in an “unbalanced” ambient space and (ii) they demonstrate that the methods we use (border apolarity) may be applied to sequences of tensors.$\underline {\mathbf {R}}(M_{\langle 3\mathbf {n}\mathbf {n}\rangle })\geq \mathbf {n}^2+2$ The methods used to obtain the results are new and “nonnatural” in the sense of Razborov and Rudich, in that the results are obtained via an algorithm that cannot be effectively applied to generic tensors. We utilize a new technique, called
border apolarity developed by Buczyńska and Buczyński in the general context of toric varieties. We apply this technique to develop an algorithm that, given a tensorT and an integerr , in a finite number of steps, either outputs that there is no border rankr decomposition forT or produces a list of all normalized ideals which could potentially result from a border rank decomposition. The algorithm is effectively implementable whenT has a large symmetry group, in which case it outputs potential decompositions in a natural normal form. The algorithm is based on algebraic geometry and representation theory. 
Let $H$ and $F$ be hypergraphs. We say $H$ {\em contains $F$ as a trace} if there exists some set $S \subseteq V(H)$ such that $H_S:=\{E\cap S: E \in E(H)\}$ contains a subhypergraph isomorphic to $F$. In this paper we give an upper bound on the number of edges in a $3$uniform hypergraph that does not contain $K_{2,t}$ as a trace when $t$ is large. In particular, we show that $$\lim_{t\to \infty}\lim_{n\to \infty} \frac{\mathrm{ex}(n, \mathrm{Tr}_3(K_{2,t}))}{t^{3/2}n^{3/2}} = \frac{1}{6}.$$ Moreover, we show $\frac{1}{2} n^{3/2} + o(n^{3/2}) \leqslant \mathrm{ex}(n, \mathrm{Tr}_3(C_4)) \leqslant \frac{5}{6} n^{3/2} + o(n^{3/2})$.more » « less

Abstract Let denote the complete 3‐uniform hypergraph on vertices and the 3‐uniform hypergraph on vertices consisting of all edges incident to a given vertex. Whereas many hypergraph Ramsey numbers grow either at most polynomially or at least exponentially, we show that the off‐diagonal Ramsey number exhibits an unusual intermediate growth rate, namely,
for some positive constants and . The proof of these bounds brings in a novel Ramsey problem on grid graphs which may be of independent interest: what is the minimum such that any 2‐edge‐coloring of the Cartesian product contains either a red rectangle or a blue ?