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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented Aug 22, 2012 at 14:40

You must log in to answer this question.

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