arXiv daily

Combinatorics (math.CO)

Thu, 20 Apr 2023

Other arXiv digests in this category:Thu, 14 Sep 2023; Wed, 13 Sep 2023; Tue, 12 Sep 2023; Mon, 11 Sep 2023; Fri, 08 Sep 2023; Tue, 05 Sep 2023; Fri, 01 Sep 2023; Thu, 31 Aug 2023; Wed, 30 Aug 2023; Tue, 29 Aug 2023; Mon, 28 Aug 2023; Fri, 25 Aug 2023; Thu, 24 Aug 2023; Wed, 23 Aug 2023; Tue, 22 Aug 2023; Mon, 21 Aug 2023; Fri, 18 Aug 2023; Thu, 17 Aug 2023; Wed, 16 Aug 2023; Tue, 15 Aug 2023; Mon, 14 Aug 2023; Fri, 11 Aug 2023; Thu, 10 Aug 2023; Wed, 09 Aug 2023; Tue, 08 Aug 2023; Mon, 07 Aug 2023; Fri, 04 Aug 2023; Thu, 03 Aug 2023; Wed, 02 Aug 2023; Tue, 01 Aug 2023; Mon, 31 Jul 2023; Fri, 28 Jul 2023; Thu, 27 Jul 2023; Wed, 26 Jul 2023; Tue, 25 Jul 2023; Mon, 24 Jul 2023; Fri, 21 Jul 2023; Thu, 20 Jul 2023; Wed, 19 Jul 2023; Tue, 18 Jul 2023; Mon, 17 Jul 2023; Fri, 14 Jul 2023; Thu, 13 Jul 2023; Wed, 12 Jul 2023; Tue, 11 Jul 2023; Mon, 10 Jul 2023; Fri, 07 Jul 2023; Thu, 06 Jul 2023; Wed, 05 Jul 2023; Tue, 04 Jul 2023; Mon, 03 Jul 2023; Fri, 30 Jun 2023; Thu, 29 Jun 2023; Wed, 28 Jun 2023; Tue, 27 Jun 2023; Mon, 26 Jun 2023; Fri, 23 Jun 2023; Thu, 22 Jun 2023; Wed, 21 Jun 2023; Tue, 20 Jun 2023; Fri, 16 Jun 2023; Thu, 15 Jun 2023; Tue, 13 Jun 2023; Mon, 12 Jun 2023; Fri, 09 Jun 2023; Thu, 08 Jun 2023; Wed, 07 Jun 2023; Tue, 06 Jun 2023; Mon, 05 Jun 2023; Fri, 02 Jun 2023; Thu, 01 Jun 2023; Wed, 31 May 2023; Tue, 30 May 2023; Mon, 29 May 2023; Fri, 26 May 2023; Thu, 25 May 2023; Wed, 24 May 2023; Tue, 23 May 2023; Mon, 22 May 2023; Fri, 19 May 2023; Thu, 18 May 2023; Wed, 17 May 2023; Tue, 16 May 2023; Mon, 15 May 2023; Fri, 12 May 2023; Thu, 11 May 2023; Wed, 10 May 2023; Tue, 09 May 2023; Mon, 08 May 2023; Fri, 05 May 2023; Thu, 04 May 2023; Wed, 03 May 2023; Tue, 02 May 2023; Mon, 01 May 2023; Fri, 28 Apr 2023; Thu, 27 Apr 2023; Wed, 26 Apr 2023; Tue, 25 Apr 2023; Mon, 24 Apr 2023; Fri, 21 Apr 2023; Wed, 19 Apr 2023; Tue, 18 Apr 2023; Mon, 17 Apr 2023; Fri, 14 Apr 2023; Thu, 13 Apr 2023; Wed, 12 Apr 2023; Tue, 11 Apr 2023; Mon, 10 Apr 2023
1.Optimal radio labelings of the Cartesian product of the generalized Peterson graph and tree

Authors:Payal Vasoya, Devsi Bantva

