VC-dimension and pseudo-random graphs

DOI10.1016/J.DAM.2025.01.030MaRDI QIDQ7025833zbMATH OpenFDO

Authors Pham Thang, Steven Senger, Michael Tait, Nguyen Thu-Huyen

Publication date 19 February 2025

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DAM.2025.01.030

zbMATH Keywords

finite fieldspseudo-random graphsVC-dimension

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Random graphs (graph-theoretic aspects) (05C80) Finite fields (field-theoretic aspects) (12E20)

Cites work

• Character tables of association schemes of affine type
• Dot products in \(\mathbb{F}_q^3\) and the Vapnik-Chervonenkis dimension
• Finite analogues of non-Euclidean spaces and Ramanujan graphs.
• scientific article; zbMATH DE number 3668627 (Why is no real title available?)
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• On the number of orthogonal systems in vector spaces over finite fields
• Pseudo-random graphs
• The smallest eigenvalues of Hamming graphs, Johnson graphs and other distance-regular graphs with classical parameters
• The solvability of norm, bilinear and quadratic equations over finite fields via spectra of graphs
• The Vapnik-Chervonenkis dimension of a random graph
• The VC dimension of quadratic residues in finite fields
• Vapnik-Chervonenkis dimension and density on Johnson and Hamming graphs
• VC-dimension and distance chains in \(\mathbb{F}_q^d\)

Cited in

(3)

• VC-dimension of hyperplanes over finite fields
• VC-dimension of subsets of Hamming graphs
• The VC-dimension of random subsets of finite groups

This page was built for publication: VC-dimension and pseudo-random graphs

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