A clique-free pseudorandom subgraph of the pseudo polarity graph

Sam Mattheus; Francesco Pavese

doi:10.1016/j.disc.2022.112871

A clique-free pseudorandom subgraph of the pseudo polarity graph

Sam Mattheus, Francesco Pavese

Onderzoeksoutput: Article › peer review

2 Citaten (Scopus)

Samenvatting

We provide a new family of K_k-free pseudorandom graphs with edge density Θ(n^−1/(k−1)), matching a recent construction due to Bishnoi, Ihringer and Pepe [2]. As in the former result, the idea is to use large subgraphs of polarity graphs, which are defined over a finite field F_q. While their construction required q to be odd, we will give the first construction with q a power of 2.

Originele taal-2	English
Artikelnummer	112871
Aantal pagina's	7
Tijdschrift	Discrete Mathematics
Volume	345
Nummer van het tijdschrift	7
DOI's	https://doi.org/10.1016/j.disc.2022.112871
Status	Published - jul 2022

Toegang tot document

10.1016/j.disc.2022.112871

Andere bestanden en links

Link to publication in Scopus

Citeer dit

@article{bb4a998a07ac4da4b4645e40c1fbc6a0,

title = "A clique-free pseudorandom subgraph of the pseudo polarity graph",

abstract = "We provide a new family of Kk-free pseudorandom graphs with edge density Θ(n−1/(k−1)), matching a recent construction due to Bishnoi, Ihringer and Pepe [2]. As in the former result, the idea is to use large subgraphs of polarity graphs, which are defined over a finite field Fq. While their construction required q to be odd, we will give the first construction with q a power of 2.",

author = "Sam Mattheus and Francesco Pavese",

year = "2022",

month = jul,

doi = "10.1016/j.disc.2022.112871",

language = "English",

volume = "345",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "7",

}

TY - JOUR

T1 - A clique-free pseudorandom subgraph of the pseudo polarity graph

AU - Mattheus, Sam

AU - Pavese, Francesco

PY - 2022/7

Y1 - 2022/7

N2 - We provide a new family of Kk-free pseudorandom graphs with edge density Θ(n−1/(k−1)), matching a recent construction due to Bishnoi, Ihringer and Pepe [2]. As in the former result, the idea is to use large subgraphs of polarity graphs, which are defined over a finite field Fq. While their construction required q to be odd, we will give the first construction with q a power of 2.

AB - We provide a new family of Kk-free pseudorandom graphs with edge density Θ(n−1/(k−1)), matching a recent construction due to Bishnoi, Ihringer and Pepe [2]. As in the former result, the idea is to use large subgraphs of polarity graphs, which are defined over a finite field Fq. While their construction required q to be odd, we will give the first construction with q a power of 2.

UR - http://www.scopus.com/inward/record.url?scp=85125648372&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2022.112871

DO - 10.1016/j.disc.2022.112871

M3 - Article

VL - 345

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 7

M1 - 112871

ER -

A clique-free pseudorandom subgraph of the pseudo polarity graph

Samenvatting

Toegang tot document

Andere bestanden en links

Vingerafdruk

Citeer dit