Generating non-jumping numbers of hypergraphs
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
The concept of jump concerns the distribution of Tur\'an densities. A number $\alpha\in[0,1)$ is a \emph{jump} for $r$ if there exists a constant $c>0$ such that if the Tur\'an density of a family $\mathscr{F}$ of $r$-uniform graphs is greater than $\alpha$, then the Tur\'an density of $\mathscr{F}$ is at least $\alpha+c$. To determine whether a number is a jump or non-jump has been a challenging problem in extremal hypergraph theory. In this paper, we give a way to generate non-jumps for hypergraphs. We show that if $\alpha,\beta$ are non-jumps for $r_1,r_2\geq2$ respectively, then $\frac{\alpha\beta(r_1+r_2)!r_1^{r_1} r_2^{r_2}}{r_1!r_2!(r_1+r_2)^{r_1+r_2}}$ is a non-jump for $r_1+r_2$. We also apply the Lagrangian method to determine the Tur\'an density of the extension of the $(r-3)$-fold enlargement of a $3$-uniform matching.
Abstract
The concept of jump concerns the distribution of Tur\'an densities. A number $\alpha\in[0,1)$ is a \emph{jump} for $r$ if there exists a constant $c>0$ such that if the Tur\'an density of a family $\mathscr{F}$ of $r$-uniform graphs is greater than $\alpha$, then the Tur\'an density of $\mathscr{F}$ is at least $\alpha+c$. To determine whether a number is a jump or non-jump has been a challenging problem in extremal hypergraph theory. In this paper, we give a way to generate non-jumps for hypergraphs. We show that if $\alpha,\beta$ are non-jumps for $r_1,r_2\geq2$ respectively, then $\frac{\alpha\beta(r_1+r_2)!r_1^{r_1} r_2^{r_2}}{r_1!r_2!(r_1+r_2)^{r_1+r_2}}$ is a non-jump for $r_1+r_2$. We also apply the Lagrangian method to determine the Tur\'an density of the extension of the $(r-3)$-fold enlargement of a $3$-uniform matching.
참고문헌 (18)
- RAHIL BABER, "Hypergraphs Do Jump", Combinatorics, Probability and Computing, 20(2), pp.161~171 (2011), Cambridge University Press (CUP)[DOI]
- P. Erdös, "On extremal problems of graphs and generalized graphs", Israel Journal of Mathematics, 2(3), pp.183~190 (1964), Springer Science and Business Media LLC[DOI]
- P. Erdos, "A limit theorem in graph theory", Studia Sci. Math. Hungar, 1, pp.51~57 (1966)
- P. Erdös, "On the structure of linear graphs", Bulletin of the American Mathematical Society, 52(12), pp.1087~1092 (1946), American Mathematical Society (AMS)[DOI]
- P Frankl, "Extremal problems whose solutions are the blowups of the small witt-designs", Journal of Combinatorial Theory, Series A, 52(1), pp.129~147 (1989), Elsevier BV[DOI]
- Peter Frankl, "A note on the jumping constant conjecture of Erdős", Journal of Combinatorial Theory, Series B, 97(2), pp.204~216 (2007), Elsevier BV[DOI]
- Peter Frankl, "Hypergraphs do not jump", Combinatorica, 4(2-3), pp.149~159 (1984), Springer Science and Business Media LLC[DOI]
- Ran Gu, "Non-jumping numbers for 5-uniform hypergraphs", Applied Mathematics and Computation, 317, pp.234~251 (2018), Elsevier BV[DOI]
- Tao Jiang, "Lagrangian densities of some sparse hypergraphs and Turán numbers of their extensions", European Journal of Combinatorics, 73, pp.20~36 (2018), Elsevier BV[DOI]
- T. Johnston, "Strong jumps and Lagrangians of non-uniform hypergraphs", arXiv:1403.1220v1, ~
- G. Katona, "On a problem of Turan in the theory of graphs", Mat. Lapok, 15, pp.228~238 (1964)
- T. S. Motzkin, "Maxima for Graphs and a New Proof of a Theorem of Turán", Canadian Journal of Mathematics, 17, pp.533~540 (1965), Canadian Mathematical Society[DOI]
- Yuejian Peng, "On Substructure Densities of Hypergraphs", Graphs and Combinatorics, 25(4), pp.583~600 (2009), Springer Science and Business Media LLC[DOI]
- Yuejian Peng, "On Jumping Densities of Hypergraphs", Graphs and Combinatorics, 25(5), pp.759~766 (2009), Springer Science and Business Media LLC[DOI]
- Yuejian Peng, "On non-strong jumping numbers and density structures of hypergraphs", Discrete Mathematics, 309(12), pp.3917~3929 (2009), Elsevier BV[DOI]
- Oleg Pikhurko, "ON possible Turán densities", Israel Journal of Mathematics, 201(1), pp.415~454 (2014), Springer Science and Business Media LLC[DOI]
- A. F. Sidorenko, "Asymptotic solution for a new class of forbiddenr-graphs", Combinatorica, 9(2), pp.207~215 (1989), Springer Science and Business Media LLC[DOI]
- P. Turan, "Eine Extremalaufgabe aus der Graphentheorie", Mat. Fiz. Lapok, 48, pp.436~452 (1941)