1
$\begingroup$

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...

Improve this question
$\endgroup$
4
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    May 18, 2012 at 13:14
  • $\begingroup$ What are 'twisted product graphs'? I found this presentation (math.unl.edu/~adonsig1/SS6A/Wright.pdf) that mentions such a concept but I'm not sure if that's what you meant. $\endgroup$
    – Felix Goldberg
    May 18, 2012 at 13:50
  • $\begingroup$ 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. $\endgroup$
    – Kevin P. Costello
    May 21, 2012 at 19:05
  • $\begingroup$ 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? $\endgroup$
    – Felix Goldberg
    May 22, 2012 at 0:08

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ :):):):):):):):) $\endgroup$
    – Felix Goldberg
    Aug 22, 2012 at 14:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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