An official website of the United States government
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
This content will become publicly available on September 1, 2026
Weighted Turán Theorems With Applications to Ramsey‐Turán Type of Problems
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
- Award ID(s):
- 2152490
- PAR ID:
- 10615926
- Publisher / Repository:
- Wiley
- Date Published:
- Journal Name:
- Journal of Graph Theory
- Volume:
- 110
- Issue:
- 1
- ISSN:
- 0364-9024
- Page Range / eLocation ID:
- 59 to 71
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Daisies are a special type of hypergraph introduced by Bollobás, Leader and Malvenuto. An$$r$$-daisy determined by a pair of disjoint sets$$K$$and$$M$$is the$$(r+|K|)$$-uniform hypergraph$$\{K\cup P\,{:}\, P\in M^{(r)}\}$$. Bollobás, Leader and Malvenuto initiated the study of Turán type density problems for daisies. This paper deals with Ramsey numbers of daisies, which are natural generalisations of classical Ramsey numbers. We discuss upper and lower bounds for the Ramsey number of$$r$$-daisies and also for special cases where the size of the kernel is bounded.more » « less
-
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
-
The planar Turán number $$\textrm{ex}_{\mathcal{P}}(C_{\ell},n)$$ is the largest number of edges in an $$n$$-vertex planar graph with no $$\ell$$-cycle. For each $$\ell\in \{3,4,5,6\}$$, upper bounds on $$\textrm{ex}_{\mathcal{P}}(C_{\ell},n)$$ are known that hold with equality infinitely often. Ghosh, Győri, Martin, Paulos, and Xiao [arXiv:2004.14094] conjectured an upper bound on $$\textrm{ex}_{\mathcal{P}}(C_{\ell},n)$$ for every $$\ell\ge 7$$ and $$n$$ sufficiently large. We disprove this conjecture for every $$\ell\ge 11$$. We also propose two revised versions of the conjecture.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 ?more » « less
