A clique-free pseudorandom subgraph of the pseudo polarity graph

DOI10.1016/J.DISC.2022.112871MaRDI QIDQ2138963zbMATH OpenOpenAlexFDO

Authors Sam Mattheus, Francesco Pavese

Publication date 17 May 2022

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2105.03755

zbMATH Keywords

clique-freepolarity graphpseudorandom graphRamsey number

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75) Random graphs (graph-theoretic aspects) (05C80) Ramsey theory (05D10)

Abstract: We provide a new family of $K_k$-free pseudorandom graphs with edge density $Theta(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 $mathbb{F}_q$. While their construction required $q$ to be odd, we will give the first construction with $q$ even.

Recommendations

• A construction for clique-free pseudorandom graphs
• A sequence of triangle-free pseudorandom graphs
• Ramsey problem on multiplicities of complete subgraphs in nearly quasirandom graphs
• Bipartite subgraphs and quasi-randomness
• Pseudorandom Graphs from Elliptic Curves

Cites work

• A construction for clique-free pseudorandom graphs
• Constructive bounds for a Ramsey-type problem
• Counting trees in graphs
• Explicit Ramsey graphs and orthonormal labelings
• Finite geometry and combinatorial applications
• scientific article; zbMATH DE number 4027516 (Why is no real title available?)
• scientific article; zbMATH DE number 4099367 (Why is no real title available?)
• Interlacing eigenvalues and graphs
• Multicolor Ramsey numbers via pseudorandom graphs
• On the independence number of graphs related to a polarity
• On the independence number of the Erdős‐Rényi and projective norm graphs and a related hypergraph
• Pseudo-random graphs
• The probabilistic method

Cited in

(5)

• A construction for clique-free pseudorandom graphs
• Random hypergraphs in pseudofinite fields
• A sequence of triangle-free pseudorandom graphs
• Turán problems in pseudorandom graphs
• Association schemes and orthogonality graphs on anisotropic points of polar spaces

This page was built for publication: A clique-free pseudorandom subgraph of the pseudo polarity graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2138963)