67 citations · 92 across the 8 of their papers we have counts for
6 papers · 1 filter
The sum of degrees in cliques
B. Bollobas, V. Nikiforov
We investigate lower bounds on the average degree in r-cliques in graphs of order n and size greater than t(r,n), where t(r,n) is the size of the Turan graph on n vertices and r co…
Joints in graphs
B. Bollobas, V. Nikiforov
In 1969 Erdoes found a lower bound on the number of (r+1)-cliques sharing an edge in graphs with n vertices and t(r,n)+1 edges, where t(r,n) is the size of the Turan graph of order…
Ramsey-type theorems for metric spaces with applications to online problems
Yair Bartal, Bela Bollobas, Manor Mendel
A nearly logarithmic lower bound on the randomized competitive ratio for the metrical task systems problem is presented. This implies a similar lower bound for the extensively stud…
Graphs and Hermitian matrices: discrepancy and singular values
Bela Bollobas, Vladimir Nikiforov
We introduce a measure of discrepancy of Hermitian matrices and establish an inequality between the second singular value of a Hermitian matrix and its discrepancy. These results a…
Books in graphs
Bela Bollobas, Vladimir Nikiforov
A book of size is a set of triangles sharing a common edge. We study the size of the maximal book in a graph as a function of the number of its edges. In particular, we ans…
Degree powers in graphs with forbidden subgraphs
Bela Bollobas, Vladimir Nikiforov
Yuster and Caro initiated the study of the sum of powers of the degrees of graphs with forbidden subgraphs. We settle two of their conjectures.