Title: Erasure list-decodable codes and Turán hypercube problems
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 augmentations we obtain improved bounds for some of these problems.  more » « less
Award ID(s):
2154082
PAR ID:
10580872
Author(s) / Creator(s):
Publisher / Repository:
Science Direct - Elsevier
Date Published:
Journal Name:
Finite Fields and Their Applications
Volume:
100
Issue:
C
ISSN:
1071-5797
Page Range / eLocation ID:
102513
Subject(s) / Keyword(s):
Sponsoring Org:
National Science Foundation
More Like this
  1. ABSTRACT We study extensions of Turán Theorem in edge‐weighted settings. A particular case of interest is when constraints on the weight of an edge come from the order of the largest clique containing it. These problems are motivated by Ramsey‐Turán type problems. Some of our proofs are based on the method of graph Lagrangians, while the other proofs use flag algebras. Using these results, we prove several new upper bounds on the Ramsey‐Turán density of cliques. Other applications of our results are in a recent paper of Balogh, Chen, McCourt, and Murley. 
    more » « less
  2. Abstract Theplanar Turán numberof a graph is the maximum number of edges in an ‐vertex planar graph without as a subgraph. Let denote the cycle of length . The planar Turán number is known for . We show that dense planar graphs with a certain connectivity property (known as circuit graphs) contain large near triangulations, and we use this result to obtain consequences for planar Turán numbers. In particular, we prove that there is a constant so that for all and . When this bound is tight up to the constant and proves a conjecture of Cranston, Lidický, Liu, and Shantanam. 
    more » « less
  3. Abstract We showthat for every integer $$k\geqslant 3$$ the set of Turán densities of $$k$$-uniform hypergraphs has an accumulation point in $[0,1)$. In particular, $1/2$ is an accumulation point for the set of Turán densities of $$3$$-uniform hypergraphs. 
    more » « less
  4. Abstract A long-standing conjecture of Erdős and Simonovits asserts that for every rational number $$r\in (1,2)$$ there exists a bipartite graph H such that $$\mathrm{ex}(n,H)=\Theta(n^r)$$ . So far this conjecture is known to be true only for rationals of form $1+1/k$ and $2-1/k$ , for integers $$k\geq 2$$ . In this paper, we add a new form of rationals for which the conjecture is true: $2-2/(2k+1)$ , for $$k\geq 2$$ . This in turn also gives an affirmative answer to a question of Pinchasi and Sharir on cube-like graphs. Recently, a version of Erdős and Simonovits $$^{\prime}$$ s conjecture, where one replaces a single graph by a finite family, was confirmed by Bukh and Conlon. They proposed a construction of bipartite graphs which should satisfy Erdős and Simonovits $$^{\prime}$$ s conjecture. Our result can also be viewed as a first step towards verifying Bukh and Conlon $$^{\prime}$$ s conjecture. We also prove an upper bound on the Turán number of theta graphs in an asymmetric setting and employ this result to obtain another new rational exponent for Turán exponents: $r=7/5$ . 
    more » « less
  5. Abstract The Pósa–Seymour conjecture determines the minimum degree threshold for forcing the$$k$$th power of a Hamilton cycle in a graph. After numerous partial results, Komlós, Sárközy, and Szemerédi proved the conjecture for sufficiently large graphs. In this paper, we focus on the analogous problem for digraphs and for oriented graphs. We asymptotically determine the minimum total degree threshold for forcing the square of a Hamilton cycle in a digraph. We also give a conjecture on the corresponding threshold for$$k$$th powers of a Hamilton cycle more generally. For oriented graphs, we provide a minimum semi-degree condition that forces the$$k$$th power of a Hamilton cycle; although this minimum semi-degree condition is not tight, it does provide the correct order of magnitude of the threshold. Turán-type problems for oriented graphs are also discussed. 
    more » « less