Conferenciantes invitados

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 N2, en ([1,n] x [1,n]) ∩ Z2 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 Zp x Zp , Zp-1 x Zp y en Zp-1 x Zp-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 Zp , la distribución de residuos cuadráticos en Zp o la distribución de las potencias gx, para g un generador de Fp , 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.