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

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.

-
Is there some reason you would believe this to be true? –  Igor Rivin Nov 6 '12 at 22:20
It's hard to make a counterexample like $K_{a,b}$ plus a few edges, since these would contain an induced complete bipartite graph with parts of size $2^{\lfloor \log_2 a \rfloor},2^{\lfloor \log_2 b\rfloor}$. –  Douglas Zare Nov 7 '12 at 2:51
Trivial comment: It does work for trees with an even number of edges. Just successively remove leaves until half the edges remain. –  Tony Huynh Nov 7 '12 at 11:48
Is 512 / 256 just chosen randomly to make the question more memorable? Or do you know stuff about graphs with 16, 32, 64 etc edges. –  Gordon Royle Nov 8 '12 at 6:43
Just randomly to keep the question tex-free and simple. –  domotorp Nov 8 '12 at 10:57

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.

-

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.

-
Remove 50 of the degree 5 vertices, one of the degree 4 vertices, and all of the degree 1 vertices. Looks tweakable though. Gerhard "Back To The Bipartite Farm" Paseman, 2012.11.06 –  Gerhard Paseman Nov 7 '12 at 4:33
If you are going to tweak it, you have to avoid an extra edge plus K5,51; similarly K4,64 and 4 edges plus Kp,252/p will also be problems. Gerhard "Looks Like Counterexamples Completely Obstructed" Paseman, 2012.11.06 –  Gerhard Paseman Nov 7 '12 at 4:44
Nice try but Gerhard's first comment shows how to cut it. –  domotorp Nov 7 '12 at 7:41
Here is another near miss that might be salvaged. Take K13,29, and take another point and make it degree 5 into the (previously) complete graph while keeping the result bipartite. This also fails, but it seems to fail in not many ways. There might still be a counterexample that is not far from a complete graph. Gerhard "Ask Me About System Design" Paseman, 2012.11.07 –  Gerhard Paseman Nov 7 '12 at 16:54
Interesting... somehow I didn't notice that $K_{4,64}$ sitting in there. I need to go look at the loops I ran to figure out why they didn't detect it. –  ARupinski Nov 7 '12 at 22:30

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

-
It looks like $K_{3,127}$ does not contain an induced subgraph from G, but it seems I can replace 383 by 382 in the above, and the number 510 can probably be substantially lowered to below 300. Gerhard "I'm Surprised Too. Go Figure" Paseman, 2012.11.09 –  Gerhard Paseman Nov 9 '12 at 19:36
I think I see a way to show that any counterexample with 512 edges needs to have at least 14 vertices in the smaller set . It may be a quicker path to show the answer is actually yes. Gerhard "Race You To A Proof" Paseman, 2012.11.09 –  Gerhard Paseman Nov 9 '12 at 19:59
Here is where I could use some help: I think $K_{12,31}$ has no subgraph from G and thus we need 372 + 4*11 edges from 12 vertices. If so then we can push 13 to 14. Gerhard "Is It Just My Imagination?" Paseman, 2012.11.10 –  Gerhard Paseman Nov 10 '12 at 21:58
Actually, I can argue more comfortably: either $K_ {14,32}$ is a subgraph or else we have 31 vertices of degree at most 14 and 4 more vertices to make up the lack, so 486 edges from 14 vertices is sufficient to find a graph from G. Gerhard "Ask Me About System Design" Paseman, 2012.11.10 –  Gerhard Paseman Nov 10 '12 at 22:11
Hi Gerhard, I cannot follow everything (like if there is no K_{14,32} subgraph, then why is it guaranteed that we have 31 vertices of degree at most 14?) but I do hope your approach will lead to a counterexample. –  domotorp Nov 11 '12 at 7:15

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

-
Looks like a=7 will be easy. Take the 4 vertices from the seven with largest degree sum. If there is no G, then the b multiset will be mostly threes, so change it by adding a fifth vertex. Gerhard "Can It Be That Easy?" Paseman, 2012.11.14 –  Gerhard Paseman Nov 15 '12 at 6:32
This suggests a strengthening of domotorps conjecture. Let H be a bipartite subgraph of (a,b) independent vertices with a<=b and 512 edges, and let c=ceil(a/2). Let H' and H'' be the induced subgraphs having those c or c+1 vertices among the a vertices with maximal degree sum. Then G having 256 edges will be an induced subgraph not only of H but also of at least one of H' or H". This might be a statement that gordonroyle can use. Gerhard "Thoughts, One Cent; Conjectures, Two" Paseman, 2012.11.14 –  Gerhard Paseman Nov 15 '12 at 7:04
I don't see why this conjecture would be true. Although for 512 it might happen to be true, but e.g. for 128 it is easy to make a counterexample. Take a $K_{9,14}$ and add two independent edges. The only induced subgraphs with 64 edges are $K_{8,8}$ and $K_{7,9}$ plus an independent edge. –  domotorp Nov 15 '12 at 7:28
Maybe I should drop the condition a<=b. Anyway I am doing my best to provide potential solution paths, even if I can only handle the cases of a < 8 currently. Gerhard "Missed It By That Much" Paseman, 2012.11.15 –  Gerhard Paseman Nov 15 '12 at 15:38
Try this: Let H have 512 edges inside K_a,b. Pick c which is half (or a little more) of the a vertices with degree sum >= 256. If you can't find a subset of the at most b many vertices to induce a subgraph using the c vertices, the induced degree multiset is quite restricted (has all but at most c-2 members with the same value, or the degree sum is not far from 256). If adding another a vertex of moderate degree to the c vertices does not help, then H is real close to a K_d,f. Vague, but I think worth pursuing. Gerhard "Maybe This Arrow Will Hit" Paseman, 2012.11.15 –  Gerhard Paseman Nov 15 '12 at 20:00

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.

-
Can you please expand on your answer? I can't how to see to prove the conjecture for the class of bipartite graphs with $\lambda_2=1$. –  Tony Huynh Nov 12 '12 at 12:13
Dear Tony, the calculation is long for each type of those graphs. But, I checked two infinite classes and they were true. I will try to write my calculating for those cases(just is a computing), but I do not have free time these days. You can see the paper and directly see the result. I added the reference, I hope it can be helpful. –  Shahrooz Janbaz Nov 12 '12 at 20:48
If they are long, it might not be important to work out the details at this moment, as probably a counterexample exists. But if you have time, I am more than happy to read it. –  domotorp Nov 12 '12 at 21:28