European journal of combinatorics

Vol. 48, num. C, p. 48-62

DOI: 10.1016/j.ejc.2015.02.008

Date of publication: 2015-08-01

Abstract:

This paper is a contribution to the problem of counting geometric graphs on point sets. More concretely, we look at the maximum numbers of non-crossing spanning trees and forests. We show that the so-called double chain point configuration of N points has Omega (12.52(N)) non-crossing spanning trees and Omega (13.61(N)) non-crossing forests. This improves the previous lower bounds on the maximum number of non-crossing spanning trees and of non-crossing forests among all sets of N points in general position given by Dumitrescu, Schulz, Sheffer and Toth (2013). Our analysis relies on the tools of analytic combinatorics, which enable us to count certain families of forests on points in convex position, and to estimate their average number of components. A new upper bound of O(22.12(N)) for the number of non-crossing spanning trees of the double chain is also obtained. (C) 2015 Elsevier Ltd. All rights reserved.]]>

Proceedings of the American Mathematical Society

Vol. 143, num. 3, p. 925-936

Date of publication: 2015-03-01

Abstract:

Let G(n, M) be the uniform random graph with n vertices and M edges. Erdos and Renyi (1960) conjectured that the limiting probability; lim(n ->infinity) Pr{G(n, n/2) is planar}; exists and is a constant strictly between 0 and 1. Luczak, Pittel and Wierman (1994) proved this conjecture, and Janson, Luczak, Knuth and Pittel (1993) gave lower and upper bounds for this probability. In this paper we determine the exact limiting probability of a random graph being planar near the critical point M = n/2. For each lambda, we find an exact analytic expression for; p(lambda) = lim(n ->infinity) Pr {G (n, n/2 (1 + lambda(n-1/3))) is planar}.; In particular, we obtain p(0) approximate to 0.99780. We extend these results to classes of graphs closed under taking minors. As an example, we show that the probability of G(n, n/2) being series-parallel converges to 0.98003. For the sake of completeness and exposition we reprove in a concise way several basic properties we need of a random graph near the critical point.]]>

Abstract:

The project addresses a set of problems which are at the forefront of contemporary combinatorics. The main objectives include the following: an extension of Szemerédi type theorems for solutions of linear systems to the sparse setting, which is the arithmetic side of recent developments leading to random versions of Ramsey and density results in combinatorics; the extension to minor closed classes of graphs of the celebrated results on enumeration and parameter analysis of planar graphs, which involve the asymptotic probability distribution of significant parameters and may lead, among other results, to the first known subquadratic algorithm for 4-coloring random planar graphs; the study of a random model for tranversal matroids, which would be a novel contribution to random models for complex combinatorial structures; a longstanding conjecture of Stanley on the feasibility of h-vectors in matroids in terms of pure simplicial complexes, for which only few simple cases have been verified; the use of polynomial methods in the study of the so-called MDS conjecture, proved by one of the members of the team in the prime case, and the improvement of constants involved in Kakeya sets and of Bourgain sets in finite geometries, as well as their extensions to higher dimensions; the extension to the geometric setting of classical results in additive combinatorics, which is connected to the existence of a class of MDS codes in the space of bilinear symmetric forms with respect to a particular metric; the asymptotic analysis of pattern densities in permutations, a novel project strongly connected to extremal graph theory and the theory of graph limits. The treatment of these problems involves a development and interleaving of algebraic, geometric and probabilistic methods in combinatorics. Building a solid ground for this set of techniques is one of the side objectives of the proposal.]]>

International Conference of the Catalan Association for Artificial Intelligence

p. 227-236

DOI: 10.3233/978-1-61499-452-7-227

Presentation's date: 2014-10-22

Abstract:

A case study in a social multi-criteria evaluation framework for selecting a windfarm location in the regions of Urgell and La Conca de Barberà in Catalonia is presented. Two different MCDM approaches are introduced and compared through their application to the mentioned case. On the one hand, a Qualitative TOPSIS methodology able to address uncertainty and, able to deal with different levels of precision is considered. On the other hand, we consider the results obtained by a non-compensatory outranking MCDM method. Both approaches are analyzed and their performance in the selection of a windfarm location is compared. Although results show that both methods conduct to similar alternatives rankings, the study highlights both their advantages and drawbacks.]]>

International Conference on University Teaching and Innovation

p. 1-15

DOI: 10.13140/RG.2.1.2282.1282

Presentation's date: 2014-07-04

Abstract:

Desde el ICE de la UPC se ha planteado una nueva formación dirigida a todo el profesorado basada en la adquisición de competencias docentes. Uno de los módulos de formación puesto en marcha trabaja la adquisición de la competencia interpersonal. Hasta la fecha se han realizado dos cursos a lo largo del año 2013. En este artículo se detallan los contenidos tratados en el módulo y las experiencias desarrolladas por algunos de los profesores que lo pusieron en práctica. Promoted by the ICE of the UPC has been set a new training for all teachers based on the acquisition of teaching skills. One of the started training modules works the acquirement of interpersonal competence. For the time being there have been two courses, both developed throughout 2013. This article describes the content covered in the module and the experiences which were carried out by some of the teachers who implemented it.]]>

Computational geometry: theory and applications

Vol. 47, num. 5, p. 563-584

DOI: 10.1016/j.comgeo.2013.12.009

Date of publication: 2014-07-01

Abstract:

Two plane geometric graphs are said to be compatible when their union is a plane geometric graph. Let S be a set of n points in the Euclidean plane in general position and let T be any given plane geometric spanning tree of S. In this work, we study the problem of finding a second plane geometric tree T' spanning S, such that is compatible with T and shares the minimum number of edges with T. We prove that there is always a compatible plane geometric tree T' having at most (n - 3)/4 edges in common with T, and that for some plane geometric trees T, any plane tree T' spanning S, compatible with T, has at least (n - 2)/5 edges in common with T. (C) 2013 Elsevier B.V. All rights reserved.

Two plane geometric graphs are said to be compatible when their union is a plane geometric graph. Let S be a set of n points in the Euclidean plane in general position and let T be any given plane geometric spanning tree of S. In this work, we study the problem of finding a second plane geometric tree T' spanning S, such that is compatible with T and shares the minimum number of edges with T. We prove that there is always a compatible plane geometric tree T' having at most #n - 3#/4 edges in common with T, and that for some plane geometric trees T, any plane tree T' spanning S, compatible with T, has at least #n - 2#/5 edges in common with T. #C# 2013 Elsevier B.V. All rights reserved.]]>

Date of publication: 2014-02-05

Graphs and combinatorics

Vol. 29, num. 6, p. 1623-1631

DOI: 10.1007/s00373-012-1220-9

Date of publication: 2013-11-01

Abstract:

In this paper we study the extremal type problem arising from the question: What is the maximum number ET(S) of edges that a geometric graph G on a planar point set S can have such that it does not contain empty triangles? We prove:(Formula Presented). © 2012 Springer.]]>

European Conference on Combinatorics, Graph Theory and Applications

p. 283-290

Presentation's date: 2013-09

Abstract:

The present project aims to articulate the group's overall research activity, maintaining multiple cooperative lines of work, but at the same time enhancing a specific topic and introducing a new more exploratory aspect. The unifying bond is computational geometry, with emphasis on algorithmic problems related to the capture, identification or optimization of geometric shape, understood in a broad sense. We propose to study both the corresponding theoretical foundations, and initiate further exploration more targeted to applications, one on reconfigurable modular robots, another revolving around the type of discriminatory analysis proper to operational research. The scientific results obtained will be combined with the training of new researchers, and maintaining the group's presence and projection in the state and international arenas. This project is conceived as a continuation of MTM2009-07242, but with several significant differences, due both to current trends in the international research community and to some small changes in the composition of the group. We have grouped the issues to be investigated into two blocks, one more theoretical and the other more oriented towards applications; however, let us be clear that the latter is also quite theoretical. We proceed to briefly outline the contents of these blocks, by specifying some particular issues: A. Theory of discrete geometric shape: foundations, algorithms, optimization 1. Algorithmic study of families of symmetric polytopes and operations on them: Study of structural properties of discrete families of polytopes constructed from the spectrum of graphs with symmetry, and new operations on them, such as the tensor product. 2. Discrete sets: Algorithms for increasing the connectivity for simultaneous biplane graphs and problems of constructing compatible graphs sharing a minimum number of edges. Characterization of sets that support graphs with connectivity or regularity 4 or 5, but which may increase in two layers. Study of the rectilinear convex hull (RCH) of sets of points and objects: optimization of different parameters of the RCH, calculation of the non-oriented RCH optimizing area, perimeter, number of connected components, etc.; algorithmic applications to classification problems and grouping of geometric objects. 3. Location and dominance of vertices in combinatorial graphs: Study of various parameters related to the notion of convexity in graphs, such as location and domination. Upper and lower bounds of these parameters in terms of order and diameter. Relationship between the various parameters. Study of these parameters in some specific families of graphs. B. The road towards applications: two concrete aspects of the use of shapes 1.Reconfiguration of modular robotic systems: Efficient distributed algorithms based on local rules for solving tasks of self-organization and reconfiguration of lattice-based modular robotic systems. Generalization to a generic conceptual model that can be applied to most real and potentially existing prototypes. Proof of the correctness of the rule sets, the efficiency of the resulting algorithms, and of the connectedness of the reconfiguration space. Development of a simulator. Presentation and analysis of experimental results. 2.Geometric outlier detection: A study of the application of classical tools and algorithms of computational geometry in disciplines such as health, education and marketing, which must process large amounts of data that can be described geometrically. In particular, we will focus on the detection of data that are outliers according to some chosen criterion, and on the reliable estimation of missing values.]]>

Butlletí de la Societat Catalana de Matemàtiques

Vol. 28, num. 2, p. 183-231

DOI: 10.2436/20.2002.01.51

Date of publication: 2013

Random structures and algorithms

Vol. 42, num. 4, p. 438-479

DOI: 10.1002/rsa.20421

Date of publication: 2013

Abstract:

Consider a family equation image of 3-connected graphs of moderate growth, and let equation image be the class of graphs whose 3-connected components are graphs in equation image. We present a general framework for analyzing such graphs classes based on singularity analysis of generating functions, which generalizes previously studied cases such as planar graphs and series-parallel graphs. We provide a general result for the asymptotic number of graphs in equation image, based on the singularities of the exponential generating function associated to equation image. We derive limit laws, which are either normal or Poisson, for several basic parameters, including the number of edges, number of blocks and number of components. For the size of the largest block we find a fundamental dichotomy: classes similar to planar graphs have almost surely a unique block of linear size, while classes similar to series-parallel graphs have only sublinear blocks. This dichotomy was already observed by Panagiotou and Steger [25], and we provide a finer description. For some classes under study both regimes occur, because of a critical phenomenon as the edge density in the class varies. Finally, we analyze the size of the largest 3-connected component in random planar graphs.]]>

Graphs and combinatorics

Vol. 28, num. 3, p. 365-380

DOI: 10.1007/s00373-011-1055-9

Date of publication: 2012-05

Date: 2011-01-21

Discrete Mathematics Days

p. 335-346

Presentation's date: 2010-07

Abstract:

Consider a set of n pairwise disjoint axis-parallel rectangles in the plane. We call this set the source rectangles S. The aim is to move S to a set of (pairwise disjoint) target rectangles T . A move consists in a horizontal or vertical translation of one rectangle, such that it does not collide with any other rectangle during the move. We study how many moves are needed to transform S into T . We obtain bounds on the number of needed moves for labeled and for unlabeled rectangles, and for rectangles of different and of equal dimensions.]]>

SIAM journal on discrete mathematics

Vol. 23, num. 4, p. 2147-2155

DOI: 10.1137/090767947

Date of publication: 2010

Discrete mathematics and theoretical computer science

Vol. 12, num. 1, p. 75-86

