Conferenciantes invitados

• Cilleruelo, Fco. Javier
  Universidad Autónoma de Madrid.
• Felsner, Stefan
  Technische Universität Berlin.
• Miller, Mirka
  The University of Newcastle. Australia.

Resúmenes de las conferencias

---

Cilleruelo, Fco. Javier

Conjuntos de Sidon bidimensionales y aplicaciones

Abstract. Los conjuntos de Sidon son aquellos con la propiedad de que todas las diferencias de dos elementos son distintas en su espacio ambiente.

De especial interés para las aplicaciones son los conjuntos de Sidon bidimensionales. Estudiaremos en detalle estos conjuntos en N², en ([1,n] x [1,n]) ∩ Z₂ y en G x G' para dos grupos finitos G, G' dados. Veremos las conexiones de estos conjuntos con los llamados "Costas arrays", de importantes aplicaciones industriales.

Determinadas construcciones de conjuntos de Sidon en Z_p x Z_p , Z_p-1 x Z_p y en Z_p-1 x Z_p-1 también nos permitirán presentar demostraciones puramente combinatorias de algunos resultados clásicos de teoría de números. En particular estudiaremos el último teorema de Fermat en Z_p , la distribución de residuos cuadráticos en Z_p o la distribución de las potencias g^x, para g un generador de F_p , cuando x recorre un intervalo pequeño.




---

Felsner, Stefan and Knauer, Kolja

Distributive lattices from graphs

Abstract. Several instances of distributive lattices on graph structures are known. This includes

• c-orientations (Propp)
• α-orientations of planar graphs (Felsner/de Mendez)
• planar flows (Khuller, Naor and Klein)

as well as some more special instances, e.g., spanning trees of a planar graph, matchings of planar bipartite graphs and Schnyder woods.

We give a new characterization of distributive lattices in terms of edge colorings of their Hasse diagrams. This is used to show distributivity of the above and of more general instances. These studies led to a more geometric point of view.

Let a D-polytope be a polytope that is closed under componentwise max and min, i.e., the points of the polytope are an infinite distributive lattice. A characterization of D-polytopes reveals that each D-polytope has an underlying graph model. The associated graph models have two descriptions either edge based or vertex based. A translation between the two models and a characterization of the vertices of D-polytopes involves spanning-trees.




---

Miller, Mirka

Advances in the degree/diameter problem

Abstract. In extremal graph theory, there is a well-known fundamental problem called the degree/diameter problem, which is to determine the largest (in terms of the number of vertices) graphs or digraphs of given maximum degree, respectively, maximum out-degree, and given diameter. General upper bounds, called Moore bounds, exist for the largest possible order of such graphs and digraphs of given maximum degree Δ (respectively, maximum out-degree d) and diameter D (respectively, diameter k).

In recent years, there have been many interesting new results in both the undirected and directed versions of the problem, resulting in improvements in both the lower bounds and the upper bounds on the largest possible number of vertices. However, quite a number of open problems regarding the degree/diameter problem do still exist. Some of these problems, such as constructing a Moore graph of degree Δ = 57 and diameter D = 2, or proving that such a graph cannot exist, have been open for 50 years.

In this talk we will present an overview of the degree/diameter problem for both undirected and directed graphs and we outline several open problems.