Search

Richmond and Richmond (American Mathematical Monthly 104 (1997), 713--719) proved the following theorem: If, in a metric space with at least five points, all triangles are degenerate, then the space is isometric to a subset of the real line. We prove that the hypothesis is unnecessarily strong: In a metric space on $n$ points, fewer than $7n^2/6$ suitably placed degenerate triangles suffice. However, fewer than $n(n-1)/2$ degenerate triangles, no matter how cleverly placed, never suffice., Comment: Supersedes arXiv:2209.14361 [math.MG]

When processing data streams with highly skewed and nonstationary key distributions, we often observe overloaded partitions when the hash partitioning fails to balance data correctly. To avoid slow tasks that delay the completion of the whole stage of computation, it is necessary to apply adaptive, on-the-fly partitioning that continuously recomputes an optimal partitioner, given the observed key distribution. While such solutions exist for batch processing of static data sets and stateless stream processing, the task is difficult for long-running stateful streaming jobs where key distribution changes over time. Careful checkpointing and operator state migration is necessary to change the partitioning while the operation is running. Our key result is a lightweight on-the-fly Dynamic Repartitioning (DR) module for distributed data processing systems (DDPS), including Apache Spark and Flink, which improves the performance with negligible overhead. DR can adaptively repartition data during execution using our Key Isolator Partitioner (KIP). In our experiments with real workloads and power-law distributions, we reach a speedup of 1.5-6 for a variety of Spark and Flink jobs., Comment: 14 pages, 8 figures

One way to study the combinatorics of finite metric spaces is to study the betweenness relation associated with the metric space. In the hypergraph metrization problem, one has to find and characterize metric betweennesses whose collinear triples (or alternatively, non-degenerate triangles) coincide with the edges of a given $3$-uniform hypergraph. Metrizability of different kinds of hypergraphs was investigated in the last decades. Chen showed that steiner triple systems are not metrizable, while Richmond and Richmond characterized linear betweennesses, i.e. metric betweennesses that realize the complete $3$-uniform hypergraph. The latter result was also generalized to almost-metric betweennesses by Beaudou et al. In this paper, we further extend this theory by characterizing the largest nonlinear almost-metric betweennesses that satisfy certain hereditary properties, as well as the ones that contain a small linear number of non-degenerate triangles., Comment: 36 pages, 7 figures; technical proofs are relegated to a separate appendix

The betweenness structure of a finite metric space $M = (X, d)$ is a pair $\mathcal{B}(M) = (X,\beta_M)$ where $\beta_M$ is the so-called betweenness relation of $M$ that consists of point triplets $(x, y, z)$ such that $d(x, z) = d(x, y) + d(y, z)$. The underlying graph of a betweenness structure $\mathcal{B} = (X,\beta)$ is the simple graph $G(\mathcal{B}) = (X, E)$ where the edges are pairs of distinct points with no third point between them. A connected graph $G$ is uniquely representable if there exists a unique metric betweenness structure with underlying graph $G$. It was implied by previous works that trees are uniquely representable. In this paper, we give a characterization of uniquely representable graphs by showing that they are exactly the block graphs. Further, we prove that two related classes of graphs coincide with the class of block graphs and the class of distance-hereditary graphs, respectively. We show that our results hold not only for metric but also for almost-metric betweenness structures., Comment: 16 pages (without references); 3 figures; major changes: simplified proofs, improved notations and namings, short overview of metric graph theory

In their paper published in 1997, Richmond and Richmond classified metric spaces in which all triangles are degenerate. That result was later reproved by Dovgoshei and Dordovskii in the finite case and it was generalized to finite pseudometric betweennesses by Beaudou et al. In this paper, we give a new, independent proof to the finite case of the original theorem which we reformulate in terms of linearity of betweenness structures., Comment: 10 pages, 3 figures Keywords: Finite metric space, Metric betweenness, Linearity, Degenerate triangles triangles

In their paper, Bounds on the Number of Edges in Hypertrees, G.Y. Katona and P.G.N. Szab\'o introduced a new, natural definition of hypertrees in $k$-uniform hypergraphs and gave lower and upper bounds on the number of edges. They also defined edge-minimal, edge-maximal and $l$-hypertrees and proved an upper bound on the edge number of $l$-hypertrees. In the present paper, we verify the asymptotic sharpness of the $\binom{n}{k-1}$ upper bound on the number of edges of $k$-uniform hypertrees given in the above mentioned paper. We also make an improvement on the upper bound of the edge number of $2$-hypertrees and give a general extension construction with its consequences. We give lower and upper bounds on the maximal number of edges of $k$-uniform edge-minimal hypertrees and a lower bound on the number of edges of $k$-uniform edge-maximal hypertrees. In the former case, the sharp upper bound is conjectured to be asymptotically $\frac{1}{k-1}\binom{n}{2}$., Comment: 19 pages, accepted by Discussiones Mathematicae Graph Theory in 2015; fixed proof of Theorem 6, added square at the end of proofs

Let $\mathcal{H}$ be a $k$-uniform hypergraph. A chain in $\mathcal{H}$ is a sequence of its vertices such that every $k$ consecutive vertices form an edge. In 1999 Katona and Kierstead suggested to use chains in hypergraphs as the generalisation of paths. Although a number of results have been published on hamiltonian chains in recent years, the generalization of trees with chains has still remained an open area. We generalize the concept of trees for uniform hypergraphs. We say that a $k$-uniform hypergraph $\mathcal{F}$ is a hypertree if every two vertices of $\mathcal{F}$ are connected by a chain, and an appropriate kind of cycle-free property holds. An edge-minimal hypertree is a hypertree whose edge set is minimal with respect to inclusion. After considering these definitions, we show that a $k$-uniform hypertree on $n$ vertices has at least $n-(k-1)$ edges up to a finite number of exceptions, and it has at most $\binom{n}{k-1}$ edges. The latter bound is asymptotically sharp in 3-uniform case.