pith. sign in

arxiv: 0710.2305 · v2 · submitted 2007-10-11 · 🧮 math.CO

The number of cliques in graphs of given order and size

classification 🧮 math.CO
keywords graphsnumberanalyticalapproximatesargumentsboundcertaincliques
0
0 comments X
read the original abstract

Let k_r(n,m) denote the minimum number of r-cliques in graphs with n vertices and m edges. For r=3,4 we give a lower bound on k_r(n,m) that approximates k_r(n,m) with an error smaller than n^r/(n^2-2m). The solution is based on a constraint minimization of certain multilinear forms. In our proof, a combinatorial strategy is coupled with extensive analytical arguments.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.