Abstract: A radio labeling of a graph $G$ is a function $f : V(G) \rightarrow \{0,1,2,\ldots\}$ such that $|f(u)-f(v)| \geq diam(G) + 1 - d(u,v)$ for every pair of distinct vertices $u,v$ of $G$. The radio number of $G$, denoted by $rn(G)$, is the smallest number $k$ such that $G$ has radio labeling $f$ with max$\{f(v):v \in V(G)\} = k$. In this paper, we give a lower bound for the radio number for the Cartesian product of the generalized Petersen graph and tree. We present two necessary and sufficient conditions, and three other sufficient conditions to achieve the lower bound. Using these results, we determine the radio number for the Cartesian product of the Peterson graph and stars.

2.No Where to Go But High: A Perspective on High Dimensional Expanders

Authors:Roy Gotlib, Tali Kaufman

Abstract: "No Where to go but in" is a well known statement of Osho. Osho meant to say that the answers to all our questions should be obtained by looking into ourselves. In a paraphrase to Osho's statement we say "No Where to go but high". This meant to demonstrate that for various seemingly unrelated topics and questions the only way to get significant progress is via the prism of a new philosophy (new field) called high dimensional expansion. In this note we give an introduction \footnote{This introduction reflects the authors' interests and by no mean claim to represent the field in a through way} to the high dimensional expansion philosophy, and how it has been useful recently in obtaining progress in various questions in seemingly unrelated fields. This exposition is dedicated to the memory of my mother, Sarah Kaufman, who was always trying to understand the reason why things behave in a certain way. It is also dedicated to the memory of my father Eliezer Kaufman.

3.Edge general position sets in Fibonacci and Lucas cubes

Authors:Sandi Klavžar, Elif Tan

Abstract: A set of edges $X\subseteq E(G)$ of a graph $G$ is an edge general position set if no three edges from $X$ lie on a common shortest path in $G$. The cardinality of a largest edge general position set of $G$ is the edge general position number of $G$. In this paper edge general position sets are investigated in partial cubes. In particular it is proved that the union of two largest $\Theta$-classes of a Fibonacci cube or a Lucas cube is a maximal edge general position set.

4.On the chromatic number of the plane with an arbitrarily short interval of forbidden distances

Authors:Vsevolod Voronov

Abstract: The work is devoted to to one of the variations of the Hadwiger--Nelson problem on the chromatic number of the plane. In this formulation one needs to find for arbitrarily small $\varepsilon$ the least possible number of colors needed to color the Euclidean plane in such a way that any two points, the distance between which belongs to the interval $[1-\varepsilon, 1+\varepsilon]$, are colored differently. The hypothesis proposed by G. Exoo in 2004, states that for arbitrary positive $\varepsilon$ at least 7 colors are required. Also, with a sufficiently small $\varepsilon$ the number of colors is exactly 7. The main result of this paper is the proof of this hypothesis.

5.Algebraic Characterization of the Voronoi Cell Structure of the $A_n$ Lattice

Authors:Minho Kim

Abstract: We characterized the combinatorial structure of the Voronoi cell of the $A_n$ lattice in arbitrary dimensions. Based on the well-known fact that the Voronoi cell is the disjoint union of $(n+1)!$ congruent simplices, we show that it is the disjoint union of $(n+1)$ congruent hyper-rhombi, which are the generalized rhombi or trigonal trapezohedra. The explicit structure of the faces is investigated, including the fact that all the $k$-dimensional faces, $2\le k\le n-1$, are hyper-rhombi. We show it to be the vertex-first orthogonal projection of the $(n+1)$-dimensional unit cube. Hence the Voronoi cell is a zonotope. We prove that in low dimensions ($n\le 3$) the Voronoi cell can be understood as the section of that of the $D_{n+1}$ lattice with the hyperplane orthogonal to the diagonal direction. We provide all the explicit coordinates and transformation matrices associated with our analysis. Most of our analysis is algebraic and easily accessible to those less familiar with the Coxeter-Dynkin diagrams.

6.Bounds on Maximum Weight Directed Cut

