The p-spectral Radius of Berge-keyring Hypergraphs

Abstract

Let G be a simple graph. We say that a hypergraph

\mathcal{H}

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\cal{H}$$\end{document}

is a Berge-G if there is a bijection

\psi :E(G)\to E(\mathcal{H}))

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\psi : E(G)\rightarrow E({\cal{H}}))$$\end{document}

such that e ⊆ ψ(e) for all e ∈ E(G). For any r-uniform hypergraph

\mathcal{H}

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\cal{H}$$\end{document}

and a real number p ≥ 1, the p-spectral radius of

\mathcal{H}

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\cal{H}$$\end{document}

is defined as

{\lambda }^{(p)}(\mathcal{H})=\underset{x\in {\mathbb{R}}^n,{\parallel x\parallel }_p=1}{max}r\sum _{\{i_1,i_2,\dots ,i_r\}\in E(\mathcal{H})}{x}_{i_1}{x}_{i_2}\cdots x_{i_r}.

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$${\lambda^{(p)}}({\cal{H}}) = \mathop{\max}\limits_{x \in{\mathbb{R}^n},{{\| x \|}_p} = 1} r\mathop{\sum}\limits_{\{{{i_1},{i_2}, \ldots,{i_r}}\} \in E({\cal{H}})}{x_{{i_1}}}{x_{{i_2}}} \cdots{x_{{i_r}}}.$$\end{document}

A keyring C_n(k) is a graph of order n obtained from a cycle of length n − k by appending k leaves to one of vertices of the cycle. In this paper, we obtain the 3-uniform hypergraphs with maximum p-spectral radius for p ≥ 1 among 3-uniform Berge-G hypergraphs when G is a keyring.

Keywords

p-spectral radius / Berge-hypergraph / keyring / uniform hypergraph / 05C65 / 15A18

References

[1] Axenovich M, Gyárfás A. A note on Ramsey numbers for Berge-G hypergraphs. Discrete Math., 2019, 342(5): 1245-1252

[2] Cooper J, Dutle A. Spectra of uniform hypergraphs. Linear Algebra Appl., 2012, 436(9): 3268-3299

[3] Gerbner D, Methuku A, Omidi G, Vizer M. Ramsey problems for Berge hypergraphs. SIAM J. Discrete Math., 2020, 34(1): 351-369

[4] Gerbner D, Palmer C. Extremal results for Berge hypergraphs. SIAM J. Discrete Math., 2017, 31(4): 2314-2327

[5] Grósz D., Methuku A., Tompkins C., Uniformity thresholds for the asymptotic size of extremal Berge-F-free hypergraphs. European J. Combin., 2020, 88: Paper No. 103109, 10 pp.

[6] Gruslys V., Letzter S., Morrison N., Hypergraph Lagrangians I: The Frankl–Füredi conjecture is false. Adv. Math., 2020, 365: Paper No. 107063, 30 pp.

[7] Kang L, Liu L, Lu L, Wang Z. The extremal p-spectral radius of Berge-hypergraphs. Linear Algebra Appl., 2021, 610: 608-624

[8] Kang L, Liu L, Shan E. The eigenvectors to the p-spectral radius of general hypergraphs. J. Comb. Optim., 2019, 38(2): 556-569

[9] Kang L., Nikiforov V., Extremal problems for the p-spectral radius of graphs. Electron. J. Combin., 2014, 21(3): Paper No. 3.21, 23 pp.

[10] Kang L, Nikiforov V, Yuan X. The p-spectral radius of k-partite and k-chromatic uniform hypergraphs. Linear Algebra Appl., 2015, 478: 81-107

[11] Keevash P, Lenz J, Mubayi D. Spectral extremal problems for hypergraphs. SIAM J. Discrete Math., 2014, 28(4): 1838-1854

[12] Li H, Shao J, Qi L. The extremal spectral radii of k-uniform supertrees. J. Comb. Optim., 2016, 32(3): 741-764

[13] Lu L., The maximum p-spectral radius of hypergraphs with m edges. 2018, arXiv:1803. 08653

[14] Motzkin T, Straus E. Maxima for graphs and a new proof of a theorem of Turán. Canadian J. Math., 1965, 17: 533-540

[15] Nikiforov V. Analytic methods for uniform hypergraphs. Linear Algebra Appl., 2014, 457: 455-535

[16] Palmer C, Tait M, Timmons C, Wagner A. Turán numbers for Berge-hypergraphs and related extremal problems. Discrete Math., 2019, 342(6): 1553-1563

[17] Salia N., Tompkins C., Wang Z., Zamora O., Ramsey numbers of Berge-hypergraphs and related structures. Electron. J. Combin., 2019, 26(4): Paper No. 4.40, 25 pp.

[18] Talbot J. Lagrangians of hypergraphs. Combin. Probab. Comput., 2002, 11(2): 199-216

[19] Zhou Y, Kang L, Liu L, Shan E. Extremal problems for the p-spectral radius of Berge hypergraphs. Linear Algebra Appl., 2020, 600: 22-39

[20] Zhu H, Kang L, Ni Z, Shan E. The Turán number of Berge-K₄ in 3-uniform hypergraphs. SIAM J. Discrete Math., 2020, 34(3): 1485-1492

RIGHTS & PERMISSIONS

Peking University