论文

可消去超图p-谱半径的极值问题

展开
  • 1. 上海大学数学系, 上海 200444
吴志伟  E-mail: 2515737530@qq.com

收稿日期: 2022-01-06

  网络出版日期: 2025-06-12

基金资助

国家自然科学基金(11871329);国家自然科学基金(11971298)

版权

运筹学学报编辑部, 2025, 版权所有,未经授权,不得转载。

The extremal p-spectral radius of cancellative hypergraphs

Expand
  • 1. Department of Mathematics, Shanghai University, Shanghai 200444, China

Received date: 2022-01-06

  Online published: 2025-06-12

Copyright

, 2025, All rights reserved. Unauthorized reproduction is prohibited.

摘要

AB是两个集合, AB的对称差是由$A\cup B$中所有不属于$A\cap B$的元素组成的一个集合, 记为$A\Delta B$。若一个超图不含有三条互不相同的边A, B, C使得$A\Delta B\subset C$, 则称该超图是一个可消去超图。一个3-一致可消去超图同时不含$F_4=\{abc, abd, bcd\}$$F_5=\{abc, abd, cde\}$作为子超图。Bollobás (1974) 给出了3-一致可消去超图的最大边数, 并得出平衡的完全3-部3-一致超图是唯一达到最大边数的3-一致可消去超图。Keevash和Mubayi (2004) 进一步确定了平衡的完全3-部3-一致超图是唯一不含$F_5$作为子超图且边数达到最大的3-一致超图。设$\mathcal{H}$是一个超图, W是顶点集$V(\mathcal{H})$的一个非空子集。如果超图$\mathcal{H}$中的任意一条边只包含W中的一个顶点, 则称W是超图$\mathcal{H}$的一个独立横贯。在本文中, 我们得到了具有独立横贯的3-一致可消去超图p-谱半径的最大值。进一步, 我们证明了当p>2时, 平衡的完全3-部3-一致超图是唯一具有独立横贯且p-谱半径达到最大的3-一致可消去超图。

本文引用格式

吴志伟, 康丽英 . 可消去超图p-谱半径的极值问题[J]. 运筹学学报, 2025 , 29(2) : 194 -200 . DOI: 10.15960/j.cnki.issn.1007-6093.2025.02.015

Abstract

Let A and B be two sets, the symmetry difference of A and B is a set consisting of all elements not belonging to $A\cap B$ in $A\cup B$, denoted by $A\Delta B$. A hypergraph is called a cancellative hypergraph, if it contains no three distinct edges A, B, and C, such that $A\Delta B\subset C$. In fact, a cancellative3-uniform hypergraph contains neither $F_4=\{abc, abd, bcd\}$ nor $F_5=\{abc, abd, cde\}$ as its subgraphs. Bollobás (1974) determined the maximum number of edges in a cancellative3-uniform hypergraph, and got that only the balanced complete3-partite3-uniform hypergraph achieved the maximum number of edges in a cancellative3-uniform hypergraph. Furthermore, Keevash and Mubayi (2004) determined that only the balanced complete3-partite3-uniform hypergraph achieved the maximum number of edges in a3-uniform hypergraph containing no copy of $F_5$. Let $\mathcal{H}$ be a hypergraph, and W be a nonempty subset of $V(\mathcal{H})$. If every edge in $\mathcal{H}$ contains exactly one vertex in W, then we call W an independent transversal of $\mathcal{H}$. In this paper, we determine the maximump-spectral radius of a cancellative3-uniform hypergraph with an independent transversal. Furthermore, if $p>2$, we get that only the balanced complete3-partite3-uniform hypergraph achieved the maximump-spectral radius of a cancellative3-uniform hypergraph with an independent transversal.

参考文献

1 Keevash P , Lenz J , Mubayi D . Spectral extremal problems for hypergraphs[J]. SIAM Journal on Discrete Mathematics, 2014, 28 (4): 1838- 1854.
2 Nikiforov V S . Analytic methods for uniform hypergraphs[J]. Linear Algebra & Its Applications, 2014, 457, 455- 535.
3 Lu L Y. The maximum p-spectral radius of hypergraphs with m edges[EB/OL]. [2022-01-05]. arXiv: 1803.08653.
4 Talbot J . Lagrangians of hypergraphs[J]. Combinatorics Probability & Computing, 2002, 11, 199- 216.
5 Gruslys V , Letzter S , Morrison N . Hypergraph Lagrangians I: The Frankl-Füredi conjecture is false[J]. Advances in Mathematics, 2020, 365, 107063.
6 Cooper J N , Dutle A M . Spectra of uniform hypergraphs[J]. Linear Algebra & Its Applications, 2012, 436 (9): 3268- 3292.
7 Chang J Y , Ding W Y , Qi L Q . Computing the p-spectral radii of uniform hypergraphs with applications[J]. Journal of Scientific Computing, 2018, 75 (1): 1- 25.
8 Kang L Y , Nikiforov V S , Yuan X Y . The p-spectral radius of k-partite and k-chromatic uniform hypergraphs[J]. Linear Algebra & Its Applications, 2015, 478, 81- 107.
9 Kang L Y , Liu L L , Shan E F . The eigenvectors to the p-spectral radius of general hypergraphs[J]. Journal of Combinatorial Optimization, 2019, 38 (2): 556- 569.
10 Kang L Y , Liu L L , Lu L Y , et al. The extremal p-spectral radius of Berge-hypergraphs[J]. Linear Algebra & Its Applications, 2021, 610, 608- 624.
11 Zhou Y C , Kang L Y , Liu L L , et al. Extremal problems for the p-spectral radius of Berge-hypergraphs[J]. Linear Algebra & Its Applications, 2020, 600, 22- 39.
12 Bollobás B . Three-graphs without two triples whose symmetric difference is contained in a third[J]. Discrete Mathematics, 1974, 8 (1): 21- 24.
13 Keevash P , Mubayi D . Stability theorems for cancellative hypergraphs[J]. Journal of Combinatorial Theory, Series B, 2004, 92 (1): 163- 175.
14 Turán P . On the theory of graphs[J]. Colloquium Mathematicum, 1954, 3, 19- 30.
文章导航

/