Abstract :
How dense can every induced subgraph of ⌊αn⌋ vertices (0 < α ⩽ 1) of a triangle-free graph of order n be? Tools will be developed to estimate the local density of graphs, based on the spectrum of the graph and on a fractional viewpoint. These tools are used to refute a conjecture of Erdős et al. about the local density of triangle-free graphs for a certain range of α, by estimating the local density of the Higman-Sims graph via its eigenvalues. Moreover, the local density will be related to a long-standing conjecture of Erdős, saying that every triangle-free graph can be made bipartite by the omission of at most n2/25 edges. Finally, a conjecture about the spectrum of regular triangle-free graphs is raised, which can be seen as a common relaxation of the two previous questions.
