MathDB
Good Intersections

Source: KöMaL A. 784

March 24, 2022
graph theorykomalcombinatorics

Problem Statement

Let n,s,n,s, and tt be positive integers and 0<λ<1.0<\lambda<1. A simple graph on nn vertices with at least λn2\lambda n^2 edges is given. We say that (x1,…,xs,y1,…,yt)(x_1,\ldots,x_s,y_1,\ldots,y_t) is a good intersection if letters xix_i and yjy_j denote not necessarily distinct vertices and every xiyjx_iy_j is an edge of the graph (1≤i≤s,(1\leq i\leq s, 1≤j≤t).1\leq j\leq t). Prove that the number of good insertions is at least λstns+t.\lambda^{st}n^{s+t}.
Proposed by Kada Williams, Cambridge
Back to ProblemsView on AoPS