On the second eigenvalue of hypergraphs
type: Item
instance of: scholarly article
title: On the second eigenvalue of hypergraphs
zbMATH Open document ID: 0843.05075
DOI: 10.1007/BF01294459
author: Joel Friedman
author: A. Wigderson
published in: Combinatorica
publication date: 1995-05-04T00:00:00Z
review text: We first define the second eigenvalue of 3-uniform hypergraph, and then discuss the general notion, as it applies to other uniform hypergraphs and graphs. Second, just as ordinary directed graphs can have multiple edges and self-loops, we can accomodate such notions here. Thirdly, we can also handle the notion of directed edges. We say that a directed 3-uniform hypergraph is a hypergraph where each edge \(\{i, j, k\}\) has a specified order. Now the trilinear form \(\tau\) is defined by \(\tau_{i, j, k}\) being the multiplicity if the edge \(\{i, j, k\}\). Fourth, we define for any trilinear form on \(L^2(V)\), \(\mu\), its first eigenvalue to be its norm with respect to \(L^2(V)\). Fifth, it becomes clear how we want to define the second eigenvalue in the more general case. Sixth, the first and second eigenvalue of multilinear forms (as defined in this paper) are always non-negative numbers. Lastly, we could define the eigenvalues and/or norms of multilinear forms with respect to other norms on the space of functions on \(V\), such as \(L^p(V)\) for any \(1\leq p\leq \infty\).
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 750658
zbMATH Keywords: second eigenvalue
zbMATH Keywords: hypergraph
zbMATH Keywords: uniform hypergraphs
zbMATH Keywords: directed edges
zbMATH Keywords: trilinear form
zbMATH Keywords: first eigenvalue
zbMATH Keywords: multilinear forms
zbMATH Keywords: norms
MaRDI profile type: Publication
cites work: Eigenvalues and expanders
cites work: Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory
cites work: Diameters and Eigenvalues
cites work: On the second eigenvalue and random walks in random \(d\)-regular graphs
cites work: Some graphs with small second eigenvalue
cites work: Q3715120
cites work: An Estimate for Character Sums
cites work: Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
cites work: Q3963253
cites work: On using deterministic functions to reduce randomness in probabilistic algorithms
cites work: Q3745279
cites work: Characteristic vectors of bordered matrices with infinite dimensions
full work available at URL: https://doi.org/10.1007/bf01294459
OpenAlex ID: W1979110822
description: scientific article; zbMATH DE number 750658