Authors:Jiangdong Ai, Stefanie Gerke, Gregory Gutin, Anders Yeo, Yacong Zhou

Abstract: We obtain lower and upper bounds for the maximum weight of a directed cut in the classes of weighted digraphs and weighted acyclic digraphs as well as in some of their subclasses. We compare our results with those obtained for the maximum size of a directed cut in unweighted digraphs. In particular, we show that a lower bound obtained by Alon, Bollobas, Gyafas, Lehel and Scott (J Graph Th 55(1) (2007)) for unweighted acyclic digraphs can be extended to weighted digraphs with the maximum length of a cycle being bounded by a constant and the weight of every arc being at least one. We state a number of open problems.

7.A note on the 1-2-3 Theorem for infinite graphs

Authors:Marcin Stawiski

Abstract: Karo\'nski, {\L}uczak and Thomason conjectured in 2004 that for every finite graph without isolated edge, the edges can be assigned weights from $\{1,2,3\}$ in such a way that the endvertices of each edge have different sums of incident edge weights. This is known as the 1-2-3 Conjecture, and it was only recently proved by Keusch. We extend this result to infinite graphs in the following way. If $G$ is a graph without isolated edge, then the edges can be assigned weights from $\{1,2,3\}$ is such a way that the endvertices of each edge have different sum of incident edge weights, or these endvertices have both the same infinite degree. We also investigate the extensions of theorems about total and list versions of 1-2-3 Conjecture to infinite graphs.

8.Critically 3-frustrated signed graphs

Authors:Chiara Cappello, Reza Naserasr, Eckhard Steffen, Zhouningxin Wang

Abstract: Extending the notion of maxcut, the study of the frustration index of signed graphs is one of the basic questions in the theory of signed graphs. Recently two of the authors initiated the study of critically frustrated signed graphs. That is a signed graph whose frustration index decreases with the removal of any edge. The main focus of this study is on critical signed graphs which are not edge-disjoint unions of critically frustrated signed graphs (namely non-decomposable signed graphs) and which are not built from other critically frustrated signed graphs by subdivision. We conjecture that for any given $k$ there are only finitely many critically $k$-frustrated signed graphs of this kind. Providing support for this conjecture we show that there are only two of such critically $3$-frustrated signed graphs where there is no pair of edge-disjoint negative cycles. Similarly, we show that there are exactly ten critically $3$-frustrated signed planar graphs that are neither decomposable nor subdivisions of other critically frustrated signed graphs. We present a method for building non-decomposable critically frustrated signed graphs based on two given such signed graphs. We also show that the condition of being non-decomposable is necessary for our conjecture.

9.Sparse vertex cutsets and the maximum degree

Authors:Stéphane Bessy, Johannes Rauch, Dieter Rautenbach, Uéverton S. Souza

Abstract: We show that every graph $G$ of maximum degree $\Delta$ and sufficiently large order has a vertex cutset $S$ of order at most $\Delta$ that induces a subgraph $G[S]$ of maximum degree at most $\Delta-3$. For $\Delta\in \{ 4,5\}$, we refine this result by considering also the average degree of $G[S]$. If $G$ has no $K_{r,r}$ subgraph, then we show the existence of a vertex cutset that induces a subgraph of maximum degree at most $\left(1-\frac{1}{{r\choose 2}}\right)\Delta+O(1)$.

10.Binomial convolutions for rational power series

Authors:Ira M. Gessel, Ishan Kar

Abstract: The binomial convolution of two sequences $\{a_n\}$ and $\{b_n\}$ is the sequence whose $n$th term is $\sum_{k=0}^{n} \binom{n}{k} a_k b_{n-k}$. If $\{a_n\}$ and $\{b_n\}$ have rational generating functions then so does their binomial convolution. We discuss an efficient method, using resultants, for computing this rational generating function and give several examples involving Fibonacci and tribonacci numbers and related sequences. We then describe a similar method for computing Hadamard products of rational generating functions. Finally we describe two additional methods for computing binomial convolutions and Hadamard products of rational power series, one using symmetric functions and one using partial fractions.