Spectral extremal results for hypergraphs

DOI10.37236/9018MaRDI QIDQ2049621zbMATH OpenOpenAlexFDO

Authors Yuan Hou, An Chang, Joshua Cooper

Publication date 27 August 2021

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1909.08120

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Berge graphsTurán numbers for hypergraphsTurán type extremal problem

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Extremal problems in graph theory (05C35) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Hypergraphs (05C65)

Abstract: Let $F$ be a graph. A hypergraph is called Berge $F$ if it can be obtained by replacing each edge in $F$ by a hyperedge containing it. Given a family of graphs $mathcalF$, we say that a hypergraph $H$ is Berge $mathcalF$-free if for every $FinmathcalF$, the hypergraph $H$ does not contain a Berge $F$ as a subhypergraph. In this paper we investigate the connections between spectral radius of the adjacency tensor and structural properties of a linear hypergraph. In particular, we obtain a spectral version of Tur'{a}n-type problems over linear $k$-uniform hypergraphs by using spectral methods, including a tight result on Berge $C_4$-free linear $3$-uniform hypergraphs.

Review text

Summary: Let \(F\) be a graph. A hypergraph is called Berge \(F\) if it can be obtained by replacing each edge in \(F\) by a hyperedge containing it. Given a family of graphs \(\mathcal{F}\), we say that a hypergraph \(H\) is Berge \(\mathcal{F}\)-free if for every \(F \in \mathcal{F}\), the hypergraph \(H\) does not contain a Berge \(F\) as a subhypergraph. In this paper we investigate the connections between spectral radius of the adjacency tensor and structural properties of a linear hypergraph. In particular, we obtain a spectral version of Turán-type problems over linear \(k\)-uniform hypergraphs by using spectral methods.

Recommendations

• Spectral extremal problems for hypergraphs
• Spectra of hypergraphs and applications
• Extremal properties of the distance spectral radius of hypergraphs
• On the spectrum of hypergraphs
• Some new results and problems in spectral extremal graph theory
• Spectral properties of general hypergraphs
• scientific article; zbMATH DE number 7352045
• The extremal \(p\)-spectral radius of Berge hypergraphs
• Spectra of general hypergraphs
• On the spectrum and linear programming bound for hypergraphs

Cites work

• A bound on the spectral radius of graphs with \(e\) edges
• A bound on the spectral radius of hypergraphs with \(e\) edges
• A new generalization of Mantel's theorem to \(k\)-graphs
• A survey of Turán problems for expansions
• Almost disjoint triangles in 3-space
• An extension of Mantel's theorem to k-graphs
• Asymptotics for the Turán number of Berge-\(K_{2,t}\)
• Asymptotics for Turán numbers of cycles in 3-uniform linear hypergraphs
• Bounds on graph eigenvalues. II
• Eigenvalues of a real supersymmetric tensor
• Extremal results for Berge hypergraphs
• Further results for Perron-Frobenius theorem for nonnegative tensors
• scientific article; zbMATH DE number 5942358 (Why is no real title available?)
• scientific article; zbMATH DE number 3505014 (Why is no real title available?)
• scientific article; zbMATH DE number 3609704 (Why is no real title available?)
• Linear Turán Numbers of Linear Cycles and Cycle-Complete Ramsey Numbers
• On 3-uniform hypergraphs without a cycle of a given length
• On \(r\)-uniform linear hypergraphs with no Berge-\(K_{2,t}\)
• On hypergraphs of girth five
• Perron-Frobenius theorem for nonnegative multilinear forms and extensions
• Perron-Frobenius theorem for nonnegative tensors
• Some eigenvalue properties in graphs (conjectures of Graffiti -- II)
• Some new results in extremal graph theory
• Spectra of uniform hypergraphs
• Spectral bounds for the clique and independence numbers of graphs
• Spectral extrema for graphs: the Zarankiewicz problem
• Spectral extremal problems for hypergraphs
• The history of degenerate (bipartite) extremal graph problems

Cited in

(22)

• Extremal problems for the \(p\)-spectral radius of Berge hypergraphs
• The extremal \(p\)-spectral radius of Berge hypergraphs
• Analytic methods for uniform hypergraphs
• Spectral extrema for graphs: the Zarankiewicz problem
• Spectral radius on linear \(r\)-graphs without expanded \(K_{r+1}\)
• Spectral extremal problems for hypergraphs
• Spectral extremal graphs for the bowtie
• Graph partitioning: an updated survey
• On the spectral radius of uniform weighted hypergraph
• A stability result for Berge-\( K_{3 , t}r\)-graphs and its applications
• A note on stability results for Berge-\( K_{s , t}\) hypergraphs
• MT-product of tensors, spectral radius and walks of hypergraphs
• Spectral Turán problems for nondegenerate hypergraphs
• On the spectral Turán problems for bipartite hypergraphs
• The extremal problems for the spectral radius of hypergraphs without the Berge-graphs
• The spectral radius of the hypergraphs without the expansion of P₃ or Berge-P_k
• Principal eigenvectors in hypergraph Turán problems
• Extremal spectral radii of uniform supertrees
• The spectral radius of 3-graphs without Berge paths of given length
• Spectral bipartite Turán problems on linear hypergraphs
• Some Turán-type results for the signless Laplacian spectral radius
• Bounds on the spectral radii of Berge C₅-free linear r-graphs

This page was built for publication: Spectral extremal results for hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2049621)