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

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

1 Citation (Scopus)

Abstract

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.

Original language	English
Article number	112871
Number of pages	7
Journal	Discrete Mathematics
Volume	345
Issue number	7
DOIs	https://doi.org/10.1016/j.disc.2022.112871
Publication status	Published - Jul 2022

Access to Document

10.1016/j.disc.2022.112871

Cite this

@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

Abstract

Access to Document

Other files and links

Fingerprint

Cite this