Date of publication: 2010

Abstract:

A geometric graph is a graph G = (V;E) drawn in the plane, such that V is a point set in general position and E is a set of straight-line segments whose endpoints belong to V . We study the following extremal problem for geometric graphs: How many arbitrary edges can be removed from a complete geometric graph with n vertices such that the remaining graph still contains a certain non-crossing subgraph. The non-crossing subgraphs that we consider are perfect matchings, subtrees of a given size, and triangulations. In each case, we obtain tight bounds on the maximum number of removable edges.]]>

Computational geometry: theory and applications

Vol. 42, num. 9, p. 913-922

DOI: 10.1016/j.comgeo.2009.03.005,

Date of publication: 2009-11

Computational geometry: theory and applications

Vol. 42, num. 6-7, p. 617-626

DOI: 10.1016/j.comgeo.2008.12.005

Date of publication: 2009-08

Geombinatorics

Vol. XIX, num. 1, p. 5-6

Date of publication: 2009-07

Encuentros de Geometría Computacional

p. 91-97

Presentation's date: 2009-06-29

Abstract:

Let G be a directed graph and k a positive integer. We define the k-color graph of G (Dk(G) for short) as the directed graph having all k-colorings of G as node set, and where two k-colorings and ' are joined by a directed edge ! ' if ' is obtained from by choosing a vertex v and recoloring v so that its color is different from the colors of all its out-neighbors. We investigate reachability questions in Dk(G). In particular we want to know whether a fixed legal k′-coloring of G with k′ k is reachable in Dk(G) from every possible initial k-coloring . Interesting instances of this problem arise when G is planar and the orientation is an arbitrary -orientation for fixed . Our main result is that reachability can be guaranteed if the orientation has maximal out-degree k − 1 and an accessible pseudo-sink.]]>

Discrete applied mathematics

Vol. 157, num. 7, p. 1509-1520

DOI: 10.1016/j.dam.2008.06.018

Date of publication: 2009-04

Discrete mathematics and theoretical computer science

Vol. 11, num. 2, p. 47-56

Date of publication: 2009-01

European Workshop on Computational Geometry

p. 133-136

Presentation's date: 2009

Abstract:

We consider a variation of a problem stated by Erd˝os and Szekeres in 1935 about the existence of a number fES(k) such that any set S of at least fES(k) points in general position in the plane has a subset of k points that are the vertices of a convex k-gon. In our setting the points of S are colored, and we say that a (not necessarily convex) spanned polygon is monochromatic if all its vertices have the same color. Moreover, a polygon is called empty if it does not contain any points of S in its interior. We show that any bichromatic set of n ≥ 5044 points in R2 in general position determines at least one empty, monochromatic quadrilateral (and thus linearly many).]]>

Encuentros de Geometría Computacional

p. 221-228

Presentation's date: 2009

Abstract:

Let S be a two-colored set of n points in general position in the plane. We show that S admits at least 2 n 17 pairwise disjoint monochromatic triangles with vertices in S and empty of points of S. We further show that S can be partitioned into 3 n 11 subsets with pairwise disjoint convex hull such that within each subset all but at most one point have the same color. A lower bound on the number of subsets needed in any such partition is also given.]]>

Information processing letters

Vol. 109, num. 2, p. 124-129

Date of publication: 2008-12

Date of publication: 2008-11

Lecture notes in computer science

Vol. 4529, p. 307-317

DOI: 10.1007/978-3-540-72950-1_31

Date of publication: 2007-06

12th International Fuzzy Systems Association World Congress

p. 307-310

VIII Jornadas ARCA, Sistemas Cualitativos y Diagnosis

p. 86-91

Journal of combinatorial mathematics and combinatorial computing

Vol. 57, p. 97-102

Date of publication: 2006-01

European journal of combinatorics

Vol. 20, num. 5, p. 337-349

Date of publication: 1999-07

Date: 1996-10

Discrete mathematics

Vol. 138, num. 1-3, p. 147-160

Date of publication: 1995-03

Date of publication: 1995-01