Welcome to MathOverflow

Question

2

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

edited May 24 2012 at 11:29

asked May 15 2012 at 9:17

Felix Goldberg
2,385●5●12

	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 2012 at 13:14
	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. – Felix Goldberg May 18 2012 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 2012 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 2012 at 0:08

Ani from Asat forum · Answer 1 · 2012-08-21 17:53:34Z UTC

1

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

answered Aug 21 at 17:53

Ani from Asat forum
11●1

:):):):):):):):) – Felix Goldberg Aug 22 at 14:40

almost-bipartite nearly-isolated subgraphs

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.