The independence and clique cover numbers of the squarefree graph

by Boris Alexeev, Dustin G. Mixon, and Will Sawin

Abstract

We determine the largest subset \(A \subseteq \{1,\dotsc,n\}\) such that for all \(a,b\in A\), the product \(ab\) is not squarefree. Specifically, the maximum size is achieved by the complement of the odd squarefree numbers.

This resolves a problem of Paul Erdős and András Sárközy from 1992.

Approximate citation

Boris Alexeev, Dustin G. Mixon, and Will Sawin
The independence and clique cover numbers of the squarefree graph

Useful links

	Direct PDF link
	arXiv online preprint server version