Collineation groups of finite projective planes and Graph Isomorphism.

Disclaimer. Esta es la re-publicación de una entrada anterior (de 2009 o 2010) que hemos reeditado para la ocasión, por el reciente breaktrough en relación al problema de isomorfismo de grafos, sobre el que todavía no se conocen detalles. Seguramente el método por el que Babai ha mejorado la cota superior para este problema no tiene nada que ver con el contenido de la entrada. 

Hubo un tiempo en que uno leía sobre estos temas  y era como leer el periódico: me entraban con total facilidad. Me interesaban mucho y les dedicaba tiempo. Eso era antes de recibir golpe tras golpe en las tramitaciones de las patentes.

Ya se sabe que el sistema de patentes está diseñado para estimular la publicación de nuevos resultados, no para estimular la investigación en sí: es un señuelo en el que sólo se pica una vez, salvo que te vaya bien, cosa que ocurre en la  minoría de los casos. En general, y salvo casos extremos, el que ha probado una vez no repite por esta vía (esta tortura) y lo normal es  que se dedique  a otras cosas que no tengan nada que ver con la invención / investigación.  Esta es la experiencia de un toro que salió con mucha fuerza a la plaza (es decir con mucho entusiasmo,  con mucha ilusión, con muchas ganas, sobre todo por partir con un buen resultado, una invención genuina, con potenciales aplicaciones) y al que, tras tercios de  Bilski varas y Alice Corp banderillas brutales, sobre todo el segundo, ya solo le queda que le den la puntilla

¿ Son más satisfactorias las  otras vías del investigador, como  la academica con financiación pública ? ¿ Hay alguna diferencia entre preparar solicitudes de patente que nadie se va a leer, ni siquiera el examinador, y preparar solicitudes de financiación de proyectos de investigación ? ¿ Se leen los funcionarios que conceden las subvenciones las propuestas ? ¿ Es menos arbitraria la concesión de las segundas que la  de las primeras ? Desconozco las respuestas a estas preguntas, pero de una manera o de otra, la mayor parte del tiempo se invierte en redactar documentos que nos son de investigación dirigidos a individuos que no  los van a comprender.

Luego seguramente no hay mucha diferencia. Ok, hay una gran diferencia: el que va por la vía de la patente paga por rellenar impresos mientras que al que va por la vía de la academia le pagan por hacer lo mismo. Yo me refiero a que ninguno de los dos,  salvo el que obtiene rendimientos por la vía de la patente o el que consigue una subvención (también hay investigadores estrella que consiguen cuantiosos premios que les permite  una independencia financiera y una investigación libre), tiene al  final tiempo para investigar que es lo que se supone que le gustaría hacer. 

Quiero recordar que considero que la respuesta a mi  segunda solicitud de patente es una auténtica tomadura de pelo, un impresentable pitorreo a mi costa y altamente ofensivo teniendo en cuenta los recursos invertidos, y una falta de respeto al inventor en general, indigno de una institución de un país avanzado como es EEUU y demuestra que el examinador, tras más de seis años de tramitación,  o bien no se ha leído la solicitud y no conoce la innovación en detalle o está actuando de mala fe. Se mire por dónde se mire, con las reglas en la mano (Interim Guidances y Examples), incluso después del caso Alice corp, la segunda solicitud se debe de conceder. Ya hemos señalado a tres responsables: examinador, supervisor y dirección de la USPTO (la directora). Y ya hemos comentado que esperamos que con la respuesta que ya tenemos  preparada (estamos dándole la última revisión) la decisión sea otra.   

Ahora no es que aborrezca estos temas pero he perdido grandemente el interés, les dedico mucho menos tiempo y realmente me cuesta enterarme, incluso de lo que escribí yo. Ya no es como leer un periódico, sino más bien como leer un ensayo de un filósofo post-moderno. Por lo tanto advierto que la entrada puede contener errores.  

Está en inglés (y puede contener erratas o errores gramaticales) y debido a la elevada erosión que  sufre la web con el paso del tiempo, muchos enlaces fallarán.

Añadido posterior. Al  inicio de la entrada había un párrafo relacionado con mi propia investigación que he eliminado pues luego concluí que lo que describía en él era incorrecto.

No recuerdo qué es lo que me llevó a la hipótesis del primer párrafo que he dejado. Lo dejo tal cual ya que si lo elimino ya tendría que empezar a modificar el resto de la entrada.

Posiblemente la siguiente proposición:

Proposition 4. Testing isomorphism of graphs with bounded valence is polynomialtime reducible to the problem of determining generators for Aute (X ), where X is a connected graph with the same valence, and e is a distinguished edge.

Una presentación reciente (2014) del método de Babai para los diseños de Steiner (que eran algunos de los casos que habían identificado como más complicados para este problema). Diría que la situación es muy parecida a la que hemos descubierto en el problema de recorridos hamiltonianos en los Dígrafos de Cayley bigenerados (versión decisión):  los casos más difíciles tienen menos grados de libertad (el tamaño del grupo de automorfismos no llega a explotar exponencialmente) y por ello la complejidad queda controlada (cuasipolinómica de momento). ¿ Llegará a polinómica ?, se pregunta todo el mundo…En cuanto a los casos fáciles, no tengo claro la situación: o bien los casos fáciles son los que teniendo más grados de libertad es sencillo encontrar la diferencia entre los dos grafos o aunque tengan un grupo de automorfismos exponencial no hace falta explorar todo el grupo para determinar que son iguales. Ya digo que esto último no lo tengo claro.

Fin añadido. 

Some considerations has led us to stablish the following working hypothesis: the hard cases for the isomorphism problem over combinatorial structures represented in normal form are also those for which the automorphism group is two-generated.

And the desire to check this hypothesis has led us to study if the collineation groups of finite (desarguian) projective planes are two generated (this search has been inspired by the content of this thesis). In this post we plan to clarify or at least to collect links about this research.

Añadido posterior. El enlace anterior falla. La tesis citada es: Efficient algorithms for graph isomorphism testing (esperamos que este enlace supere la fuerte erosión de los próximos años) en la que el autor nos comenta sobre cuales son las familias de grafos más complicadas para cualquier algoritmo de GI. Fin añadido.

Projective planes.

Let´s first recall that the theory of projective planes is a subtheory of the theory of combinatorial designs. Also of interest. As we can see in the previous link there are many of those (although most if not all can be described by the triple SET, SUBSET, RESTRICTIONS OVER SUSETS), and in this post we will focus almost exclusively on the theory of finite projective spaces.

Good introductory preliminaries in the introduction of this, where they inform that standard references for finite geometries are:

–Dembowski´s Finite geometries,

–Beth, Jungnickel and Lenz´s Design Theory and,

–for projective planes Hughes and Piper´s  Design Theory.

In Projective planes PG(2, n), n is the order of the plane which has a number of points / planes shown to be equal to: n^2+n+1. In the Desarguian planes PG(2, q), which are the classical examples, q is a prime power and points and lines are the 1-and 2-dimensional subspaces of the vector space GF(q)^3, respectively and a point is incident with a line iff it is a subset of the line (a well known example is the Fano plane, the unique Desarguian plane of order 2, up to isomorphism). Though I´m looking for introductory papers, this kind of groups seems quite general so that most papers are quite specialized.

As every other field of mathematics, this one has central conjectures and theorems:

–A first important theorem, which situates projective spaces within the more general setting of combinatorial designs is the Dembowski-Wagner theorem (see this paper).

–When restricted to projective spaces, a first important negative theorem is the Bruck-Ryser theorem and,

–for construction purposes the theorem that relates latin squares with projective planes (see this paper).

Automorphism groups  of projective planes.

Of more interest for our purpose is the conjecture par excellence in this field,  the prime power order conjecture. Since all known projective planes with transitive collineation group are Desarguesian (that is of prime power order) it has been conjectured that all such planes are Desarguesian.

The most celebrated theorem, related with this conjecture, is the Ostrom-Wagner (see their conjoint paper “On projective and affine planes with transitive collineation groups”), theorem that asserts that the conjecture is true for projective planes with 2-transitive collineation groups (see the very interesting introduction in  this paper) if a finite projective plane admits a collineation group acting doubly transitively on points, then the plane is Desarguesian and the group contains the Projective Special Linear group (some kind of PSL groups where of interest for us in previous posts).

On the other hand, as far as I know, there is not yet any equivalent to Frucht theorem for projective planes, unfortunately: see this paper.

Other links / papers of interest I have found so far are:

The entry of Springer Encyclopediae of Mathematics about projective planes with information about the finite and desarguian cases.

A paper about projective spaces in general including finite projective spaces, with a proof of the fundamental theorem of projective spaces, and about projective planes (see also this other paper  by an author which has published intensively in the field of permutations groups).  These papers comes from a lecture notes book (see the presentation chapter  ) that can be accessed through this link.

–The web page of an active author in the field, Professor William M. Kantor which also has published in the field of GI, as coauthor of Babai. A clear signal that the thread of research we are following has been already explored. Some papers of this author: one, two, three, four, five, six, seven and eight.

 —Ho, Chat Yin(1-FL). On the order of a finite projective plane and its collineation group.
Finite geometries and combinatorial designs (Lincoln, NE, 1987), 299–301, Contemp. Math., 111, Amer. Math. Soc., Providence, RI, 1990. 51E15 (20B25)

http://www.uwyo.edu/moorhouse/pub/psl3q.pdf and from the same author http://www.uwyo.edu/moorhouse/pub/psl2q.pdf.

http://www.combinatorics.org/Volume_13/PDF/v13i1r94.pdf

After reading in diagonal all this papers I have not clear if the hypothesis stands or not (possibly not). So, to be continued.

Terms and conditions: 1. Any commenter of this blog agrees to transfer the copy right of his comments to the blogger. 2. RSS readers and / or aggregators that captures the content of this blog (posts or comments) are forbidden. These actions will be subject to the DMCA notice-and-takedown rules and will be legally pursued by the proprietor of the blog.

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s


A %d blogueros les gusta esto: