{"id":"arxiv/2604.02949","url":"https://arxiv.org/abs/2604.02949","tags":["cs.DM","math.CO"],"score":0,"title":"Sample compression schemes for balls in structurally sparse graphs","domain":"cs.DM","source":"arxiv","authors":["Romain Bourneuf","Jędrzej Hodor","Piotr Micek","Clément Rambaud"],"reviews":0,"subject":"cs.DM","summary":"Sample compression schemes were defined by Littlestone and Warmuth (1986) as an abstraction of the structure underlying many learning algorithms. In a sample compression scheme, we are given a large sample of vertices of a fixed hypergraph with labels indicating the containment in some hyperedge. The task is to compress the sample in such a way that we can retrieve the labels of the original sample. The size of a sample compression scheme is the amount of information that is kept in the compression. Every hypergraph with a sample compression scheme of bounded size must have bounded…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-04-03","reactions":{}}