Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am working on an exercise question asking me to "discuss the possibilities of a triangle-free strongly regular graph of order 100 and degree $d$".

Let $b$ be the parameter of the number of common neighbors of 2 non-adjacent vertices. Then pick any vertex $u$, it has $d-1$ neighbors, which must be pairwise non-adjacent for the graph to be triangle-free. Each of the neighbors of $u$ must therefore be adjacent to $d-1$ non-neighbors of $u$. So $d(d-1)$ edges run from neighbors of $u$ to non-neighbors of $u$. On the other hand, each non-neighbor of $u$ must connect to $b$ neighbors of $u$. So there are $b(99-d)$ edges running from non-neighbors of $u$ to neighbors of $u$.

So I get $d(d-1)=(99-d)b$. Having messed about this equation and double checked using all the theorems I know, I have only the following possibilities:

  1. The graph is empty
  2. The graph is 1-factor
  3. The graph is $K_{50,50}$
  4. The graph has $d=22$ and $b=6$.

I know that the first 3 possibilities are valid. I want to eliminate or prove the existence or even the uniqueness of the last possibility but have no idea how. I looked up a database and in fact the last possibility uniquely exists.

Can someone prove the existence and uniqueness of possibility 4?

share|improve this question
    
@AustinMohr: As you wish. –  hardmath Nov 24 '12 at 19:15
    
You should ask your professor what is expected of you. The best any of us can do is speculate what s/he expects from this question. A better question for this site is to prove or disprove the existence of item 4. –  Austin Mohr Nov 24 '12 at 19:36
    
Some interesting history, supplementing what you found in that "database" link, is recounted in these slides from a talk last year by Matan Ziv-Av. –  hardmath Nov 24 '12 at 20:06
add comment

1 Answer

It's hard to know what specifically is expected from the class on this exercise. You've gotten pretty far with the equation $d(d-1)=(99-d)b$. I'd guess tested for what values $b \lt d$ and perhaps applied some of the algebraic conditions counting eigenvalue multiplicity to isolate $d = 22$ and $b = 6$ as an interesting possibility.

Dale M. Mesner was the first to prove existence of such a triangle-free strongly regular graph (tfSRG) on 100 vertices. The result appears among others in his 1956 (unpublished) dissertation, An investigation of certain combinatorial properties of partially balanced incomplete block experimental designs and association schemes, with a detailed study of designs of Latin square and related types (Michigan State University).

Existence can of course be shown by exhibiting the tfSRG. It's more economical to present an equivalent BIBD design related to the non-edge pairs of the graph, which can be given as 77 blocks of size 6 on 22 points. As Mesner states in a 1964 paper, Negative Latin Square Designs: "The author conjectured that the design did not exist in this case, undertook an empirical search in hopes of proving its nonexistence, and in the course of the search inadvertently constructed it."

Uniqueness of that graph is also not all that easy or illuminating. Again I point out a quote from Mesner's 1964 paper: "In the next theorem [Thm. 8.7] we have attempted to steer between tedium and nonproof by giving enough details that the interested or suspicious reader can fill in the rest." This theorem is the uniqueness of the design.

The slides of Matan Ziv-Av's talk explain Mesner's work in some detail and relate it to subsequent (and ongoing) research efforts.

share|improve this answer
    
This should be a comment rather than an answer. –  Austin Mohr Nov 24 '12 at 19:13
    
After the changes made recently, it seems like a good answer. It suggests to me that it's probably too hard to prove the existence and uniqueness and thus suggests what the OP has found is about all the professor wants to hear. But, if the OP wants to go further, it should provide all the OP needs. –  Graphth Nov 25 '12 at 17:18
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.