Hypergraph expanders of all uniformities from Cayley graphs

David Conlon; Jonathan Tidor; Yufei Zhao

doi:10.1112/plms.12371

Hypergraph expanders of all uniformities from Cayley graphs

David Conlon
, Jonathan Tidor
, Yufei Zhao

Research output: Contribution to journal › Article › peer-review

6 Scopus citations

Abstract

Hypergraph expanders are hypergraphs with surprising, non-intuitive expansion properties. In a recent paper, the first author gave a simple construction, which can be randomized, of 3-uniform hypergraph expanders with polylogarithmic degree. We generalize this construction, giving a simple construction of (Formula presented.) -uniform hypergraph expanders for all (Formula presented.).

Original language	English (US)
Pages (from-to)	1311-1336
Number of pages	26
Journal	Proceedings of the London Mathematical Society
Volume	121
Issue number	5
DOIs	https://doi.org/10.1112/plms.12371
State	Published - Nov 1 2020
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Mathematics

Keywords

05C65
05C81 (primary)

Access to Document

10.1112/plms.12371

Cite this

@article{1be93be0833f41cf9d1ec3da4a681f9b,

title = "Hypergraph expanders of all uniformities from Cayley graphs",

abstract = "Hypergraph expanders are hypergraphs with surprising, non-intuitive expansion properties. In a recent paper, the first author gave a simple construction, which can be randomized, of 3-uniform hypergraph expanders with polylogarithmic degree. We generalize this construction, giving a simple construction of (Formula presented.) -uniform hypergraph expanders for all (Formula presented.).",

keywords = "05C65, 05C81 (primary)",

author = "David Conlon and Jonathan Tidor and Yufei Zhao",

note = "Publisher Copyright: {\textcopyright} 2020 The Authors. The publishing rights in this article are licensed to the London Mathematical Society under an exclusive licence.",

year = "2020",

month = nov,

day = "1",

doi = "10.1112/plms.12371",

language = "English (US)",

volume = "121",

pages = "1311--1336",

journal = "Proceedings of the London Mathematical Society",

issn = "0024-6115",

publisher = "John Wiley and Sons Ltd",

number = "5",

}

TY - JOUR

T1 - Hypergraph expanders of all uniformities from Cayley graphs

AU - Conlon, David

AU - Tidor, Jonathan

AU - Zhao, Yufei

PY - 2020/11/1

Y1 - 2020/11/1

N2 - Hypergraph expanders are hypergraphs with surprising, non-intuitive expansion properties. In a recent paper, the first author gave a simple construction, which can be randomized, of 3-uniform hypergraph expanders with polylogarithmic degree. We generalize this construction, giving a simple construction of (Formula presented.) -uniform hypergraph expanders for all (Formula presented.).

AB - Hypergraph expanders are hypergraphs with surprising, non-intuitive expansion properties. In a recent paper, the first author gave a simple construction, which can be randomized, of 3-uniform hypergraph expanders with polylogarithmic degree. We generalize this construction, giving a simple construction of (Formula presented.) -uniform hypergraph expanders for all (Formula presented.).

KW - 05C65

KW - 05C81 (primary)

UR - https://www.scopus.com/pages/publications/85094642633

UR - https://www.scopus.com/pages/publications/85094642633#tab=citedBy

U2 - 10.1112/plms.12371

DO - 10.1112/plms.12371

M3 - Article

AN - SCOPUS:85094642633

SN - 0024-6115

VL - 121

SP - 1311

EP - 1336

JO - Proceedings of the London Mathematical Society

JF - Proceedings of the London Mathematical Society

IS - 5

ER -

Hypergraph expanders of all uniformities from Cayley graphs

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this