Search

The Lonely Runner Conjecture originated in Diophantine approximation will turn 60 in 2028. Even if the conjecture is still widely open, the flow of partial results, innovative tools and connections to different problems and applications has been steady on its long life. This survey attempts to give a panoramic view of the status of the problem, trying to highlight the contributions of the many papers that it has originated., Comment: 38 pages

An edge-colored multigraph $G$ is rainbow connected if every pair of vertices is joined by at least one rainbow path, i.e., a path where no two edges are of the same color. In the context of multilayered networks we introduce the notion of multilayered random geometric graphs, from $h\ge 2$ independent random geometric graphs $G(n,r)$ on the unit square. We define an edge-coloring by coloring the edges according to the copy of $G(n,r)$ they belong to and study the rainbow connectivity of the resulting edge-colored multigraph. We show that $r(n)=\left(\frac{\log n}{n}\right)^{\frac{h-1}{2h}}$ is a threshold of the radius for the property of being rainbow connected. This complements the known analogous results for the multilayerd graphs defined on the Erd\H{o}s-R\' enyi random model.

A perfect code in a graph is an independent set of the graph such that every vertex outside the set is adjacent to exactly one vertex in the set. A circulant graph is a Cayley graph of a cyclic group. In this paper we study perfect codes in circulant graphs of degree $p^l - 1$, where $p$ is a prime and $l \ge 1$. We obtain a necessary and sufficient condition for such a circulant graph to admit perfect codes, give a construction of all such circulant graphs which admit perfect codes, and prove a lower bound on the number of distinct perfect codes in such a circulant graph. This extends known results for the case $l=1$ and provides insight on the general problem on the existence and structure of perfect codes in circulant graphs.

In \cite[Serra, Vena, Extremal families for the Kruskal-Katona theorem]{sv21}, the authors have shown a characterization of the extremal families for the Kruskal-Katona Theorem. We further develop some of the arguments given in \cite{sv21} and give additional properties of these extremal families. F\"uredi-Griggs/M\"ors theorem from 1986/85 \cite{furgri86,mors85} claims that, for some cardinalities, the initial segment of the colexicographical is the unique extremal family; we extend their result as follows: the number of (non-isomorphic) extremal families strictly grows with the gap between the last two coefficients of the $k$-binomial decomposition. We also show that every family is an induced subfamily of an extremal family, and that, somewhat going in the opposite direction, every extremal family is close to being the inital segment of the colex order; namely, if the family is extremal, then after performing $t$ lower shadows, with $t=O(\log(\log n))$, we obtain the initial segment of the colexicographical order. We also give a ``fast'' algorithm to determine whether, for a given $t$ and $m$, there exists an extremal family of size $m$ for which its $t$-th lower shadow is not yet the initial segment in the colexicographical order. As a byproduct of these arguments, we give yet another characterization of the families of $k$-sets satisfying equality in the Kruskal--Katona theorem. Such characterization is, at first glance, less appealing than the one in \cite{sv21}, since the additional information that it provides is indirect. However, the arguments used to prove such characterization provide additional insight on the structure of the extremal families themselves., Comment: 44 pages, 3 figures, 1 table

Given a family $S$ of $k$--subsets of $[n]$, its lower shadow $\Delta(S)$ is the family of $(k-1)$--subsets which are contained in at least one set in $S$. The celebrated Kruskal--Katona theorem gives the minimum cardinality of $\Delta(S)$ in terms of the cardinality of $S$. F\"uredi and Griggs (and M\"ors) showed that the extremal families for this shadow minimization problem in the Boolean lattice are unique for some cardinalities and asked for a general characterization of these extremal families. In this paper we prove a new combinatorial inequality from which yet another simple proof of the Kruskal--Katona theorem can be derived. The inequality can be used to obtain a characterization of the extremal families for this minimization problem, giving an answer to the question of F\"uredi and Griggs. Some known and new additional properties of extremal families can also be easily derived from the inequality.

We show that if $A$ is a subset of a group of prime order $p$ such that $|2A|<2.7652|A|$ and $|A|<1.25\cdot10^{-6}p$, then $A$ is contained in an arithmetic progression with at most $|2A|-|A|+1$ terms, and $2A$ contains an arithmetic progression with the same difference and at least $2|A|-1$ terms. This improves a number of previously known results.

We prove that product-free sets of the free group over a finite alphabet have maximum density $1/2$ with respect to the natural measure that assigns total weight one to each set of irreducible words of a given size. This confirms a conjecture of Leader, Letzter, Narayanan and Walters. In more general terms, we actually prove that strongly $k$-product-free sets have maximum density $1/k$ in terms of the said measure., Comment: 10 pages. Uploaded accepted version including some changes suggested by anonymous referees

