Turán Numbers of Complete 3-Uniform Berge-Hypergraphs

被引:0
作者
L. Maherani
M. Shahsiah
机构
[1] Isfahan University of Technology,Department of Mathematical Sciences
[2] Institute for Research in Fundamental Sciences (IPM),School of Mathematics
来源
Graphs and Combinatorics | 2018年 / 34卷
关键词
Turán number; Extremal hypergraph; Berge-hypergraph; 05C65; 05C35; 05D05;
D O I
暂无
中图分类号
学科分类号
摘要
Given a family F\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {F}}$$\end{document} of r-graphs, the Turán number of F\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {F}}$$\end{document} for a given positive integer N, denoted by ex(N,F)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ex(N,{\mathcal {F}})$$\end{document}, is the maximum number of edges of an r-graph on N vertices that does not contain any member of F\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {F}}$$\end{document} as a subgraph. For given r≥3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r\ge 3$$\end{document}, a complete r-uniform Berge-hypergraph, denoted by Kn(r)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${K}_n^{(r)}$$\end{document}, is an r-uniform hypergraph of order n with the core sequence v1,v2,…,vn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$v_{1}, v_{2}, \ldots ,v_{n}$$\end{document} as the vertices and distinct edges eij,\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$e_{ij},$$\end{document}1≤i<j≤n,\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1\le i<j\le n,$$\end{document} where every eij\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$e_{ij}$$\end{document} contains both vi\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$v_{i}$$\end{document} and vj\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$v_{j}$$\end{document}. Let Fn(r)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {F}}^{(r)}_n$$\end{document} be the family of complete r-uniform Berge-hypergraphs of order n. We determine precisely ex(N,Fn(3))\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ex(N,{\mathcal {F}}^{(3)}_{n})$$\end{document} for N≥n≥13\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$N \ge n \ge 13$$\end{document}. We also find the extremal hypergraphs avoiding Fn(3)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {F}}^{(3)}_{n}$$\end{document}.
引用
收藏
页码:619 / 632
页数:13
相关论文
共 21 条
  • [1] Erdős P(1959)On maximal paths and circuits of graphs Acta Math. Acad. Sci. Hungar. 10 337-356
  • [2] Gallai T(2014)Hypergraph Turán numbers of linear cycles J. Combin. Theory Ser. A 123 252-270
  • [3] Füredi Z(2014)On Exact solution of the hypergraph Turán problem for Combinatorica 34 299-322
  • [4] Jiang T(2016)-uniform linear paths Eur. J. Combin. 58 238-246
  • [5] Füredi Z(2012)Hypergraph extensions of the Erdős–Gallai theorem Combin. Probab. Comput. 21 193-201
  • [6] Jiang T(2012)Hypergraphs with no cycle of a given length Combinatorica 32 187-203
  • [7] Seiver R(1935)3-uniform hypergraphs avoiding a given odd cycle J. Lond. Math. Soc. 10 26-30
  • [8] Győri E(2015)On representatives of subsets J. Combin. Theory Ser. A 129 167-190
  • [9] Katona GY(2006)Turán problems and shadows I: paths and cycles J. Combin. Theory Ser. B 96 122-134
  • [10] Lemons N(2013)A hypergraph extension of Turán’s theorem J. Combin. Theory Ser. B 103 220-225