MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am looking for examples/families of graphs with the following (maybe vague-sounding at first) property: the graph $G$ has a relatively large subgraph $B$ such that $B$ is bipartite-plus-a-few-edges and the cut between $B$ and $G-B$ is small.

In a paper called A characterization of the smallest eigenvalue of a graph (J. Graph Theory, 1994) Desai and Rao studied this problem and related it to the signless Laplacian spectrum. What I am after here is locating some explicit examples.

EDIT: I can construct lots of examples by just taking a bipartite graph and loosely attaching it to another large dense graph, and then sprinkling some noise. But I'd like to know if there are well-known interesting graphs/families that already display such a behaviour.

EDIT2: Let's take a concrete example. Do the Paley graphs have such a property?

EDIT3: Just a bounce, since the bounty expires tomorrow...

share|cite|improve this question
You might consider k-partite graphs with large bipartite compnent or certain mixed product or twisted product graphs. Gerhard "Ask Me About System Design" Paseman, 2012.05.18 – Gerhard Paseman May 18 '12 at 13:14
What are 'twisted product graphs'? I found this presentation ( that mentions such a concept but I'm not sure if that's what you meant. – Felix Goldberg May 18 '12 at 13:50
What range are you considering here when you say "relatively large"? Do you want $B$ to be a constant fraction of $G$, or $n^{\alpha}$ vertices for some $0<\alpha<1$? If the former, Paley graphs may not be the best bet, as they're quasirandom in the sense of Chung-Graham-Wilson (have large eigenvalue gap; equiv. all large subsets of vertices span about the same number of edges) -- I think if you work through their bounds you get that the Paley graph has no nearly bipartite subgraphs of size larger than $q^{1/2+\epsilon}$ vertices, and you might be able to get better bounds by number theory. – Kevin P. Costello May 21 '12 at 19:05
A constant fraction will be better, I think. You are probably right about the Paley graphs, I managed to pick like the worst possible example... Any other suggestions perhaps? – Felix Goldberg May 22 '12 at 0:08

You can look on such family as amenable graph by bipartite folner sets

share|cite|improve this answer
:):):):):):):):) – Felix Goldberg Aug 22 '12 at 14:40

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.