Source author record

Oriol Serra

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

ResearcherUnclaimed source record

math.CO Discrete Mathematics math.NT Computational Complexity math.GR math.MG

Catalog footprint

Research overview

18works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Distance-constrained labellings of Cartesian products of graphs

An $L(h_1, h_2, \ldots, h_l)$ -labelling of a graph $G$ is a mapping $ϕ: V(G) \rightarrow \{0, 1, 2, \ldots\}$ such that for $1\le i\le l$ and each pair of vertices $u, v$ of $G$ at distance $i$ , we have $|ϕ(u) - ϕ(v)| \geq h_i$ . The span of $ϕ$ is the difference between the largest and smallest labels assigned to the vertices of $G$ by $ϕ$ , and $λ_{h_1, h_2, \ldots, h_l}(G)$ is defined as the minimum span over all $L(h_1, h_2, \ldots, h_l)$ -labellings of $G$ . In this paper we study $λ_{h, 1, \ldots, 1}$ for Cartesian products of graphs, where $(h, 1, \ldots, 1)$ is an $l$ -tuple with $l \ge 3$ . We prove that, under certain natural conditions, the value of this and three related invariants on a graph $H$ which is the Cartesian product of $l$ graphs attain a common lower bound. In particular, the chromatic number of the $l$ -th power of $H$ equals this lower bound plus one. We further obtain a sandwhich theorem which extends the result to a family of subgraphs of $H$ which contain a certain subgraph of $H$ . All these results apply in particular to the class of Hamming graphs: if $q_1\ge \cdots \ge q_d\ge 2$ and $3\le l\le d$ then the Hamming graph $H=H_{q_1,q_2,\ldots ,q_d}$ satisfies $λ_{q_l,1,\ldots,1}(H) = q_1q_2\ldots q_l-1$ whenever $q_1q_2\ldots q_{l-1}>3(q_{l-1}+1)q_l\ldots q_d$ . In particular, this settles a case of the open problem on the chromatic number of powers of the hypercubes.

preprint2022arXiv

On the Homomorphism Order of Oriented Paths and Trees

A partial order is universal if it contains every countable partial order as a suborder. In 2017, Fiala, Hubička, Long and Nešetřil showed that every interval in the homomorphism order of graphs is universal, with the only exception being the trivial gap $[K_1,K_2]$ . We consider the homomorphism order restricted to the class of oriented paths and trees. We show that every interval between two oriented paths or oriented trees of height at least 4 is universal. The exceptional intervals coincide for oriented paths and trees and are contained in the class of oriented paths of height at most 3, which forms a chain.

preprint2020arXiv

On List k-Coloring Convex Bipartite Graphs

List k-Coloring (Li k-Col) is the decision problem asking if a given graph admits a proper coloring compatible with a given list assignment to its vertices with colors in {1,2,..,k}. The problem is known to be NP-hard even for k=3 within the class of 3-regular planar bipartite graphs and for k=4 within the class of chordal bipartite graphs. In 2015, Huang, Johnson and Paulusma asked for the complexity of Li 3-Col in the class of chordal bipartite graphs. In this paper we give a partial answer to this question by showing that Li k-Col is polynomial in the class of convex bipartite graphs. We show first that biconvex bipartite graphs admit a multichain ordering, extending the classes of graphs where a polynomial algorithm of Enright, Stewart and Tardos (2014) can be applied to the problem. We provide a dynamic programming algorithm to solve the Li k-Col in the calss of convex bipartite graphs. Finally we show how our algorithm can be modified to solve the more general Li H-Col problem on convex bipartite graphs.

preprint2020arXiv

Sidon set systems

A family ${\mathcal A}$ of $k$ -subsets of $\{1,2,\dots, N\}$ is a Sidon system if the sumsets $A+B$ , $A,B\in \mathcal{A}$ are pairwise distinct. We show that the largest cardinality $F_k(N)$ of a Sidon system of $k$ -subsets of $[N]$ satisfies $F_k(N)\le {N-1\choose k-1}+N-k$ and the asymptotic lower bound $F_k(N)=Ω_k(N^{k-1})$ . More precise bounds on $F_k(N)$ are obtained for $k\le 3$ . We also obtain the threshold probability for a random system to be Sidon for $k\ge 2$ .

preprint2018arXiv

Triangulations and a discrete Brunn-Minkowski inequality in the plane

For a set $A$ of points in the plane, not all collinear, we denote by ${\rm tr}(A)$ the number of triangles in any triangulation of $A$ ; that is, ${\rm tr}(A) = 2i+b-2$ where $b$ and $i$ are the numbers of points of $A$ in the boundary and the interior of $[A]$ (we use $[A]$ to denote "convex hull of $A$ "). We conjecture the following analogue of the Brunn-Minkowski inequality: for any two point sets $A,B \subset {\mathbb R}^2$ one has ${\rm tr}(A+B)^{\frac12}\geq {\rm tr}(A)^{\frac12}+{\rm tr}(B)^{\frac12}.$ We prove this conjecture in several cases: if $[A]=[B]$ , if $B=A\cup\{b\}$ , if $|B|=3$ , or if none of $A$ or $B$ has interior points.

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

Correlation among runners and some results on the Lonely Runner Conjecture

The Lonely Runner Conjecture was posed independently by Wills and Cusick and has many applications in different mathematical fields, such as diophantine approximation. This well-known conjecture states that for any set of runners running along the unit circle with constant different speeds and starting at the same point, there is a moment where all of them are far enough from the origin. We study the correlation among the time that runners spend close to the origin. By means of these correlations, we improve a result of Chen on the gap of loneliness and we extend an invisible runner result of Czerwinski and Grytczuk. In the last part, we introduce dynamic interval graphs to deal with a weak version of the conjecture thus providing some new results.

preprint2013arXiv

On sumsets and convex hull

One classical result of Freimann gives the optimal lower bound for the cardinality of A+A if A is a d-dimensional finite set in the Euclidean d-space. Matolcsi and Ruzsa have recently generalized this lower bound to |A+kB| if B is d-dimensional, and A is contained in the convex hull of B. We characterize the equality case of the Matolcsi-Ruzsa bound. The argument is based partially on understanding triangulations of polytopes.

preprint2013arXiv

Random subgraphs make identification affordable

An identifying code of a graph is a dominating set which uniquely determines all the vertices by their neighborhood within the code. Whereas graphs with large minimum degree have small domination number, this is not the case for the identifying code number (the size of a smallest identifying code), which indeed is not even a monotone parameter with respect to graph inclusion. We show that every graph $G$ with $n$ vertices, maximum degree $Δ=ω(1)$ and minimum degree $δ\geq c\logΔ$ , for some constant $c>0$ , contains a large spanning subgraph which admits an identifying code with size $O\left(\frac{n\logΔ}δ\right)$ . In particular, if $δ=Θ(n)$ , then $G$ has a dense spanning subgraph with identifying code $O\left(\log n\right)$ , namely, of asymptotically optimal size. The subgraph we build is created using a probabilistic approach, and we use an interplay of various random methods to analyze it. Moreover we show that the result is essentially best possible, both in terms of the number of deleted edges and the size of the identifying code.

preprint2012arXiv

A Structure Theorem for Small Sumsets in Nonabelian Groups

Let G be an arbitrary finite group and let S and T be two subsets such that |S|>1, |T|>1, and |TS|< |T|+|S|< |G|-1. We show that if |S|< |G|-4|G|^{1/2}+1 then either S is a geometric progression or there exists a non-trivial subgroup H such that either |HS|< |S|+|H| or |SH| < |S|+|H|. This extends to the nonabelian case classical results for Abelian groups. When we remove the hypothesis |S|<|G|-4|G|^{1/2}+1 we show the existence of counterexamples to the above characterization whose structure is described precisely.

preprint2012arXiv

On the number of monochromatic solutions of integer linear systems on Abelian groups

Let $G$ be a finite abelian group with exponent $n$ , and let $r$ be a positive integer. Let $A$ be a $k\times m$ matrix with integer entries. We show that if $A$ satisfies some natural conditions and $|G|$ is large enough then, for each $r$ --coloring of $G\setminus \{0\}$ , there is $δ$ depending only on $r,n$ and $m$ such that the homogeneous linear system $Ax=0$ has at least $δ|G|^{m-k}$ monochromatic solutions. Density versions of this counting result are also addressed.

preprint2012arXiv

On the Removal Lemma for Linear Systems over Abelian Groups

In this paper we present an extension of the removal lemma to integer linear systems over abelian groups. We prove that, if the $k$ --determinantal of an integer $(k\times m)$ matrix $A$ is coprime with the order $n$ of a group $G$ and the number of solutions of the system $Ax=b$ with $x_1\in X_1,..., x_m\in X_m$ is $o(n^{m-k})$ , then we can eliminate $o(n)$ elements in each set to remove all these solutions. This is a follow-up of our former paper 'A Removal Lemma for Systems of Linear Equations over Finite Fields' arXiv:0809.1846v1, which dealt with the case of finite fields.

preprint2012arXiv

On the tree-depth of Random Graphs

The tree-depth is a parameter introduced under several names as a measure of sparsity of a graph. We compute asymptotic values of the tree-depth of random graphs. For dense graphs, p>> 1/n, the tree-depth of a random graph G is a.a.s. td(G)=n-O(sqrt(n/p)). Random graphs with p=c/n, have a.a.s. linear tree-depth when c>1, the tree-depth is Theta (log n) when c=1 and Theta (loglog n) for c<1. The result for c>1 is derived from the computation of tree-width and provides a more direct proof of a conjecture by Gao on the linearity of tree-width recently proved by Lee, Lee and Oum. We also show that, for c=1, every width parameter is a.a.s. constant, and that random regular graphs have linear tree-depth.

preprint2012arXiv

Remarks on the equality case of the Bonnesen inequality

An argument is provided for the equality case of the high dimensional Bonnesen inequality for sections. The known equality case of the Bonnesen inequality for projections is presented as a consequence.

preprint2011arXiv

Counting patterns in colored orthogonal arrays

Let $S$ be an orthogonal array $OA(d,k)$ and let $c$ be an $r$ --coloring of its ground set $X$ . We give a combinatorial identity which relates the number of vectors in $S$ with given color patterns under $c$ with the cardinalities of the color classes. Several applications of the identity are considered. Among them, we show that every equitable $r$ --coloring of the integer interval $[1,n]$ has at least $1/2(n/r)^2+O(n)$ monochromatic Schur triples. We also show that in an orthogonal array $OA(d,d-1)$ , the number of monochromatic vectors of each color depends only on the number of vectors which miss that color and the cardinality of the color class.

preprint2011arXiv

Rainbow Matchings: existence and counting

A perfect matching M in an edge-colored complete bipartite graph K_{n,n} is rainbow if no pair of edges in M have the same color. We obtain asymptotic enumeration results for the number of rainbow matchings in terms of the maximum number of occurrences of a color. We also consider two natural models of random edge-colored K_{n,n} and show that, if the number of colors is at least n, then there is with high probability a random matching. This in particular shows that almost every square matrix of order n in which every entry appears at most n times has a Latin transversal.

preprint2011arXiv

Rainbow-free 3-colorings of Abelian Groups

A 3-coloring of the elements of an abelian group is said to be rainbow--free if there is no 3-term arithmetic progression with its members having pairwise distinct colors. We give a structural characterization of rainbow--free colorings of abelian groups. This characterization proves a conjecture of Jungić et al. on the size of the smallest chromatic class of a rainbow-free 3-coloring of cyclic groups.

preprint2010arXiv

On the cardinality of sumsets in torsion-free groups

Let $A, B$ be finite subsets of a torsion-free group $G$ . We prove that for every positive integer $k$ there is a $c(k)$ such that if $|B|\ge c(k)$ then the inequality $|AB|\ge |A|+|B|+k$ holds unless a left translate of $A$ is contained in a cyclic subgroup. We obtain $c(k)<c_0k^{6}$ for arbitrary torsion-free groups, and $c(k)<c_0k^{3}$ for groups with the unique product property, where $c_0$ is an absolute constant. We give examples to show that $c(k)$ is at least quadratic in $k$ .

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.

Oriol Serra

Research overview

Is this your work?

18 publications

Distance-constrained labellings of Cartesian products of graphs

On the Homomorphism Order of Oriented Paths and Trees

On List k-Coloring Convex Bipartite Graphs

Sidon set systems

Triangulations and a discrete Brunn-Minkowski inequality in the plane

Counting configuration-free sets in groups

Correlation among runners and some results on the Lonely Runner Conjecture

On sumsets and convex hull

Random subgraphs make identification affordable

A Structure Theorem for Small Sumsets in Nonabelian Groups

On the number of monochromatic solutions of integer linear systems on Abelian groups

On the Removal Lemma for Linear Systems over Abelian Groups

On the tree-depth of Random Graphs

Remarks on the equality case of the Bonnesen inequality

Counting patterns in colored orthogonal arrays

Rainbow Matchings: existence and counting

Rainbow-free 3-colorings of Abelian Groups

On the cardinality of sumsets in torsion-free groups

See the researcher in context

Building this map preview