Vertex bisection is a graph partitioning problem in which the aim is to find a partition into two equal parts that minimizes the number of vertices in one partition set that have a neighbor in the other set. We are interested in giving upper bounds on the vertex bisection width of random $d$-regular graphs for constant values of $d$. Our approach is based on analyzing a greedy algorithm by using the Differential Equations Method. In this way, we obtain the first known upper bounds for the vertex bisection width in random regular graphs. The results are compared with experimental ones and with lower bounds obtained by Kolesnik and Wormald, (Lower Bounds for the Isoperimetric Numbers of Random Regular Graphs, SIAM J. on Disc. Math. 28(1), 553-575, 2014)., Comment: 31 pages, 2 figures

The theory of rapid mixing random walks plays a fundamental role in the study of modern randomised algorithms. Usually, the mixing time is measured with respect to the worst initial position. It is well known that the presence of bottlenecks in a graph hampers mixing and, in particular, starting inside a small bottleneck significantly slows down the diffusion of the walk in the first steps of the process. The average mixing time is defined to be the mixing time starting at a uniformly random vertex and hence is not sensitive to the slow diffusion caused by these bottlenecks. In this paper we provide a general framework to show logarithmic average mixing time for random walks on graphs with small bottlenecks. The framework is especially effective on certain families of random graphs with heterogeneous properties. We demonstrate its applicability on two random models for which the mixing time was known to be of order $(\log n)^2$, speeding up the mixing to order $\log n$. First, in the context of smoothed analysis on connected graphs, we show logarithmic average mixing time for randomly perturbed graphs of bounded degeneracy. A particular instance is the Newman-Watts small-world model. Second, we show logarithmic average mixing time for supercritically percolated expander graphs. When the host graph is complete, this application gives an alternative proof that the average mixing time of the giant component in the supercritical Erd\H{o}s-R\'enyi graph is logarithmic., Comment: To appear in Electronic Journal of Probability

A partial order is universal if it contains every countable partial order as a suborder. In 2017, Fiala, Hubi\v{c}ka, Long and Ne\v{s}et\v{r}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., Comment: 6 pages, 1 figure. Extended abstract for Eurocomb 2021; corrected title

Let $A_1$ and $A_2$ be randomly chosen subsets of the first $n$ integers of cardinalities $s_2\geq s_1 = \Omega(s_2)$, such that their sumset $A_1+A_2$ has size $m$. We show that asymptotically almost surely $A_1$ and $A_2$ are almost fully contained in arithmetic progressions $P_1$ and $P_2$ with the same common difference and cardinalities approximately $s_i m/(s_1+s_2)$. We also prove a counting theorem for such pairs of sets in arbitrary abelian groups. The results hold for $s_i = \omega(\log^3 n)$ and $s_1+s_2 \leq m = o(s_2/\log^3 n)$. Our main tool is an asymmetric version of the method of hypergraph containers which was recently used by Campos to prove similar results in the special case $A=B$., Comment: a) Replaced Theorem 2.2 with a less general statement (proof of previously claimed result contained an error), no influence on the main results of this article. b) Incorporated numerous suggestions by anonymous referees to improve presentation, thank you!

We introduce the Multicolored Graph Realization problem (MGRP). The input to the problem is a colored graph $(G,\varphi)$, i.e., a graph together with a coloring on its vertices. We can associate to each colored graph a cluster graph ($G_\varphi)$ in which, after collapsing to a node all vertices with the same color, we remove multiple edges and self-loops. A set of vertices $S$ is multicolored when $S$ has exactly one vertex from each color class. The problem is to decide whether there is a multicolored set $S$ such that, after identifying each vertex in $S$ with its color class, $G[S]$ coincides with $G_\varphi$. The MGR problem is related to the class of generalized network problems, most of which are NP-hard. For example the generalized MST problem. MGRP is a generalization of the Multicolored Clique Problem, which is known to be W[1]-hard when parameterized by the number of colors. Thus MGRP remains W[1]-hard, when parameterized by the size of the cluster graph and when parameterized by any graph parameter on $G_\varphi$, among those for treewidth. We look to instances of the problem in which both the number of color classes and the treewidth of $G_\varphi$ are unbounded. We show that MGRP is NP-complete when $G_\varphi$ is either chordal, biconvex bipartite, complete bipartite or a 2-dimensional grid. Our hardness results follows from suitable reductions from the 1-in-3 monotone SAT problem. Our reductions show that the problem remains hard even when the maximum number of vertices in a color class is 3. In the case of the grid, the hardness holds also graphs with bounded degree. We complement those results by showing combined parameterizations under which the MGR problem became tractable., Comment: 23 pages, 9 figures

Let $\Gamma$ be an Abelian group and let $G$ be a simple graph. We say that $G$ is $\Gamma$-colorable if for some fixed orientation of $G$ and every edge labeling $\ell:E(G)\rightarrow \Gamma$, there exists a vertex coloring $c$ by the elements of $\Gamma$ such that $c(y)-c(x)\neq \ell(e)$, for every edge $e=xy$ (oriented from $x$ to $y$). Langhede and Thomassen proved recently that every planar graph on $n$ vertices has at least $2^{n/9}$ different $\mathbb{Z}_5$-colorings. By using a different approach based on graph polynomials, we extend this result to $K_5$-minor-free graphs in the more general setting of field coloring. More specifically, we prove that every such graph on $n$ vertices is $\mathbb{F}$-$5$-choosable, whenever $\mathbb{F}$ is an arbitrary field with at least $5$ elements. Moreover, the number of colorings (for every list assignment) is at least $5^{n/4}$., Comment: 14 pages

An $L(h_1, h_2, \ldots, h_l)$-labelling of a graph $G$ is a mapping $\phi: 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 $|\phi(u) - \phi(v)| \geq h_i$. The span of $\phi$ is the difference between the largest and smallest labels assigned to the vertices of $G$ by $\phi$, and $\lambda_{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 $\lambda_{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 $\lambda_{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., Comment: Final version published in Discrete Applied Mathematics

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.

Let the random variable $X\, :=\, e(\mathcal{H}[B])$ count the number of edges of a hypergraph $\mathcal{H}$ induced by a random $m$ element subset $B$ of its vertex set. Focussing on the case that $\mathcal{H}$ satisfies some regularity condition we prove bounds on the probability that $X$ is far from its mean. It is possible to apply these results to discrete structures such as the set of $k$-term arithmetic progressions in the cyclic group $\mathbb{Z}_N$. Furthermore, we show that our main theorem is essentially best possible and we deduce results for the case $B\sim B_p$ is generated by including each vertex independently with probability $p$.

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., Comment: 30 pages

The connection between inequalities in additive combinatorics and analogous versions in terms of the entropy of random variables has been extensively explored over the past few years. This paper extends a device introduced by Ruzsa in his seminal work introducing this correspondence. This extension provides a toolbox for establishing the equivalence between sumset inequalities and their entropic versions. It supplies simpler proofs of known results and opens a path for obtaining new ones., Comment: The former version had an error the authors could not fix. This version keeps only that parts that did not depend on the incorrect statement

A conjecture of Freiman gives an exact formula for the largest volume of a finite set $A$ of integers with given cardinality $k = |A|$ and doubling $T = |2A|$. The formula is known to hold when $T \le 3k-4$, for some small range over $3k-4$ and for families of structured sets called chains. In this paper we extend the formula to sets of every dimension and prove it for sets composed of three segments, giving structural results for the extremal case. A weaker extension to sets composed of a bounded number of segments is also discussed., Comment: 16 pages

Freiman's 2.4-Theorem states that any set $A \subset \mathbb{Z}_p$ satisfying $|2A| \leq 2.4|A| - 3 $ and $|A| < p/35$ can be covered by an arithmetic progression of length at most $|2A| - |A| + 1$. A more general result of Green and Ruzsa implies that this covering property holds for any set satisfying $|2A| \leq 3|A| - 4$ as long as the rather strong density requirement $|A| < p/10^{215}$ is satisfied. We present a version of this statement that allows for sets satisfying $|2A| \leq 2.48|A| - 7$ with the more modest density requirement of $|A| < p/10^{10}$., Comment: 13 pages, 1 figure

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)=\Omega_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$., Comment: Incorporated referee comments. Published in Rev. Mat. Iberoam

The Johnson graph $J(n,m)$ has the $m$--subsets of $\{1,2,\ldots,n\}$ as vertices and two subsets are adjacent in the graph if they share $m-1$ elements. Shapozenko asked about the isoperimetric function $\mu_{n,m}(k)$ of Johnson graphs, that is, the cardinality of the smallest boundary of sets with $k$ vertices in $J(n,m)$ for each $1\le k\le {n\choose m}$. We give an upper bound for $\mu_{n,m}(k)$ and show that, for each given $k$ such that the solution to the Shadow Minimization Problem in the Boolean lattice is unique, and each sufficiently large $n$, the given upper bound is tight. We also show that the bound is tight for the small values of $k\le m+1$ and for all values of $k$ when $m=2$., Comment: 15 pages, 1 figure. Improved version with the comments from the referees

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., Comment: 31 pages

A Theorem of Hou, Leung and Xiang generalised Kneser's addition Theorem to field extensions. This theorem was known to be valid only in separable extensions, and it was a conjecture of Hou that it should be valid for all extensions. We give an alternative proof of the theorem that also holds in the non-separable case, thus solving Hou's conjecture. This result is a consequence of a strengthening of Hou et al.'s theorem that is a transposition to extension fields of an addition theorem of Balandraud., Comment: 17 pages

We are interested in characterising pairs $S,T$ of $F$-linear subspaces in a field extension $L/F$ such that the linear span $ST$ of the set of products of elements of $S$ and of elements of $T$ has small dimension. Our central result is a linear analogue of Vosper's Theorem, which gives the structure of vector spaces $S, T$ in a prime extension $L$ of a finite field $F$ for which $\dim_FST =\dim_F S+\dim_F T-1,$ when $\dim_F S, \dim_F T\ge 2$ and $\dim_F ST\le [L:F]-2$., Comment: 33 pages

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., Comment: 18 pages