22
$\begingroup$

Let $e_6(n)$ be the greatest number of edges in a simple graph with $n$ vertices and girth at least 6. Let $G_6(n)$ be the set of simple graphs of order $n$ with girth at least 6 and $e_6(n)$ edges.

My question: Is there any $n$ for which none of the graphs in $G_6(n)$ is bipartite?

From computer experiments, I have found that the only values of $n\le 50$ for which $G_6(n)$ has any non-bipartite graphs at all are 7 (7 edges), 9 (10 edges), 15 (22 edges), 27 (53 edges), and 43 (106 edges). However, in all those cases $G_6(n)$ includes bipartite graphs as well.

A table (needs checking, please don't cite yet): "[n=44,e=108,g=12]" means $e_6(44)=108$ and there are 12 graphs. All the graphs are bipartite unless the notation is like "[n=15,e=22,g=2+1]" which means there are two bipartite graphs and one non-bipartite graph.

[n=5,e=4,g=3], [n=6,e=6,g=1], [n=7,e=7,g=1+1], [n=8,e=9,g=1], [n=9,e=10,g=3+1], [n=10,e=12,g=3], [n=11,e=14,g=1], [n=12,e=16,g=1], [n=13,e=18,g=1], [n=14,e=21,g=1], [n=15,e=22,g=2+1], [n=16,e=24,g=4], [n=17,e=26,g=4], [n=18,e=29,g=1], [n=19,e=31,g=1], [n=20,e=34,g=1], [n=21,e=36,g=3], [n=22,e=39,g=2], [n=23,e=42,g=1], [n=24,e=45,g=1], [n=25,e=48,g=1], [n=26,e=52,g=1], [n=27,e=53,g=2+2], [n=28,e=56,g=1], [n=29,e=58,g=1], [n=30,e=61,g=1], [n=31,e=64,g=1], [n=32,e=67,g=5], [n=33,e=70,g=3], [n=34,e=74,g=1], [n=35,e=77,g=1], [n=36,e=81,g=1], [n=37,e=84,g=3], [n=38,e=88,g=2], [n=39,e=92,g=1], [n=40,e=96,g=1], [n=41,e=100,g=1], [n=42,e=105,g=1], [n=43,e=106,g=2+3], [n=44,e=108,g=12], [n=45,e=110,g=183], [n=46,e=115,g=1], [n=47,e=118,g=1], [n=48,e=122,g=1], [n=47,e=118,g=1], [n=48,e=122,g=1], [n=49,e=126,g=1], [n=50,e=130,g=1].

Update Nov 2015: For $51\le n\le 63$, all extremal graphs are bipartite except for $n=63$, where there are 3 bipartite extremal graphs and 4 non-bipartite extremal graphs (187 edges).

$\endgroup$
16
  • $\begingroup$ For those of us less adept but still wanting to play, can you comment briefly on how e_6(n) can be nicely estimated? Gerhard "Hopes For Easy And Good" Paseman, 2012.06.15 $\endgroup$ Jun 16, 2012 at 6:19
  • $\begingroup$ This is a rough/nonprecise estimate of $e_6(n).$ The odd graph $O_n$ ($n >3$) has $O(n)$ vertices and $O(n^2)$ edges and girth precisely 6. $\endgroup$
    – Jernej
    Jun 16, 2012 at 9:28
  • $\begingroup$ @Brendan is there a graph in $G_6(n)$ for some $n$ with girth greater than 6? $\endgroup$
    – Jernej
    Jun 16, 2012 at 9:31
  • $\begingroup$ @Jernej: The only example up to 44 vertices is the 7-gon. I doubt there are any others, but I don't know a proof. $\endgroup$ Jun 16, 2012 at 15:17
  • $\begingroup$ @Jernej: The odd graph $O_n$ that I know has exponentially many vertices. The one on 35 vertices has 70 edges, compared with $e_6(35)=77$. $\endgroup$ Jun 16, 2012 at 15:22

2 Answers 2

2
$\begingroup$

I am collecting some varied thoughts on the problem, in the hopes that it will inspire someone to finish the problem.

I suggested earlier that the graphs in $G_{n+1}$ could be built incrementally from graphs in $G_n$ by adding one vertex and thee appropriate number of edges. Brendan McKay assured me that this would not be possible for $n=44$ as "that graph had too many edges", to reinterpret his assurance. Even so, it might be useful to consider the subgraph relation on the union of the $G$'s and see if most of them can be built up incrementally, and to characterize the ones that aren't and are primitive in some sense.

It is clear that removing one vertex and its adjacent edges from an example in $G_{n+1}$ does not reduce the minimum girth, and that adding a vertex and single edge also does not reduce the girth, so that the function $e(n)$ is increasing in $n$ for $n>4$ and further increases by no more than the minimum degree taken over all the vertices of all the members of $G_{n+1}$.

There likely is a nice argument bounding the maximum degree among all members of $G_n$, but I don't see it. I can build a graph on an even number of vertices by gluing a number of length 3 paths together at their endpoints, but this gives an average degree of slightly less than 3 and a max degree of slightly less than n/2, so this is useful more for providing a lower bound for $e(n)$ than anything else.

Another construction giving a bipartite involves associating each point in a set L with a small subset (of size 3, say) of another set R in a way that no two subsets of R so chosen intersect in more than one point. The result has girth 6 or more and if both L and R have 7 points, a maximal example resembles a BIBD (or for me, an adjacency matrix of 0's and 1's with order 7 and absolute determinant value of 24) which I believe corresponds to Brendan's example for $n=14$. Perhaps BIBD's contribute more examples? They might be a significant subclass of the primitive graphs in the subgraph relation I mention above.

Also, why so many graphs for $n=45$? It makes me think of the combinatorial explosion of equivalence classes of Hadamard matrices, although it might be better to think of equivalence classes (under row and column permutations and perhaps under switching as well) of 0-1 matrices having maximal determinant values. Are there combinatorial analogues in the literature which might suggest such a brief plethora of examples?

Gerhard "Binary Matrices On My Mind" Paseman, 2012.06.28

$\endgroup$
0
1
$\begingroup$

It seems I have an answer to my own question, though credit belongs to my computer. Namely, $e_6(47)=118$ and the unique graph in that class is not bipartite. I wish I could offer some insight, but at the moment it is a mystery.

Very sorry, that was incorrect. I must have been looking at the wrong file. Up to $n=48$ vertices inclusive there is always at least one bipartite graph with $e_6(n)$ edges. So the problem remains open.

$\endgroup$
3
  • $\begingroup$ Are you confident enough of your results to list some of them here? In particular I am thinking of a table listing e_6(n) and (the number of isomorphism types of) G_6(n)? The more courageous of us might attempt to verify/alternatively derive your computations. Gerhard "Still Checking My Courage Meter" Paseman, 2012.06.25 $\endgroup$ Jun 25, 2012 at 7:32
  • $\begingroup$ @Gerhard: I added a table, but the program and the output need a lot of checking yet before I'd swear to it being correct. $\endgroup$ Jun 25, 2012 at 14:40
  • $\begingroup$ Thank you for the table. Do the results follow your intuition? I'm surprised at the number of occurrences of "g=1]" in the table. Gerhard "Ask Me About System Design" Paseman, 2012.06.25 $\endgroup$ Jun 25, 2012 at 17:24

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.