Communications on Applied Mathematics and Computation ›› 2021, Vol. 3 ›› Issue (2): 243-256.doi: 10.1007/s42967-020-00073-7

• ORIGINAL PAPER • Previous Articles     Next Articles

The Spectral Radii of Intersecting Uniform Hypergraphs

Peng, Li Zhang, Xiao, Dong Zhang   

  1. School of Mathematical Sciences, MOE-LSC, SHL-MAC, Shanghai Jiao Tong University, Shanghai 200240, China
  • Received:2019-11-10 Revised:2020-04-10 Online:2021-06-20 Published:2021-05-26
  • Contact: Xiao-Dong Zhang, Peng-Li Zhang E-mail:xiaodong@sjtu.edu.cn;zpengli@sjtu.edu.cn
  • Supported by:
    This work is supported by the National Natural Science Foundation of China (Nos. 11971311, 11531001), and the Montenegrin-Chinese Science and Technology Cooperation Project (No. 3-12).

Abstract: The celebrated Erdős-Ko-Rado theorem states that given n ≥ 2k, every intersecting k-uniform hypergraph G on n vertices has at most $(_{k - 1}^{n - 1})$ edges. This paper states spectral versions of the Erdős-Ko-Rado theorem: let G be an intersecting k-uniform hypergraph on n vertices with n ≥ 2k. Then, the sharp upper bounds for the spectral radius of $\mathcal{A}$α(G) and $\mathcal{Q}$*(G) are presented, where $\mathcal{A}$α(G) = α$\mathcal{D}$(G) + (1 - α)$\mathcal{A}$(G) is a convex linear combination of the degree diagonal tensor $\mathcal{D}$(G) and the adjacency tensor $\mathcal{A}$(G) for 0 ≤ α < 1, and $\mathcal{Q}$*(G) is the incidence $\mathcal{Q}$-tensor, respectively. Furthermore, when n > 2k, the extremal hypergraphs which attain the sharp upper bounds are characterized. The proof mainly relies on the Perron-Frobenius theorem for nonnegative tensor and the property of the maximizing connected hypergraphs.

Key words: Erd?s-Ko-Rado theorem, Intersecting hypergraph, Tensor, Spectral radius

CLC Number: