Re: [sage-devel] Re: Is Brown's construction available in the graph component of sagemath?

[ni732h . sphl]

I just got it wrong.
I understand what you said and will implement Erdos-Renyi graph for sage.

Where can I read your GAP code?
I want to read it for study. 

yawara


On Wednesday, October 19, 2016 at 11:29:27 PM UTC+9, Dima Pasechnik wrote:
>
>
>
> On Wednesday, October 19, 2016 at 7:05:23 AM UTC+1, ywr nn wrote:
>>
>> hi, Dima!
>>
>> In my context, for every power of primes q, Brown's construction gives a 
>> graph with order q^2+q+1, maximum degree q+1, diameter 2.
>> The graph is not a regular one. The degree sequence of the graph is 
>> [(q+1)^(q^2), q^(q+1)].
>> This Brown's construction gives known largest lower bounds for the 
>> degree-diameter problem for the case of diameter 2.
>>
>> Is not this construction called "Brown's construction" in graph theory?
>>
>
> Well, as I said, it was also discovered simultaneously and independently 
> by Erdós and Rényi (see e.g. 
> http://www.combinatorics.org/ojs/index.php/eljc/article/download/v22i2p21/pdf
> for a short discussion on this)
>
> Does this sound right to you?
> Dima
>
>
>
>> yawara
>>
>> On Mon, Oct 10, 2016 at 8:52 PM, Dima Pasechnik  wrote:
>>
>>>
>>>
>>> On Sunday, October 9, 2016 at 9:10:50 PM UTC, ni732...@gmail.com wrote:

 Brown's construction is the function which takes a finite field to a 
 graph with diameter 2.
 http://www.emis.ams.org/journals/EJC/Surveys/ds14.pdf

 Is it available in the graph component of sagemath?

>>>
>>> I won't be surprised if it could be constructed as a subgraph of one of 
>>> many strongly regular graphs
>>> known to Sage, but there is no direct way to build such a graph in Sage, 
>>> IMHO.
>>>
>>> The description of the adjacency in the link you provide is a bit too 
>>> brief to see what exactly it does, 
>>> but I think these graphs are also known as  Erdős–Rényi graphs, from 
>>> P. Erdós, A. Rényi, V.T. Sós
>>> On a problem of graph theory
>>> Studia Sci. Math. Hungar., 1 (1966), pp. 215–235
>>>
>>> Brown's paper was published in the same year: W.G. Brown
>>> On graphs that do not contain a Thomsen graph
>>> Canad. Math. Bull., 9 (1966), pp. 281–285
>>>
>>> We published a paper where these graphs were considered, and I 
>>> implemented
>>> a construction of them in GAP, but not in Sage :-)
>>> https://www.cs.ox.ac.uk/publications/publication7266-abstract.html
>>>
>>> Please feel free to cc me on the Sage ticket with an implementation, I'd 
>>> be glad to review it.
>>>
>>> Dima
>>>  
>>>
 If not, I plan to implement it for sagemath.

 yawara

>>> -- 
>>> You received this message because you are subscribed to the Google 
>>> Groups "sage-devel" group.
>>> To unsubscribe from this group and stop receiving emails from it, send 
>>> an email to sage-devel+...@googlegroups.com.
>>> To post to this group, send email to sage-...@googlegroups.com.
>>> Visit this group at https://groups.google.com/group/sage-devel.
>>> For more options, visit https://groups.google.com/d/optout.
>>>
>>
>>

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] Is Brown's construction available in the graph component of sagemath?

[ni732h . sphl]

Brown's construction is the function which takes a finite field to a graph 
with diameter 2.
http://www.emis.ams.org/journals/EJC/Surveys/ds14.pdf

Is it available in the graph component of sagemath?
If not, I plan to implement it for sagemath.

yawara

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.