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.
A clique-free pseudorandom subgraph of the pseudo polarity graph
Pavese F.
2022-01-01
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.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
