Extremal Graph Theoretic Questions for q-Ary Vectors

A q-graph H on n vertices is a set of vectors of length n with all entries from $$\{0,1,\dots ,q\}$${ 0 , 1 , ⋯ , q } and every vector (that we call a q-edge) having exactly two non-zero entries. The support of a q-edge $${\textbf{x}}$$x is the pair $$S_{\textbf{x}}$$S x of indices of non-zero entries. We say that H is an s-copy of an ordinary graph F if $$|H|=|E(F)|$$| H | = | E ( F ) | , F is isomorphic to the graph with edge set $$\{S_{\textbf{x}}:{\textbf{x}}\in H\}$${ S x : x ∈ H } , and whenever $$v\in e,e'\in E(F)$$v ∈ e , e ′ ∈ E ( F ) , the entries with index corresponding to v in the q-edges corresponding to e and $$e'$$e ′ sum up to at least s. E.g., the q-edges (1, 3, 0, 0, 0), (0, 1, 0, 0, 3), and (3, 0, 0, 0, 1) form a 4-triangle. The Turán number $$\mathop {}\!\textrm{ex}(n,F,q,s)$$ex ( n , F , q , s ) is the maximum number of q-edges that a q-graph H on n vertices can have if it does not contain any s-copies of F. In the present paper, we determine the asymptotics of $$\mathop {}\!\textrm{ex}(n,F,q,q+1)$$ex ( n , F , q , q + 1 ) for many graphs F.