Source author record

Juanjo Rué

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.NT Data Structures and Algorithms Discrete Mathematics

Catalog footprint

Research overview

13works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Structure and enumeration of K4-minor-free links and link-diagrams

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.

preprint2016arXiv

Counting configuration-free sets in groups

We provide new examples of the asymptotic counting for the number of subsets on groups of given size which are free of certain configurations. These examples 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. As a consequence, random counterparts are presented as well.

preprint2015arXiv

Many 2-level polytopes from matroids

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)-dimensional 2-level polytopes is bounded from below by $c \cdot n^{-5/2} \cdot ρ^{-n}$ , where $c\approx 0.03791727$ and $ρ^{-1} \approx 4.88052854$ .

preprint2015arXiv

Spanning trees in random series-parallel graphs

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 \varrho^{-n} (1+o(1))$ , where $s$ and $\varrho$ are computable constants, the values of which are approximately $s \approx 0.09063$ and $\varrho^{-1} \approx 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.

preprint2014arXiv

On the limiting distribution of the metric dimension for random forests

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.

preprint2013arXiv

On polynomial representation functions for multilinear forms

Given an infinite sequence of positive integers $\cA$, we prove that for every nonnegative integer $k$ the number of solutions of the equation $n=a_1+...+a_k$ , $a_1,\,..., a_k\in \cA$, is not constant for $n$ large enough. This result is a corollary of our main theorem, which partially answers a question of Sárközy and Sós on representation functions for multilinear forms. Additionally, we obtain an Erdős-Fuchs type result for a wide variety of representation functions.

preprint2013arXiv

The least common multiple of random sets of positive integers

We study the typical behavior of the least common multiple of the elements of a random subset $A\subset \{1,\dots, n\}$ . For example we prove that $\text{lcm}\{a:\ a\in A\}=2^{n(1+o(1))}$ for almost all subsets $A\subset\{1,\dots,n\}$ .

preprint2012arXiv

On the probability of planarity of a random graph near the critical point

Consider the uniform random graph $G(n,M)$ with $n$ vertices and $M$ edges. Erdős and Rényi (1960) conjectured that the limit $$ \lim_{n \to \infty} \Pr\{G(n,\textstyle{n\over 2}) is planar}} $$ exists and is a constant strictly between 0 and 1. Łuczak, Pittel and Wierman (1994) proved this conjecture and Janson, Łuczak, Knuth and Pittel (1993) gave lower and upper bounds for this probability. In this paper we determine the exact probability of a random graph being planar near the critical point $M=n/2$ . For each $λ$ , we find an exact analytic expression for $p(λ) = \lim_{n \to \infty} \Pr{G(n,\textstyle{n\over 2}(1+λn^{-1/3})) is planar}.$ In particular, we obtain $p(0) \approx 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,\textstyle{n\over 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.

preprint2011arXiv

Asymptotic Enumeration of Non-crossing Partitions on Surfaces

We generalize the notion of non-crossing partition on a disk to general surfaces with boundary. For this, we consider a surface $Σ$ and introduce the number $C_Σ(n)$ of non-crossing partitions of a set of $n$ points laying on the boundary of $Σ$ . Our proofs use bijective techniques arising from map enumeration, joint with the symbolic method and singularity analysis on generating functions. An outcome of our results is that the exponential growth of $C_Σ(n)$ is the same as the one of the $n$ -th Catalan number, i.e., does not change when we move from the case where $Σ$ is a disk to general surfaces with boundary.

preprint2011arXiv

Dynamic Programming for Graphs on Surfaces

We provide a framework for the design and analysis of dynamic programming algorithms for surface-embedded graphs on n vertices and branchwidth at most k. Our technique applies to general families of problems where standard dynamic programming runs in 2^{O(k log k)} n steps. Our approach combines tools from topological graph theory and analytic combinatorics. In particular, we introduce a new type of branch decomposition called "surface cut decomposition", generalizing sphere cut decompositions of planar graphs introduced by Seymour and Thomas, which has nice combinatorial properties. Namely, the number of partial solutions that can be arranged on a surface cut decomposition can be upper-bounded by the number of non-crossing partitions on surfaces with boundary. It follows that partial solutions can be represented by a single-exponential (in the branchwidth k) number of configurations. This proves that, when applied on surface cut decompositions, dynamic programming runs in 2^{O(k)} n steps. That way, we considerably extend the class of problems that can be solved in running times with a single-exponential dependence on branchwidth and unify/improve most previous results in this direction.

preprint2011arXiv

On the error term of the logarithm of the lcm of a quadratic sequence

We study the logarithm of the least common multiple of the sequence of integers given by $1^2+1, 2^2+1,..., n^2+1$ . Using a result of Homma on the distribution of roots of quadratic polynomials modulo primes we calculate the error term for the asymptotics obtained by Cilleruelo.

preprint2010arXiv

On dilates sums

Let $A$ be a finite nonempty set of integers. An asymptotic estimate of several dilates sum size was obtained by Bukh. The unique known exact bound concerns the sum $|A+k\cdot A|,$ where $k$ is a prime and $|A|$ is large. In its full generality, this bound is due to Cilleruelo, Serra and the first author. Let $k$ be an odd prime and assume that $|A|>8k^{k}.$ A corollary to our main result states that $|2\cdot A+k\cdot A|\ge (k+2)|A|-k^2-k+2.$ Notice that $|2\cdot P+k\cdot P|=(k+2)|P|-2k,$ if $P$ is an arithmetic progression.

preprint2009arXiv

Enumerating simplicial decompositions of surfaces with boundaries

It is well-known that the triangulations of the disc with $n+2$ vertices on its boundary are counted by the $n$ th Catalan number $C(n)=\frac{1}{n+1}{2n \choose n}$ . This paper deals with the generalisation of this problem to any arbitrary compact surface $S$ with boundaries. We obtain the asymptotic number of simplicial decompositions of the surface $S$ with $n$ vertices on its boundary. More generally, we determine the asymptotic number of dissections of $S$ when the faces are $δ$ -gons with $δ$ belonging to a set of admissible degrees $Δ\subseteq \{3,4,5,...\}$ . We also give the limit laws of certain parameters of such dissections.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Juanjo Rué

Research overview

Is this your work?

13 publications

Structure and enumeration of K4-minor-free links and link-diagrams

Counting configuration-free sets in groups

Many 2-level polytopes from matroids

Spanning trees in random series-parallel graphs

On the limiting distribution of the metric dimension for random forests

On polynomial representation functions for multilinear forms

The least common multiple of random sets of positive integers

On the probability of planarity of a random graph near the critical point

Asymptotic Enumeration of Non-crossing Partitions on Surfaces

Dynamic Programming for Graphs on Surfaces

On the error term of the logarithm of the lcm of a quadratic sequence

On dilates sums

Enumerating simplicial decompositions of surfaces with boundaries

See the researcher in context

Building this map preview