Does every bipartite graph with 512 edges have an induced subgraph with 256 edges?

Question

Suppose we have a (simple) bipartite graph with $2^k$ edges. Is it true that there is a subset of the vertices such that their induced subgraph has exactly $2^{k-1}$ edges?

I know that the answer is no for general graphs, since you can take a $K_6$ plus a disjoint edge. I also know that if we don't require the number of edges to be a power of 2, the answer is again no as shown by a $K_{5,9}$ plus a disjoint edge. I suspect that the answer to my question is also no.

Remark: A similar question where the smallest counterexample has $181^2$ ``edges'': http://www.math.bas.bg/serdica/1995/1995-219-230.pdf

Update: I know this holds for $k\le 3$ even for general graphs.

Answer 1

Not an answer, but I like this question, so I decided to document a dark alley I went down which should be avoided (or more optimistically tweaked).

Begin Dark Alley.

Initially, I tried to get a counterexample out of purely number theoretic considerations. That is, let $2^{2k-1}-1$ be a Mersenne prime. Let $G$ be the graph consisting of the complete bipartite graph $K_{2^k+1, 2^k-1}$ together with an isolated edge $e$. Note that $G$ contains exactly $2^{2k}$ edges. Let $H$ be an induced subgraph of $G$ with exactly $2^{2k-1}$ edges. Note that if $e \in H$, then $K_{2^k+1, 2^k-1}$ contains an induced subgraph with exactly $2^{2k-1}-1$ edges. But this is impossible since $2^{2k-1}-1$ is prime. Unfortunately, $K_{2^k+1, 2^k-1}$ itself has an induced subgraph with $2^{2k-1}$ edges, by taking a subset of size $2^{k}$ from the left side and one of size $2^{k-1}$ from the right side. This is yet another instance of Douglas Zare's comment of don't try to make a counterexample which is a complete bipartite graph plus a few edges.

End Dark Alley.

Answer 2

It's possible I messed up in my calculations, so by all means check it to be sure, but I think the following is an example of what you seek:

Start with a copy of $K_{5,103}$ with vertices $v_1\ldots v_5,w_1\ldots w_{103}$ and remove the edges $v_iw_i$ for $1\leq i\leq 5$. Add two copies of $K_2$ to make a total of 512 edges. Then unless I messed up somewhere in my calculation, no induced subgraph can have exactly 256 edges in it.

There were another of other near misses I found (similar initial setups which had exactly 1 way (up to relabelling of vertices) to remove vertices leaving exactly 256 edges), so it shouldn't be hard to modify this construction to find an example if it turns out the above example fails after all.

Answer 3

Domotorp and ARupinski likely know this already, but I thought I would record this as an initial foray into cornering a counterexample by a process of elimination. I will not bother with the general case, but focus on the specification of 256 out of 512. Let G be the collection of all bipartite graphs with 256 edges.

I will consider bipartite graphs only, and my concern is with the size of the smaller vertex set and how many edges can come from it. Certainly any node with degree at least 256 will contain an induced subgraph from G. Further any two nodes in the small set with combined degree of 256 or greater will also contain a subgraph from G. There is likely a better characterization than the following: any three vertices with combined degree of 383 and any 4 vertices with combined degree of 510 will produce a subgraph from G. (Note I am focusing on small independent vertex sets.)

Of course we can ignore vertices of degree 0. If we can characterize nicely the graphs with, say, an independent set of 3 vertices and a large number of edges (but fewer than 383) which do not have a subgraph from G, we might be able to use this to classify such graphs with larger independent sets, working our way up to 23 vertices, the rough square root of 512.

EDIT 2012.11.11 Unfortunately the analysis below is not quite right. One can find a subgraph of $K_{4,96}$ with $3*96=288$ edges which contains no induced subgraph from G. It turns out that if there are enough edges and the degrees of the larger set are anything but a multiset of 3's with at most one 2, then the conclusion holds and indeed $267$ edges are enough. I am confident that this line of investigation will produce something useful, but the treatment below is not enough. In particular, I am now unsure there is no counterexample which is not a subgraph of, say, $K_{7,n}$ for some $n$. END EDIT 2012.11.11

EDIT 2012.11.09 This problem is not exactly one about submultisets of integers and number theory, but taking that slant cuts a wide swath in the forest of bipartite graphs on 512 edges.

The major reason for needing 382 edges coming from 3 independent points while requiring less than 270 points coming from 4 independent points can be viewed as purely number-theoretic: given a=3 and b=127, there are no integers c and d such that $0 \leq c \leq a$ and $0 \leq d \leq b$ and $cd=256$. So $K_{3,127}$ is a graph of 381 edges which has no induced subgraph belonging to G. However, number theory can be used to show 382 edges from 3 points suffice, as we can either remove one of the three points and work with the remaining 2, or we look at the one point with degree 128 and note it has enough neighbors of the right degree that we just need to remove neighbors of degree 3 (or smaller degree if we run out) to achieve an induced subgraph from G.

That 4 points requires a lot fewer edges results from just needing enough residue classes mod 4 to take care of any problems: either there is a $K_{4,64}$ subgraph hidden, or there are at least enough vertices of degree 1,2, and 3 to adjust the sum mod 4. As a result, it is clear that $252+ 4*3$ is enough edges to find a subgraph from G, so let's be generous and say a combined degree of 280 suffices for 4 vertices.

We can now leverage that estimate and say that for 5 (and 6 and 7) vertices that 350 (and 420 and 490) edges respectively between them are enough to find a subgraph from G, either by removing neighbors of the 5 vertices, or by removing the vertex among the five with smallest degree, reducing it to a previous case.

Since 8 divides 256, we need either find a subgraph of the form $K_{8,32}$ or enough vertices of smaller degrees to finish the job. Rough estimates give 304 as a sufficient combined degree, which we can now leverage to say that no counterexamples on 512 edges from 13 vertices will be found.

Likely we can extend it by analyzing the case of 12 vertices further, but I will save that for later. I now suspect that domotorp will not get his counterexample for bipartite graphs with $2^n$ edges for $n \lt 10$. END EDIT 2012.11.09

Gerhard "Inching His Way Toward Bounty" Paseman, 2012.11.08

Answer 4

Even though this is not a complete answer, there are enough elements in this posting that I think someone can use to show domotorp where not to look for a counterexample. I also want to separate it from the marginally useful clutter in the other post of mine. Recall that I am focused on showing every bipartite graph H with exactly 512 edges has a subset of vertices which yields G, our target of an induced subgraph of H with exactly 256 edges.

A useful fact: if n is a prime power, if M is a multiset of positive proper divisors of n with sum equal to n, then there is a submultiset M' of M with sum kn/p, where k and p are positive integers, k is less than p, and p is the prime dividing n. A corollary of this fact is that any positive number of independent vertices whose degree sum is at least 256 and whose neighbors have degrees which are precisely powers of 2 will have an induced subgraph G on precisely that set of independent vertices. Edit: so that the corollary reads correctly, assume a subgraph H of K_a,b with degree sum of the a vertices at least 256 and the degrees of the b vertices are appropriate powers of 2. Then G subgraph of K_a,b' exists as an induced subgraph of H. End Edit.

From the corollary we get that domotorp won't find any counterexample graphs H which are subgraphs of K_a,b for a=1 or a=2. Further, for a=3 or 4, there won't be any counterexamples because at least two of the independent vertices of H will have degree sum at least 256. However, I want to refine the case of a=4 a bit.

Let J be a subgraph of K_4,b with number of edges n = 256 + 3k for some nonegative integer k. Then J also has an induced subgraph G: remove the b vertices of degree 3 and whatever else is needed to achieve the target number of edges. If J has a wealth of degrees, remove vertices of degrees 1,2, or 4 until n=256+3k as above. Otherwise J has less than 264 edges or else the b vertices all have degree 3, with at most one exception which must be of degree 2. Now from the four independent vertices, remove from J that vertex which has smallest degree. The result will either have less than 260 edges, or will have a b vertex of degree 1 or at least two of degree 2, or a single edge will be removed leaving a K_3,b subgraph. In the first case J had less than 350 edges, the second and third cases will yield the goal graph G, and the final case will yield no G unless b is at least 128. The upshot is that if J has more than 381 edges, it will have a target graph G as an induced subgraph.

I worried the case a=4 to bits for a couple of reasons: one is to establish that any H which is a subgraph of K_5,b will have four of the five independent vertices with degree sum more than 400 (and thus will not be a counterexample), and two is to put a Rube Goldbergian type cap on this post for a=6. This proof idea is neat, and might be extendible, but I am going to give others the chance to do it.

Let H be a subgraph with 512 edges and be a subgraph of K_6,b. Note that if any two of the six independent vertices have degree sum at least 256 or any of those six has degree less than 12, I can turn to cases for a=2 and a=5 and assert that a target G exists.

I will now find four of the six vertices and hope that there is a G that uses those vertices. Note that we may assume the four vertices have degree sum at least 256.

First consider the degree sums of the six mod 3. The sum of the sums is 2=512 mod 3. Suppose two of the degrees mod 3 are 2. Then the remaining four have degree sum equal mod 3 to 256, so I can use that to produce G. So assume at most one of the six degrees is 2 mod 3. Then if there is one other nonzero degree mod 3, there is at least one which is zero mod 3, and those two I exclude from the four to get another degree sum equal mod 3 to 256, and again I get G. The remaining case that resolves nicely is if none are 2 mod 3, and again I can find G.

The last case is that one of the six vertices has degree 2 mod 3, and all the rest are 0 mod 3. Of the remaining 5, I can try to choose some subset of 4 and hope for that subgraph to not fall in the case where the multiset of b vertices foils me by having all threes or all threes and one two. But if I am so unlucky, then I take all 5 vertices to get a degree set with some fours or some ones, as well as some threes or twos (remember at least 12 degrees will be incremented, although some of them might have started at 0). So I can guarantee a multiset of degrees that allow the composition I want, and gain my prize graph G.

The things I do for bounty!

Gerhard "Wait Till You See Seven" Paseman, 2012.11.14

Answer 5

You are right Dear domotorp,

Suppose the second largest eigenvalue of bipartite graph $G$ is one, i.e, $\lambda_2=1$. In this case, $G$ belong to the finite type, (there are infinite number of such graphs), bipartite graphs. With some calculation, we can see that your conjecture is true for this type of graphs. Also, we can say more, if we use some other spectral techniques.

The Paper Reference:

Petrovic M., On graphs with exactly one eigenvalue less than -1, J. Combin. Theory Ser. B 52 (1991), 102-112.