The Helly bound for singular sums
type: Item
instance of: scholarly article
title: The Helly bound for singular sums
zbMATH Open document ID: 1021.05034
DOI: 10.1016/S0012-365X(01)00240-0
author: Robert E. Jamison
published in: Discrete Mathematics
publication date: 2002-05-28T00:00:00Z
review text: A set \(S\subseteq \{0,1,2,\dots,n-1\}\) is called singular if \(x-y\) is singular, that is not coprime to \(n\), for all \(x,y\in S\). Let \(S_2(n)\) be the maximum value of \(|S+S|\) over all singular \(S\subseteq \{0,1,2,\dots,n-1\}\). Suppose \(n\) has \(d\) prime factors, the smallest of which is \(p\). If \(d\leq 2\), then \(S_2(n)=n/p\). In this paper the language of graph theory and properties of Helly families are used to prove that in general \(S_2(n)\geq n-\phi(n)\), where \(\phi\) denotes the Euler totient function. This bound is shown to be tight when \(d=3\) and it is conjectured to be tight for \(d=4\) as well. For \(d\geq 5\) it is claimed that this bound can always be improved. An extension of \(S_2\) to finite abelian groups is also explored.
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1746282
zbMATH Keywords: clique
zbMATH Keywords: edge coloring
zbMATH Keywords: abelian group
zbMATH Keywords: Helly family
zbMATH Keywords: sum cover
zbMATH Keywords: singularity graph
MaRDI profile type: Publication
full work available at URL: s0012-365x(01)00240-0
OpenAlex ID: W1981578625
description: scientific article; zbMATH DE number 1746282