Minimum degree and density of binary sequences

For d,k∈Nd,k∈N with k≤2dk≤2d, let g(d,k)g(d,k) denote the infimum density of binary sequences (xi)i∈Z∈{0,1}Z(xi)i∈Z∈{0,1}Z which satisfy the minimum degree condition ∑j=1d(xi+j+xi−j)≥k for all i∈Zi∈Z with xi=1xi=1. We reduce the problem of computing g(d,k)g(d,k) to a combinatorial problem related to the generalized kk-girth of a graph GG which is defined as the minimum order of an induced subgraph of GG of minimum degree at least kk. Extending results of Kézdy and Markert, and of Bermond and Peyrat, we present a minimum mean cycle formulation that yields g(d,k)g(d,k) for small values of dd and kk. For odd values of kk with d+1≤k≤2dd+1≤k≤2d, we conjecture g(d,k)=k2−12(dk−1) and show that this holds for k≥2d−3k≥2d−3.