A clique-free pseudorandom subgraph of the pseudo polarity graph

Sam Mattheus, Francesco Pavese

Research output: Contribution to journalArticle

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.

Original languageEnglish
Article number112871
Number of pages7
JournalDiscrete Mathematics
Volume345
Issue number7
DOIs
Publication statusPublished - Jul 2022

Fingerprint

Dive into the research topics of 'A clique-free pseudorandom subgraph of the pseudo polarity graph'. Together they form a unique fingerprint.

Cite this