Proceedings of the London Mathematical Society

DOI: 10.1112/plms.12234

Date of publication: 2019-01-01

Abstract:

We present the first combinatorial scheme for counting labelled 4-regular planar graphs through a complete recursive decomposition. More precisely, we show that the exponential generating function of labelled 4-regular planar graphs can be computed effectively as the solution of a system of equations, from which the coefficients can be extracted. As a byproduct, we also enumerate labelled 3-connected 4-regular planar graphs, and simple 4-regular rooted maps.]]>

Journal of combinatorial theory. Series A

Vol. 160, p. 261-287

DOI: 10.1016/j.jcta.2018.06.015

Date of publication: 2018-11-01

Abstract:

Let p denote the characteristic of , the finite field with q elements. We prove that if q is odd then an arc of size in the projective plane over , which is not contained in a conic, is contained in the intersection of two curves, which do not share a common component, and have degree at most , provided a certain technical condition on t is satisfied. This implies that if q is odd then an arc of size at least is contained in a conic if q is square and an arc of size at least is contained in a conic if q is prime. This is of particular interest in the case that q is an odd square, since then there are examples of arcs, not contained in a conic, of size , and it has long been conjectured that if is an odd square then any larger arc is contained in a conic. These bounds improve on previously known bounds when q is an odd square and for primes less than 1783. The previously known bounds, obtained by Segre [26], Hirschfeld and Korchmáros [17][18], and Voloch [32][33], rely on results on the number of points on algebraic curves over finite fields, in particular the Hasse–Weil theorem and the Stöhr–Voloch theorem, and are based on Segre's idea to associate an algebraic curve in the dual plane containing the tangents to an arc. In this paper we do not rely on such theorems, but use a new approach starting from a scaled coordinate-free version of Segre's lemma of tangents. Arcs in the projective plane over of size q and , q odd, were classified by Segre [25] in 1955. In this article, we complete the classification of arcs of size and . The main theorem also verifies the MDS conjecture for a wider range of dimensions in the case that q is an odd square. The MDS conjecture states that if , a k-dimensional linear MDS code has length at most . Here, we verify the conjecture for , in the case that q is an odd square.]]>

Journal of combinatorial theory. Series B

Vol. 133, p. 211-242

DOI: 10.1016/j.jctb.2018.04.009

Date of publication: 2018-09-26

Abstract:

We prove a tight upper bound on the independence polynomial (and total number of independent sets) of cubic graphs of girth at least 5. The bound is achieved by unions of the Heawood graph, the point/line incidence graph of the Fano plane. We also give a tight lower bound on the total number of independent sets of triangle-free cubic graphs. This bound is achieved by unions of the Petersen graph. We conjecture that in fact all Moore graphs are extremal for the scaled number of independent sets in regular graphs of a given minimum girth, maximizing this quantity if their girth is even and minimizing if odd. The Heawood and Petersen graphs are instances of this conjecture, along with complete graphs, complete bipartite graphs, and cycles.]]>

Journal of combinatorial theory. Series B

Vol. 136, p. 44-71

DOI: 10.1016/j.jctb.2018.09.004

Date of publication: 2018-09-17

Abstract:

A class of graphs is bridge-addable if given a graph G in the class, any graph obtained by adding an edge between two connected components of G is also in the class. We prove a conjecture of McDiarmid, Steger, and Welsh, that says that if is any bridge-addable class of graphs on n vertices, and is taken uniformly at random from , then is connected with probability at least , when n tends to infinity. This lower bound is asymptotically best possible since it is reached for forests. Our proof uses a “local double counting” strategy that may be of independent interest, and that enables us to compare the size of two sets of combinatorial objects by solving a related multivariate optimization problem. In our case, the optimization problem deals with partition functions of trees relative to a supermultiplicative functional.]]>

Electronic notes in discrete mathematics

Vol. 68, num. July 2018, p. 119

DOI: 10.1016/j.endm.2018.06.021

Date of publication: 2018-07-01

Abstract:

We study the class L of link-types that admit a K4-minor-free diagram, i.e., they can be projected on the plane so that the resulting graph does not contain any subdivision of K4. We prove that L is the closure of a subclass of torus links under the operation of connected sum. Using this structural result, we enumerate L and subclasses of it, with respect to the minimum number of crossings or edges in a projection of L' in L. Further, we obtain counting formulas and asymptotic estimates for the connected K4-minor-free link-diagrams, minimal K4-minor-free link-diagrams, and K4-minor-free diagrams of the unknot.]]>

Electronic notes in discrete mathematics

Vol. 68, num. July 2018, p. 101-106

DOI: 10.1016/j.endm.2018.06.018

Date of publication: 2018-07-01

Abstract:

We prove that for pairwise co-prime numbers k1,...,kd = 2 there does not exist any infinite set of positive integers A such that the representation function rA(n) = #{(a1,...,ad) ¿ Ad : k1a1 + ... + kdad = n} becomes constant for n large enough. This result is a particular case of our main theorem, which poses a further step towards answering a question of S´ark¨ozy and S´os and widely extends a previous result of Cilleruelo and Ru´e for bivariate linear forms (Bull. of the London Math. Society 2009).]]>

Electronic notes in discrete mathematics

Vol. 68, p. 11-16

DOI: 10.1016/j.endm.2018.06.003

Date of publication: 2018-07-01

Abstract:

Segre’s lemma of tangents dates back to the 1950’s when he used it in the proof of his “arc is a conic” theorem. Since then it has been used as a tool to prove results about various objects including internal nuclei, Kakeya sets, sets with few odd secants and further results on arcs. Here, we survey some of these results and report on how re-formulations of Segre’s lemma of tangents are leading to new results.]]>

Discrete Mathematics Days

p. 119-124

DOI: 10.1016/j.endm.2018.06.021

Presentation's date: 2018-06-28

Abstract:

We study the class of link types that admit a K4-minor-free diagram, i.e., they can be projected on the plane so that the resulting graph does not contain any subdivision of K4. We prove that is the closure of a subclass of torus links under the operation of connected sum. Using this structural result, we enumerate and subclasses of it, with respect to the minimal number of crossings or edges in a projection of . Further, we enumerate (both exactly and asymptotically) all connected K4-minor-free link diagrams, all minimal connected K4-minor-free link diagrams, and all K4-minor-free diagrams of the unknot.]]>

International Conference on the Analysis of Algorithms

DOI: 10.4230/LIPIcs.AofA.2018.18

Presentation's date: 2018-06-26

Abstract:

We provide combinatorial decompositions as well as asymptotic tight estimates for two maximal parameters: the number and average size of maximal independent sets and maximal matchings in series-parallel graphs (and related graph classes) with n vertices. In particular, our results extend previous results of Meir and Moon for trees [Meir, Moon: On maximal independent sets of nodes in trees, Journal of Graph Theory 1988]. We also show that these two parameters converge to a central limit law. © Svante Janson; licensed under Creative Commons License CC-BY.

We provide combinatorial decompositions as well as asymptotic tight estimates for two maximal parameters: the number and average size of maximal independent sets and maximal matchings in seriesparallel graphs (and related graph classes) with n vertices. In particular, our results extend previous results of Meir and Moon for trees [Meir, Moon: On maximal independent sets of nodes in trees, Journal of Graph Theory 1988]. We also show that these two parameters converge to a central limit law.]]>

Jahresbericht der Deutschen Mathematiker-Vereinigung

Vol. 120, num. 2, p. 147-150

DOI: 10.1365/s13291-017-0170-9

Date of publication: 2018-05-07

Integers: electronic journal of combinatorial number theory

Vol. 18, num. A28

Date of publication: 2018-03-23

Abstract:

This is a list of problems in combinatorial number theory gathered on the occasion of the meeting The Music of Numbers to honor the memory of the late Javier Cilleruelo (1961-2016).]]>

Proceedings of the American Mathematical Society

Vol. 146, num. 8, p. 3321-3332

DOI: 10.1090/proc/14021

Date of publication: 2018-03-20

Abstract:

We show that for all $ d\in \{3,\ldots ,n-1\}$ the size of the largest component of a random $ d$-regular graph on $ n$ vertices around the percolation threshold $ p=1/(d-1)$ is $ \Theta (n^{2/3})$, with high probability. This extends known results for fixed $ d\geq 3$ and for $ d=n-1$, confirming a prediction of Nachmias and Peres on a question of Benjamini. As a corollary, for the largest component of the percolated random $ d$-regular graph, we also determine the diameter and the mixing time of the lazy random walk. In contrast to previous approaches, our proof is based on a simple application of the switching method

First published in Proc. Amer. Math. Soc. 146 (2018), 3321-3332, published by the American Mathematical Society]]>

European Journal of Mathematics

Vol. 4, num. 1, p. 8-25

DOI: 10.1007/s40879-017-0193-x

Date of publication: 2018-03-01

Abstract:

An arc is a set of vectors of the k-dimensional vector space over the finite field with q elements Fq , in which every subset of size k is a basis of the space, i.e. every k-subset is a set of linearly independent vectors. Given an arc G in a space of odd characteristic, we prove that there is an upper bound on the largest arc containing G. The bound is not an explicit bound but is obtained by computing properties of a matrix constructed from G. In some cases we can also determine the largest arc containing G, or at least determine the hyperplanes which contain exactly k-2 vectors of the large arc. The theorems contained in this article may provide new tools in the computational classification and construction of large arcs.

This is a post-peer-review, pre-copyedit version of an article published in European Journal of Mathematics. The final authenticated version is available online at: https://doi.org/10.1007/s40879-017-0193-x]]>

Mathematische Zeitschrift

Vol. 288, num. 1-2, p. 333-360

DOI: 10.1007/s00209-017-1891-2

Date of publication: 2018-02

Abstract:

We study threshold functions for the existence of solutions to linear systems of equations in random sets and present a unified framework which includes arithmetic progressions, sum-free sets, Bh[g]Bh[g]-sets and Hilbert cubes. In particular, we show that there exists a threshold function for the property “AAcontains a non-trivial solution of M·x=0M·x=0” where AA is a random set and each of its elements is chosen independently with the same probability from the interval of integers {1,…,n}{1,…,n}. Our study contains a formal definition of trivial solutions for any linear system, extending a previous definition by Ruzsa when dealing with a single equation. Furthermore, we study the distribution of the number of non-trivial solutions at the threshold scale. We show that it converges to a Poisson distribution whose parameter depends on the volumes of certain convex polytopes arising from the linear system under study as well as the symmetry inherent in the structures, which we formally define and characterize. Juanjo Rué was partially supported by the FP7-PEOPLE-2013-CIG Project CountGraph (ref. 630749), the Spanish MICINN Projects MTM2014-54745-P and MTM2014-56350-P, the DFG within the Research Training Group Methods for Discrete Structures (ref. GRK1408), and the Berlin Mathematical School. Christoph Spiegel was supported by a Berlin Mathematical School Scholarship. Ana Zumalacárregui is supported by the Australian Research Council Grant DP140100118. The first and third authors started this project while financed by the MTM2011-22851 Grant (Spain) and the ICMAT Severo Ochoa Project SEV-2011-0087 (Spain).]]>

Abstract:

The project deals with the study of central problems in combinatorics and discrete mathematics. It covers specially three research axes: geometric combinatorics, algebraic combinatorics and probabilistic combinatorics. More precisely, the main objectives are the following: - Freiman conjecture on doubling and volume, its consequences in additive combinatorics and its interplay with the so-called polynomial Freiman-Ruzsa conjecture. - Generalization of graph invariants (chromatic polynomial and symmetric chromatic polynomial), as well as their interactions with matroid theory. - New enumerative and probabilistic results for graph families with topological obstructions, covering bipartite graph classes and regular graphs, among others. - Study of problems in incidence geometry, more particularly in relation to the MDS conjecture and to the Silvester problem for dimension higher than 4. - Study of new logic laws for random discrete structures, including rooted graphs, perfect graphs and permutations. - Analysis of the distance chromatic number of cartesian products of graphs and extensions of the sandwich theorem for non-monotone parameters. The study of these problems involves the development of new geometric, algebraic and probabilistic techniques, as well as the interaction of these areas and the use of new ones, including analytic, topological an number theoretical tools. Building a solid ground for this set of techniques is one of the side objectives of the proposal.]]>

Date of publication: 2018-01-01

Random structures and algorithms

DOI: 10.1002/rsa.20829

Date of publication: 2018-01-01

Abstract:

Biased Maker-Breaker games, introduced by Chvátal and Erdos, are central to the field of positional games and have deep connections to the theory of random structures. The main questions are to determine the smallest bias needed by Breaker to ensure that Maker ends up with an independent set in a given hypergraph. Here we prove matching general winning criteria for Maker and Breaker when the game hypergraph satisfies certain “container-type” regularity conditions. This will enable us to answer the main question for hypergraph generalizations of the H-building games studied by Bednarska and Luczak as well as a generalization of the van der Waerden games introduced by Beck. We find it remarkable that a purely game-theoretic deterministic approach provides the right order of magnitude for such a wide variety of hypergraphs, while the analogous questions about sparse random discrete structures are usually quite challenging.]]>

Random structures and algorithms

Vol. 51, num. 4, p. 631-673

DOI: 10.1002/rsa.20721

Date of publication: 2017-12

Abstract:

Let H be a fixed graph and math formula a subcritical graph class. In this paper we show that the number of occurrences of H (as a subgraph) in a graph in math formula of order n, chosen uniformly at random, follows a normal limiting distribution with linear expectation and variance. The main ingredient in our proof is the analytic framework developed by Drmota, Gittenberger and Morgenbesser to deal with infinite systems of functional equations [Drmota, Gittenberger, and Morgenbesser, Submitted]. As a case study, we obtain explicit expressions for the number of triangles and cycles of length 4 in the family of series-parallel graphs.]]>

Newsletter of the European Mathematical Society

num. 106, p. 17-20

Date of publication: 2017-12

Date of publication: 2017-12-01

Discrete and computational geometry

Vol. 60, num. 1, p. 1-34

DOI: 10.1007/s00454-017-9935-2

Date of publication: 2017-09-19

Abstract:

Let S be a set of n points in real three-dimensional space, no three collinear and not all co-planar. We prove that if the number of planes incident with exactly three points of S is less than (Formula presented.) for some (Formula presented.) then, for n sufficiently large, all but at most O(K) points of S are contained in the intersection of two quadrics. Furthermore, we prove that there is a constant c such that if the number of planes incident with exactly three points of S is less than (Formula presented.) then, for n sufficiently large, S is either a regular prism, a regular anti-prism, a regular prism with a point removed or a regular anti-prism with a point removed. As a corollary to the main result, we deduce the following theorem. Let S be a set of n points in the real plane. If the number of circles incident with exactly three points of S is less than (Formula presented.) for some (Formula presented.) then, for n sufficiently large, all but at most O(K) points of S are contained in a curve of degree at most four.]]>

Date of publication: 2017-09-01

Electronic notes in discrete mathematics

Vol. 61, p. 933-939

DOI: 10.1016/j.endm.2017.07.056

Date of publication: 2017-08-01

Abstract:

In this extended abstract, we present the first combinatorial scheme for counting labeled 4-regular planar graphs through a complete recursive decomposition. More precisely, we show that the exponential generating function counting labeled 4-regular planar graphs can be computed effectively as the solution of a system of equations. From here we can extract the coefficients by means of algebraic calculus. As a by-product, we can also compute the algebraic generating function counting labeled 3-connected 4-regular planar maps.

©

Electronic notes in discrete mathematics

Vol. 61, p. 1-7

DOI: 10.1016/j.endm.2017.07.037

Date of publication: 2017-08-01

Abstract:

In a (1 : q) Maker-Breaker game, one of the central questions is to find (or at least estimate) the maximal value of q that allows Maker to win the game. Based on the ideas of Bednarska and Luczak [Bednarska, M., and T. Luczak, Biased positional games for which random strategies are nearly optimal, Combinatorica, 20 (2000), 477–488], who studied biased H-games, we prove general winning criteria for Maker and Breaker and a hypergraph generalization of their result. Furthermore, we study the biased version of a strong generalization of the van der Waerden games introduced by Beck [Beck, J., Van der Waerden and Ramsey type games, Combinatorica, 1 (1981), 103–116] and apply our criteria to determine the threshold bias of these games up to constant factor. As in the result of [Bednarska, M., and T. Luczak, Biased positional games for which random strategies are nearly optimal, Combinatorica, 20 (2000), 477–488], the random strategy for Maker is again the best known strategy.]]>

Electronic notes in discrete mathematics

Vol. 61, p. 1-7

DOI: 10.1016/j.endm.2017.06.039

Date of publication: 2017-08-01

Abstract:

We study the existence of rainbow perfect matching and rainbow Hamiltonian cycles in edge–colored graphs where every color appears a bounded number of times. We derive asymptotically tight bounds on the minimum degree of the host graph for the existence of such rainbow spanning structures. The proof uses a probabilisitic argument combined with switching techniques.]]>

European journal of combinatorics

p. 1-3

DOI: 10.1016/j.ejc.2017.07.001

Date of publication: 2017-07-22

Abstract:

In the paper ”On the limiting distribution of the metric dimension for random forests” the metric dimension ß(G) of sparse G(n, p) with p = c/n and c < 1 was studied (Theorem 1.2). In the proof of this theorem, for the convergence in distribution Stein’s Method was applied incorrectly]]>

Journal of geometry

Vol. 108, num. 2, p. 529-543

DOI: 10.1007/s00022-016-0357-8

Date of publication: 2017-07-01

Abstract:

In this article we consider $S$ to be a set of points in $d$-space with the property that any $d$ points of $S$ span a hyperplane and not all the points of $S$ are contained in a hyperplane. The aim of this article is to introduce the function $e_d(n)$, which denotes the minimal number of hyperplanes meeting $S$ in precisely $d$ points, minimising over all such sets of points $S$ with $|S|=n$.]]>

SIAM journal on discrete mathematics

Vol. 31, num. 2, p. 1328-1354

DOI: 10.1137/120874448

Date of publication: 2017-06-22

Abstract:

We give asymptotically exact values for the treewidth tw(G) of a random geometric graph G ¿ G(n, r) in [0, v n] 2 . More precisely, let rc denote the threshold radius for the appearance of the giant component in G(n, r). We then show that for any constant 0 < r < rc, tw(G) = T( log n log log n ), and for c being sufficiently large, and r = r(n) = c, tw(G) = T(r v n). Our proofs show that for the corresponding values of r the same asymptotic bounds also hold for the pathwidth and the treedepth of a random geometric graph.]]>

IEEE transactions on information theory

Vol. 63, num. 6, p. 3658-3662

DOI: 10.1109/TIT.2017.2671344

Date of publication: 2017-06-01

Abstract:

A normal rational curve of the (k-1) -dimensional projective space over Fq is an arc of size q+1 , since any k points of the curve span the whole space. In this paper, we will prove that if q is odd, then a subset of size 3k-6 of a normal rational curve cannot be extended to an arc of size q+2 . In fact, we prove something slightly stronger. Suppose that q is odd and E is a (2k-3) -subset of an arc G of size 3k-6 . If G projects to a subset of a conic from every (k-3) -subset of E , then G cannot be extended to an arc of size q+2 . Stated in terms of error-correcting codes we prove that a k -dimensional linear maximum distance separable code of length 3k-6 over a field Fq of odd characteristic, which can be extended to a Reed–Solomon code of length q+1 , cannot be extended to a linear maximum distance separable code of length q+2 .]]>

Workshop on Analytic Algorithmics and Combinatorics

p. 46-55

Presentation's date: 2017-02-01

Abstract:

Consider the Erdos-Renyi random graph G(n, M) built with n vertices and M edges uniformly randomly chosen from the set of n2 edges. Let L be a set of positive integers. For any number of edges M 6n/2 + O(n 2/3 ), we compute – via analytic combinatorics – the number of isolated cycles of G(n, M) whose length is in L.

Consider the Erdos-Renyi random graph G(n, M) built with n vertices and M edges uniformly randomly chosen from the set of n2 edges. Let L be a set of positive integers. For any number of edges M 6n/2 + O(n 2/3 ), we compute – via analytic combinatorics – the number of isolated cycles of G(n, M) whose length is in L.]]>

Probability theory and related fields

Vol. 170, num. 1-2, p. 263-310

DOI: 10.1007/s00440-017-0757-1

Date of publication: 2017-01-26

Abstract:

For a fixed degree sequence D=(d1,…,dn) , let G(D) be a uniformly chosen (simple) graph on {1,…,n} where the vertex i has degree di . In this paper we determine whether G(D) has a giant component with high probability, essentially imposing no conditions on D . We simply insist that the sum of the degrees in D which are not 2 is at least ¿(n) for some function ¿ going to infinity with n. This is a relatively minor technical condition, and when D does not satisfy it, both the probability that G(D) has a giant component and the probability that G(D) has no giant component are bounded away from 1]]>

European journal of combinatorics

Vol. 66, p. 281-307

DOI: 10.1016/j.ejc.2017.06.027

Date of publication: 2017-01-01

Abstract:

© 2017 Elsevier Ltd. We provide asymptotic counting for the number of subsets of given size which are free of certain configurations in finite groups. Applications include sets without solutions to equations in non-abelian groups, and linear configurations in abelian groups defined from group homomorphisms. The results are obtained by combining the methodology of hypergraph containers joint with arithmetic removal lemmas. Random sparse versions and threshold probabilities for existence of configurations in sets of given density are presented as well.]]>

Random structures and algorithms

Vol. 50, num. 4, p. 511-533

DOI: 10.1002/rsa.20695

Date of publication: 2016-11-03

Abstract:

An edge colouring of a graph G is called acyclic if it is proper and every cycle contains at least three colours. We show that for every e > 0, there exists a g = g(e) such that if G has maximum degree ¿ and girth at least g then G admits an acyclic edge colouring with (1 + e)¿+O(1) colours.

This is the peer reviewed version of the following article: Cai, X. S., Perarnau, G. , Reed, B. and Watts, A. B. (2017), Acyclic edge colourings of graphs with large girth. Random Struct. Alg., 50: 511-533. doi:10.1002/rsa.20695, which has been published in final form at https://doi.org/10.1002/rsa.20695. This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for Use of Self-Archived Versions]]>

Electronic notes in discrete mathematics

Vol. 54, p. 211-216

DOI: 10.1016/j.endm.2016.09.037

Date of publication: 2016-10-18

Abstract:

The goal of our work is to analyze random cubic planar graphs according to the uniform distribution. More precisely, let G be the class of labelled cubic planar graphs and let gn be the number of graphs with n vertices]]>

Advances in applied probability

Vol. 48, num. 3, p. 848-864

DOI: 10.1017/apr.2016.31

Date of publication: 2016-09-01

Abstract:

Given any two vertices u, v of a random geometric graph G(n, r), denote by dE(u, v) their Euclidean distance and by dE(u, v) their graph distance. The problem of finding upper bounds on dG(u, v) conditional on dE(u, v) that hold asymptotically almost surely has received quite a bit of attention in the literature. In this paper we improve the known upper bounds for values of r=¿(vlogn) (that is, for r above the connectivity threshold). Our result also improves the best known estimates on the diameter of random geometric graphs. We also provide a lower bound on dE(u, v) conditional on dE(u, v).]]>

The australasian journal of combinatorics

Vol. 65, num. 3, p. 251-260

Date of publication: 2016-06-02

Abstract:

Let $L$ be a set of lines of an affine space over a field and let $S$ be a set of points with the property that every line of $L$ is incident with at least $N$ points of $S$. Let $D$ be the set of directions of the lines of $L$ considered as points of the projective space at infinity. We give a geometric construction of a set of lines $L$, where $D$ contains an $N^{n-1}$ grid and where $S$ has size $2(\frac{1}{2}N)^n$ plus smaller order terms, given a starting configuration in the plane. We provide examples of such starting configurations for the reals and for finite fields. Following Dvir's proof of the finite field Kakeya conjecture and the idea of using multiplicities of Dvir, Kopparty, Saraf and Sudan, we prove a lower bound on the size of $S$ dependent on the ideal generated by the homogeneous polynomials vanishing on $D$. This bound is maximised as $(\frac{1}{2}N)^n$ plus smaller order terms, for $n\geqslant 4$, when $D$ contains the points of a $N^{n-1}$ grid.

Let L be a set of lines of an affine space over a field and let S be a set of points with the property that every line of L is incident with at least N points of S. Let D be the set of directions of the lines of L considered as points of the projective space at infinity. We give a geometric construction of a set of lines L, where D contains an Nn−1 grid and where S has size 2( 1 2N) n plus smaller order terms, given a starting configuration in the plane. We provide examples of such starting configurations for the reals and for finite fields. Following Dvir’s proof of the finite field Kakeya conjecture and the idea of using multiplicities of Dvir, Kopparty, Saraf and Sudan, we prove a lower bound on the size of S dependent on the ideal generated by the homogeneous polynomials vanishing on D. This bound is maximised as ( 1 2N) n plus smaller order terms, for n > 4, when D contains the points of a Nn−1 grid.]]>

Discrete mathematics

Vol. 339, num. 4, p. 1206-1211

DOI: 10.1016/j.disc.2015.11.010

Date of publication: 2016-04-06

Abstract:

We show that the norm graph with n vertices about View the MathML source edges, which contains no copy of the complete bipartite graph Kt,(t-1)!+1, does not contain a copy of Kt+1,(t-1)!-1.]]>

Advances in applied mathematics

Vol. 75, p. 18-55

DOI: 10.1016/j.aam.2015.12.001

Date of publication: 2016-04-01

Abstract:

By means of analytic techniques we show that the expected number of spanning trees in a connected labelled series-parallel graph on n vertices chosen uniformly at random satisfies an estimate of the form s%-n(1 + o(1)), where s and % are computable constants, the values of which are approximately s ˜ 0.09063 and %-1 ˜ 2.08415. We obtain analogue results for subfamilies of series-parallel graphs including 2-connected series-parallel graphs, 2-trees, and series-parallel graphs with fixed excess.]]>

Journal of mathematical chemistry

Vol. 54, num. 3, p. 765-776

DOI: 10.1007/s10910-015-0584-5

Date of publication: 2016-03-01

Abstract:

Carbon is the most versatile of chemical elements in combining with itself or other elements to form chains, rings, sheets, cages, and periodic 3D structures. One of the perspective trends for creating new molecules of nanotechnological interest deals with constructs which may be formed by chemically linking of cage molecules. The growing interest in fullerene polyhedra and other molecules with pentagonal rings raises also a question about geometrically consistent in E3E3 nanoarchitectures which may be obtained by aggregating many such molecules. Simple examples are chains and rings assembled from pyramidal (car)borane subunits. Adequate geometrical models of such objects are a chain and an annulus built from regular pentagons wherein any two adjacent pentagons share an edge. Among arising combinatorial problems may be both analytical and constructive enumeration of such chains and annuli drawn in plane with no two edges crossing each other. This may also employ several mathematical disciplines, such as geometry, (spectral) graph theory, semigroup theory, theory of fractals, and others. We discuss some practical approaches for solving the mentioned mathematical problem.

The final publication is available at Springer via http://dx.doi.org/10.1007/s10910-015-0584-5]]>

Abstract:

The unifying focus of this project is computational geometry, with emphasis on both combinatorial and algorithmic problems on the relationship between combinatorial graphs and their geometric embeddings. This disciplinary framework is inserted into a wider one, namely discrete and algorithmic mathematics. Its major development in recent times is due to its association with computer and communication technologies. This is why it still requires an intense and sustained research effort. With this project we want to channel the general research activity of the group, with its multiplicity of cooperative working lines, while at the same time intensifying work on a specific topic: the interaction between combinatorial and geometric graphs. Simultaneously, we intend to consolidate the direction initiated in the previous project (MTM2012-30951/FEDER) intensifying the identification and study of problems arising from application areas. Although one cannot ignore the fact that our research is of theoretical kind, we cannot ignore either that many of the problems that computational geometry studies arise from its many applications. We have structured our proposal in three lines of work of a fundamental nature: A1. Domination in combinatorial graphs, A2. Domination and coverings in geometric graphs, A3. Geometric embedding of combinatorial graphs, plus another two, more oriented towards applications: B1. Modular robotic system reconfiguration, B2. Geometric algorithms for geographic information, Regarding the foundations of theoretical type, the research lines we propose seek to delve into the study of combinatorial properties of graphs (A1) whose transposition to geometric graphs (A2) is of great interest for the research community in combinatorial and algorithmic geometry: domination, location, covering... This relationship between properties of combinatorial graphs and those of geometric graphs is also evident in the crucial fact that is reflected in A3: on the one hand, the study of combinatorial properties of graphs is eased by the study of their embeddings in the plane and, conversely, the study of sets of points -in the plane and in higher dimension- is eased by studying the graphs they determine. As for the applications, the three subjects that this project aims to emphasize are linked to the previous subjects because the algorithms of B1 rely on properties of regular graphs and minimum spanning trees, and some of the problems of B2 are directly related to visibility problems on terrains. Main objective: scientific achievements. The natural objective of this project is to obtain as complete and advanced results as possible in the study of the algorithmic-geometric problems described above. Additional objectives: in parallel with the main objective, we have two other complementary goals which are also natural in a project of this nature: maintaining the international projection of the group, and maintaining our efforts into training young researchers.]]>

Snapshots for modern mathematics from Oberwolfach

num. 16, p. 1-11

DOI: 10.14760/SNAP-2015-016-EN

Date of publication: 2015-12-01

Abstract:

Imagine you have a cutout from a piece of squared paper and a pile of dominoes, each of which can cover exactly two squares of the squared paper. How many different ways are there to cover the entire paper cutout with dominoes? One specific paper cutout can be mathematically described as the so-called Aztec Diamond, and a way to cover it with dominoes is a domino tiling. In this snapshot we revisit some of the seminal combinatorial ideas used to enumerate the number of domino tilings of the Aztec Diamond. The existing connection with the study of the so-called alternating-sign matrices is also explored.]]>

Discrete and computational geometry

Vol. 54, num. 3, p. 954-979

DOI: 10.1007/s00454-015-9735-5

Date of publication: 2015-10-26

Abstract:

The family of 2-level matroids, that is, matroids whose base polytope is 2-level, has been recently studied and characterized by means of combinatorial properties. 2-Level matroids generalize series-parallel graphs, which have been already successfully analyzed from the enumerative perspective. We bring to light some structural properties of 2-level matroids and exploit them for enumerative purposes. Moreover, the counting results are used to show that the number of combinatorially non-equivalent (n-1)(n-1)-dimensional 2-level polytopes is bounded from below by c·n-5/2·¿-nc·n-5/2·¿-n, where c˜0.03791727c˜0.03791727 and ¿-1˜4.88052854¿-1˜4.88052854.

The final publication is available at Springer via DOI 10.1007/s00454-015-9735-5]]>

European journal of combinatorics

Vol. 52, num. A, p. 1-11

DOI: 10.1016/j.ejc.2015.08.001

Date of publication: 2015-09-07

Abstract:

In this paper, we show that for every graph of maximum average degree bounded away from d and any two (d + 1)-colorings of it, one can transform one coloring into the other one within a polynomial number of vertex recolorings so that, at each step, the current coloring is proper. In particular, it implies that we can transform any 8-coloring of a planar graph into any other 8-coloring with a polynomial number of recolorings. These results give some evidence on a conjecture of Cereceda et al [8] which asserts that any (d + 2) coloring of a d-degenerate graph can be transformed into any other one using a polynomial number of recolorings. We also show that any (2d + 2)-coloring of a d-degenerate graph can be transformed into any other one with a linear number of recolorings.

This is a post-peer-review, pre-copyedit version of an article published in European Journal of Combinatorics. The final authenticated version is available online at: https://doi.org/10.1016/j.ejc.2015.08.001]]>

European Conference on Combinatorics, Graph Theory and Applications

p. 383-391

DOI: 10.1016/j.endm.2015.06.054

Presentation's date: 2015-08-31

Abstract:

In this extended abstract we determine a normal limiting distribution for the number of triangles in a uniformly at random 3-connected cubic planar graph, as well as the precise expectation and variance values. Further comments towards the more complicated problem of studying both the limiting distribution of triangles in random cubic planar graphs, and the (asymptotic) number of triangle-free cubic planar graphs are discussed as well.]]>

International journal of algebra and computation

Vol. 25, num. 5, p. 799-811

DOI: 10.1142/S0218196715500198

Date of publication: 2015-08-01

Abstract:

We compute estimates for the word metric of Baumslag-Solitar groups in terms of the Britton's lemma normal form. As a corollary, we find lower bounds for the growth rate for the groups BS(p, q) with 1 < p <= q.]]>

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.]]>

European journal of combinatorics

Vol. 49, p. 68-89

Date of publication: 2015-03-20

Abstract:

The metric dimension of a graph G is the minimum size of a subset S of vertices of G such that all other vertices are uniquely determined by their distances to the vertices in S. In this paper we investigate the metric dimension for two different models of random forests, in each case obtaining normal limit distributions for this parameter.]]>

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.]]>