 |
Discrete Mathematics & Theoretical Computer Science |
vol. 28:3
1. Curves, points, incidences and covering
Given a point set, mostly a grid in our case, we seek upper and lower bounds on the number of curves that are needed to cover the point set. We say a curve covers a point if the curve passes through the point. We consider such coverings by monotonic curves, lines, orthoconvex curves, circles, etc. We also study a problem that is converse of the covering problem -- if a set of $n^2$ points in the plane is covered by $n$ lines then can we say something about the configuration of the points?
Section: Combinatorics
2. On the area-depth symmetry on Łukasiewicz paths
In an effort to further understanding $q,t$-Catalan statistics, a new statistic on Dyck paths called $\mathtt{depth}$ was proposed in Pappe, Paul and Schilling (2022) and was shown to be jointly equi-distributed with the well-known $\mathtt{area}$ statistics. In a recent preprint, Qu and Zhang (2025) generalized $\mathtt{depth}$ to so-called ``$\vec{k}$-Dyck paths''. They showed that $\mathtt{area}$ and $\mathtt{depth}$ are also jointly equi-distributed over such paths with a fixed multiset of up-steps and a given first up-step, and they conjectured that the same holds when also fixing the last up-step. In this short note, we settle this conjecture on the more general context of Łukasiewicz paths by interpreting $\mathtt{area}$ and $\mathtt{depth}$ under the classical bijection between Łukasiewicz paths and plane trees, through which the symmetry is transparent.
Section: Combinatorics
3. Representing Hypergraphs by Point-Line Incidences
We consider hypergraph visualizations that represent vertices as points in the plane and hyperedges as curves passing through the points of their incident vertices. Specifically, we consider several different variants of this problem by (a) restricting the curves to be lines or line segments, (b) allowing two curves to cross if they do not share an element, or not; and (c) allowing two curves to overlap or not. We show $\exists\mathbb{R}$-hardness for six of the eight resulting decision problem variants and describe polynomial-time algorithms in some restricted settings. Lastly, we briefly touch on what happens if we allow the lines of the represented hyperedges to have bends - to this we generalize a counterexample to a long-standing result that was sometimes assumed to be correct.
Section: Combinatorics
4. The height of skew Dyck paths with two variants of downsteps
Recently, in the context of walks of hexagonal circle packings, interest has emerged in the family of skew Dyck paths with two variants of down-steps. These paths have steps $U, D_g, D_b, L=D_r$. Using generating functions, the kernel method and (in)finite linear systems, contributions to the (average) height and other enumerations are made. As in many similar instances, the average height is of order $\sqrt n$.
Section: Combinatorics
5. The $s$-chromatic Ramsey number for stars
In 1977, Chung, Chung and Liu generalized the definition of the Ramsey number. They introduced the $s$-chromatic Ramsey number as follows. Let $1\leq s< t$ be integers and let $A_{1}, A_{2}, \dots, A_{c}$ be subsets with size $s$ of $[t]$, where $c= {t\choose s}$. For given graphs $G_{1}, G_{2}, \dots, G_{c}$, the {\it $s$-chromatic Ramsey number} $r^{s, t}(G_{1}, G_{2}, \dots, G_{c})$, is the minimum positive integer $N$ such that every $t$-coloring of $E(K_{N})$ yields a copy of $G_{i}$ whose edges are colored by colors in the color set $A_{i}$ for some $i\in [c]$. The {\it star-critical $s$-chromatic Ramsey number} $r_{*}^{s, t}(G_{1}, G_{2}, \dots, G_{c})$, is the minimum integer $\ell$ such that every $t$-coloring of the edges in $K_{N}- E(K_{1, N- 1- \ell})$ yields a copy of $G_{i}$ whose edges are colored by colors in the color set $A_{i}$ for some $i\in [c]$, where $N= r^{s, t}(G_{1}, G_{2}, \dots, G_{c})$. If $G_{1}= G_{2}= \dots= G_{c}= G$, then we simplify them to $r^{s, t}(G)$ (also called the {\it weakened Ramsey number}) and $r^{s, t}_{*}(G)$, respectively. In this paper, we determine all the values of $r^{s, t}(K_{1, m})$ and $r_{*}^{s, t}(K_{1, m})$, and part of the value of $r^{s, t}(K_{1, m_{1}}, K_{1, m_{2}}, \dots, K_{1, m_{c}})$.
Section: Graph Theory
6. Coloring Grids Avoiding Bicolored Paths
The star chromatic number on a graph is the minimum number of colors in a proper vertex coloring forbidding any $P_4$ with two colors (bicolored). This problem was introduced by Grünbaum (1973) together with the acyclic coloring of graphs, where bicolored cycles are avoided. In this paper, we study a generalization of this problem, by considering proper vertex coloring on graphs forbidding bicolored paths of a fixed length, which was initially discussed by Alon, McDiarmid, and Reed (1991). Here, we study this problem on products of two paths. We show that at least 4 colors are needed to properly color the product of paths, $P_m\square P_n$, avoiding a bicolored $P_k,$ unless $n<k-2$ or $m<k-2.$ With this result, the above question is settled for all $k$ on 2-dimensional grids.
Section: Graph Theory
7. Strong Embeddings of 3-Connected Cubic Planar Graphs on Surfaces of non-negative Euler Characteristic
Whitney proved that 3-connected planar graphs admit a unique embedding on the sphere. In contrast, Enami investigated embeddings of 3-connected cubic planar graphs on non-spherical surfaces with non-negative Euler characteristic. He established that such an embedding exists if and only if the dual graph contains a particular subgraph. Here, strong embeddings are investigated motivated by the cycle double cover conjecture and the relation to triangulated surfaces. We provide a complete characterization of strong embeddings on the projective plane, the torus, and the Klein bottle in terms of a distinguished subset of Enami's subgraphs. This characterization not only deepens the structural understanding of graph embeddings on non-spherical surfaces, but also establishes a robust foundation for computing cycle double covers. As a direct consequence, we derive explicit criteria that determine when a graph does not admit a strong embedding on these surfaces-offering new tools for both theoretical analysis and algorithmic applications.
Section: Graph Theory