6
$\begingroup$

Turan's theorem provides minimum number of edges of a graph on $n$ vertices to surely contain a clique of a prescribed size. This has been generalized to regular graphs.

What additional specializations have been made in the literature if the graph is regular and contains additional algebraic structure?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

There are versions of Turan's theorem that add spectral assumptions to regularity. This one is due to Sudakov, Szabó, & Vu (CiteSeer link):

A graph is called an $(n, d, \lambda)$-graph if it has $n$ vertices, is $d$-regular, and $\max_{i \ge 2} |\lambda_i| \le \lambda$, where $\lambda_i$ are the adjaceny-matrix eigenvalues, largest to smallest.

If for some $r \ge 2$, $d^r \gg \lambda n^{r-1}$, then every $(n, d, \lambda)$-graph contains a clique of size $r+1$. They establish bounds on the size of the largest $K_{r+1}$-free subgraph.

In some sense this requires that the 2nd-largest eigenvalue is sufficiently small.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thankyou for the answer. When I meant structure, I meant something algebraic. I am familiar with Vu's work. It is a good reference. $\endgroup$
    – Turbo
    Commented Oct 17, 2013 at 4:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .