VC-dimension and pseudo-random graphs
Abstract
Let G be a graph and U?V(G) be a set of vertices. For each v?U, let hv:U?{0,1} be the function defined by hv(u)=&1ifu?v,u?U0ifu??v,u?U,and set H(U)?{hv:v?U}. The first purpose of this paper is to study the following question: What families of graphs G and what conditions on U do we need so that the VC-dimension of H(U) can be determined? We show that if G is a pseudo-random graph, then under some mild conditions, the VC dimension of H(U) can be bounded from below. Specific cases of this theorem recover and improve previous results on VC-dimension of functions defined by the well-studied distance and dot-product graphs over a finite field.
Department(s)
Mathematics
Document Type
Article
DOI
10.1016/j.dam.2025.01.030
Keywords
Finite fields, Pseudo-random graphs, VC-dimension
Publication Date
4-15-2025
Recommended Citation
Senger, Steven; Pham, Thang; Tait, Michael; and Thu-Huyen, Nguyen, "VC-dimension and pseudo-random graphs" (2025). Faculty Scholarship. 155.
https://bearworks.missouristate.edu/articles00/155
Journal Title
Discrete Applied Mathematics
