2015/09/10 by Tuvi Etzion, Etzion, Tuvi
Computer Science · Mathematics · #Advanced Data Storage Technologies #Cellular Automata and Applications #Combinatorics (math.CO) #FOS: Mathematics #Optimization and Search Problems #math.CO
paper · pdf · doi:10.48550/arxiv.1509.03072
I want to rewrite it and start it fresh
openalex publication_date 2015/09/10 · arxiv created 2016/08/12 · arxiv updated 2016/08/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we raise a variant of a classic problem in extremal graph theory, which is motivated by a design of fractional repetition codes, a model in distributed storage systems. For any feasible positive integers d≥ 3, n ≥ 3, and k, where n-1 ≤ k ≤ \binomn2, what is the minimum possible number of vertices in a d-regular undirected graph whose subgraphs with n vertices contain at most k edges? The goal of this paper is to give the exact number of vertices for each instance of the problem and also to provide some bounds for general values of n, d, and k. A few general bounds with some exact values, for this Turán-type problem, are given. We present an almost complete solution for 3 ≤ n ≤ 5.