An official website of the United States government
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
This content will become publicly available on December 1, 2025
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
- 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
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
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 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
