A clique-free pseudorandom subgraph of the pseudo polarity graph

2021/05/08 by Sam Mattheus, Francesco Pavese, Mattheus, Sam +1 · 1 citation
Computer Science · Engineering · #51E20 #Coding theory and cryptography #Combinatorics (math.CO) #Cooperative Communication and Network Coding #FOS: Mathematics #Primary 05D10. Secondary 05E30 #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2105.03755

openalex publication_date 2021/05/08 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28

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. As in the former result, the idea is to use large subgraphs of polarity graphs, which are defined over a finite field \mathbbF_q. While their construction required q to be odd, we will give the first construction with q even.

Cited by

• Combinatorial theorems relative to sparse sets

Related

• A construction for clique-free pseudorandom graphs
• Triangle-free induced subgraphs of polarity graphs
• Orthogonal polarity graphs and Sidon sets
• A note on graphs without short even cycles
• A Paley-like graph in characteristic two