IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Normalized Laplacian Tensor and Isoperimetric Inequalities for Uniform Hypergraphs

  • Sept. 9, 2016
  • 2:30 p.m.
  • LeConte 312

Abstract

Laplacian eigenvalues play important roles in isoperimetric properties for graphs. For a given simple graph $G$ and any two sets $X$ and $Y$, it is well-known that $$\left| |E(X,Y)|- \frac{{\rm Vol}(|X|){\rm Vol}(|Y|)}{{\rm Vol}(G)} \right|\leq \bar \lambda \frac{\sqrt{{\rm Vol}(X){\rm Vol}(\bar X){\rm Vol}(Y){\rm Vol}(\bar Y)}}{{\rm Vol}(G)}.$$ Here $E(X,Y)$ denote the set of ordered edges with first vertex in $X$ and the second in $Y$, ${\rm Vol}(X)$ denote the sum of degrees in $X$, and $\bar \lambda$ is related to the Laplacian eigenvalues of $G$. Such isoperimetric inequality is related to the edge expansion, the conductance, and the Cheeger constant of the graph. In this paper, we will study the analogy of such isoperimetric inequality for $r$-uniform hypergraphs with $r\geq 3$. The key idea is how to define the Laplacian tensor and its "second largest eigenvalues" properly.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC