摘要
Given integers m and f,let Sn(m,f)be the set consisting of all integers e such that every n-vertex graph with e edges contains an m-vertex induced subgraph with f edges,and let σ(m,f)=lim sup_(n→∞)|S_(n)(m,f)|/(_(2)^(n)).As a natural extension of an extremal problem of Erdös,this was investigated by Erd˝os,Füredi,Rothschild and Sós 20 years ago.Their main result indicates that integers in S_(n)(m,f)are rare for most pairs(m,f),though they also found infinitely many pairs(m,f)whose σ(m,f)is a fixed positive constant.Here we aim to provide some improvements on this study.Our first result shows that σ(m,f)≤1/2 holds for all but finitely many pairs(m,f)and the constant 1/2 cannot be improved.This answers a question of Erdös et al.Our second result considers infinitely many pairs(m,f)of special forms,whose exact values of σ(m,f)were conjectured by Erdös et al.We partially solve this conjecture(only leaving two open cases)by making progress on some constructions which are related to number theory.Our proofs are based on the research of Erdös et al.and involve different arguments in number theory.We also discuss some related problems.
基金
supported by Hong Kong RGC Grant GRF 16308219 and Hong Kong RGC Grant ECS 26304920
supported by the National Key R and D Program of China 2020YFA0713100
National Natural Science Foundation of China Grant 12125106
Innovation Program for Quantum Science and Technology 2021ZD0302904
Anhui Initiative in Quantum Information Technologies Grant AHY150200
Research supported in part by NSFC Grant 11922113
National Key Research and Development Program of China 2021YFA1000700.
