Small dense subgraphs of polarity graphs and the extremal number for the 4-cycle

preprint2015arXivOpen access

Abstract

In this note, we show that for any m∈{1,2,…,q+1}m \in \{1,2, \dots , q +1 \}, if GG is a polarity graph of a projective plane of order qq that has an oval, then GG contains a subgraph on m+(m2)m + \binom{m}{2} vertices with m2+m48q−O(m4q3/2+m)m^2+\frac{m^4}{8q} - O ( \frac{m^4}{q^{3/2} } +m ) edges. As an application, we give the best known lower bounds on the Turán number ex(n,C4)\mathrm{ex}(n, C_4) for certain values of nn. In particular, we disprove a conjecture of Abreu, Balbuena, and Labbate concerning ex(q2−q−2,C4)\mathrm{ex}(q^2-q-2, C_4) where qq is a power of 22.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.