Bisection width, discrepancy, and eigenvalues of hypergraphs

DOI10.1016/J.JCTB.2025.11.003MaRDI QIDQ6873948zbMATH OpenFDO

Authors Eero Räty, István Tomon

Publication date 15 January 2026

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.JCTB.2025.11.003

zbMATH Keywords

Alon-Boppana theorembisection widthdiscrepancyeigenvalue

Mathematics Subject Classification ID

Connectivity (05C40) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Semidefinite programming (90C22)

Cites work

• A note on internal partitions: the 5-regular case and beyond
• A proof of Alon’s second eigenvalue conjecture and related problems
• Bounds on the bisection width for random \(d\)-regular graphs
• Bounds on the max and min bisection of random cubic and random 4-regular graphs
• Cutting a graph into two dissimilar halves
• Deterministic Edge Connectivity in Near-Linear Time
• Deterministic mincut in almost-linear time
• Deterministic near-linear time minimum cut in weighted graphs
• Discrepancy in graphs and hypergraphs
• Eigenvalues and linear quasirandom hypergraphs
• Expander graphs and their applications
• scientific article; zbMATH DE number 125467 (Why is no real title available?)
• scientific article; zbMATH DE number 1256719 (Why is no real title available?)
• scientific article; zbMATH DE number 475375 (Why is no real title available?)
• scientific article; zbMATH DE number 1834674 (Why is no real title available?)
• scientific article; zbMATH DE number 826245 (Why is no real title available?)
• Imbalances in k‐colorations
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Local flow partitioning for faster edge connectivity
• Minimum cuts and sparsification in hypergraphs
• On the first and second eigenvalue of finite and infinite uniform hypergraphs
• On the second eigenvalue of a graph
• On the second eigenvalue of hypergraphs
• On the spectrum of hypergraphs
• Regular honest graphs, isoperimetric numbers, and bisection of weighted graphs
• Spectra of hypergraphs and applications
• Spectra of uniform hypergraphs
• Spectral extremal problems for hypergraphs
• The isoperimetric number of random regular graphs
• The Laplacian of a uniform hypergraph
• The Spectra of Infinite Hypertrees

Cited in

(1)

• MaxCut in graphs with sparse neighborhoods

This page was built for publication: Bisection width, discrepancy, and eigenvalues of hypergraphs

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