For integers $k\geq 1$ and $n\geq 2k+1$, the Schrijver graph $S(n,k)$ has as vertices all $k$-element subsets of $[n]:=\{1,2,\ldots,n\}$ that contain no two cyclically adjacent elements, and an edge between any two disjoint sets. More generally, for integers $k\geq 1$, $s\geq 2$, and $n \geq sk+1$, the $s$-stable Kneser graph $S(n,k,s)$ has as vertices all $k$-element subsets of $[n]$ in which any two elements are in cyclical distance at least $s$. We prove that all the graphs $S(n,k,s)$, in particular Schrijver graphs $S(n,k)=S(n,k,2)$, admit a Hamilton cycle that can be computed in time $\mathcal{O}(n)$ per generated vertex.
相關內容
\v{C}ech Persistence diagrams (PDs) are topological descriptors routinely used to capture the geometry of complex datasets. They are commonly compared using the Wasserstein distances $OT_{p}$; however, the extent to which PDs are stable with respect to these metrics remains poorly understood. We partially close this gap by focusing on the case where datasets are sampled on an $m$-dimensional submanifold of $\mathbb{R}^{d}$. Under this manifold hypothesis, we show that convergence with respect to the $OT_{p}$ metric happens exactly when $p\gt m$. We also provide improvements upon the bottleneck stability theorem in this case and prove new laws of large numbers for the total $\alpha$-persistence of PDs. Finally, we show how these theoretical findings shed new light on the behavior of the feature maps on the space of PDs that are used in ML-oriented applications of Topological Data Analysis.
Given a graph $G=(V,E)$, a function $f:V\to \{0,1,2\}$ is said to be a \emph{Roman Dominating function} if for every $v\in V$ with $f(v)=0$, there exists a vertex $u\in N(v)$ such that $f(u)=2$. A Roman Dominating function $f$ is said to be an \emph{Independent Roman Dominating function} (or IRDF), if $V_1\cup V_2$ forms an independent set, where $V_i=\{v\in V~\vert~f(v)=i\}$, for $i\in \{0,1,2\}$. The total weight of $f$ is equal to $\sum_{v\in V} f(v)$, and is denoted as $w(f)$. The \emph{Independent Roman Domination Number} of $G$, denoted by $i_R(G)$, is defined as min$\{w(f)~\vert~f$ is an IRDF of $G\}$. For a given graph $G$, the problem of computing $i_R(G)$ is defined as the \emph{Minimum Independent Roman Domination problem}. The problem is already known to be NP-hard for bipartite graphs. In this paper, we further study the algorithmic complexity of the problem. In this paper, we propose a polynomial-time algorithm to solve the Minimum Independent Roman Domination problem for distance-hereditary graphs, split graphs, and $P_4$-sparse graphs.
This paper addresses the problem of finding a minimum-cost $m$-state Markov chain $(S_0,\ldots,S_{m-1})$ in a large set of chains. The chains studied have a reward associated with each state. The cost of a chain is its "gain", i.e., its average reward under its stationary distribution. Specifically, for each $k=0,\ldots,m-1$ there is a known set ${\mathbb S}_k$ of type-$k$ states. A permissible Markov chain contains exactly one state of each type; the problem is to find a minimum-cost permissible chain. The original motivation was to find a cheapest binary AIFV-$m$ lossless code on a source alphabet of size $n$. Such a code is an $m$-tuple of trees, in which each tree can be viewed as a Markov Chain state. This formulation was then used to address other problems in lossless compression. The known solution techniques for finding minimum-cost Markov chains were iterative and ran in exponential time. This paper shows how to map every possible type-$k$ state into a type-$k$ hyperplane and then define a "Markov Chain Polytope" as the lower envelope of all such hyperplanes. Finding a minimum-cost Markov chain can then be shown to be equivalent to finding a "highest" point on this polytope. The local optimization procedures used in the previous iterative algorithms are shown to be separation oracles for this polytope. Since these were often polynomial time, an application of the Ellipsoid method immediately leads to polynomial time algorithms for these problems.
We prove that for any graph $G$ of maximum degree at most $\Delta$, the zeros of its chromatic polynomial $\chi_G(x)$ (in $\mathbb{C}$) lie inside the disc of radius $5.94 \Delta$ centered at $0$. This improves on the previously best known bound of approximately $6.91\Delta$. We also obtain improved bounds for graphs of high girth. We prove that for every $g$ there is a constant $K_g$ such that for any graph $G$ of maximum degree at most $\Delta$ and girth at least $g$, the zeros of its chromatic polynomial $\chi_G(x)$ lie inside the disc of radius $K_g \Delta$ centered at $0$, where $K_g$ is the solution to a certain optimization problem. In particular, $K_g < 5$ when $g \geq 5$ and $K_g < 4$ when $g \geq 25$ and $K_g$ tends to approximately $3.86$ as $g \to \infty$. Key to the proof is a classical theorem of Whitney which allows us to relate the chromatic polynomial of a graph $G$ to the generating function of so-called broken-circuit-free forests in $G$. We also establish a zero-free disc for the generating function of all forests in $G$ (aka the partition function of the arboreal gas) which may be of independent interest.
The convex dimension of a $k$-uniform hypergraph is the smallest dimension $d$ for which there is an injective mapping of its vertices into $\mathbb{R}^d$ such that the set of $k$-barycenters of all hyperedges is in convex position. We completely determine the convex dimension of complete $k$-uniform hypergraphs, which settles an open question by Halman, Onn and Rothblum, who solved the problem for complete graphs. We also provide lower and upper bounds for the extremal problem of estimating the maximal number of hyperedges of $k$-uniform hypergraphs on $n$ vertices with convex dimension $d$. To prove these results, we restate them in terms of affine projections that preserve the vertices of the hypersimplex. More generally, we provide a full characterization of the projections that preserve its $i$-dimensional skeleton. In particular, we obtain a hypersimplicial generalization of the linear van Kampen-Flores theorem: for each $n$, $k$ and $i$ we determine onto which dimensions can the $(n,k)$-hypersimplex be linearly projected while preserving its $i$-skeleton. Our results have direct interpretations in terms of $k$-sets and $(i,j)$-partitions, and are closely related to the problem of finding large convexly independent subsets in Minkowski sums of $k$ point sets.
We consider so-called $N$-fold integer programs (IPs) of the form $\max\{c^T x : Ax = b, \ell \leq x \leq u, x \in \mathbb Z^{nt}\}, where $A \in \mathbb Z^{(r+sn)\times nt} consists of $n$ arbitrary matrices $A^{(i)} \in \mathbb Z^{r\times t}$ on a horizontal, and $n$ arbitrary matrices $B^{(j)} \in \mathbb Z^{s\times t} on a diagonal line. Several recent works design fixed-parameter algorithms for $N$-fold IPs by taking as parameters the numbers of rows and columns of the $A$- and $B$-matrices, together with the largest absolute value $\Delta$ over their entries. These advances provide fast algorithms for several well-studied combinatorial optimization problems on strings, on graphs, and in machine scheduling. In this work, we extend this research by proposing algorithms that additionally harness a partition structure of submatrices $A^{(i)}$ and $B^{(j)}$, where row indices of non-zero entries do not overlap between any two sets in the partition. Our main result is an algorithm for solving any $N$-fold IP in time $nt log(nt)L^2(S_A)^{O(r+s)}(p_Ap_B\Delta)^{O(rp_Ap_B+sp_Ap_B)}$, where $p_A$ and $p_B$ are the size of the largest set in such a partition of $A^{(i)}$ and $B^{(j)}$, respectively, $S_A$ is the number of parts in the partition of $A = (A^{(1)},..., A^{(n)}), and $L = (log(||u - \ell||_\infty)\cdot (log(max_{x:\ell \leq x \leq u} |c^Tx|))$ is a measure of the input. We show that these new structural parameters are naturally small in high-multiplicity scheduling problems, such as makespan minimization on related and unrelated machines, with and without release times, the Santa Claus objective, and the weighted sum of completion times. In essence, we obtain algorithms that are exponentially faster than previous works by Knop et al. (ESA 2017) and Eisenbrand et al./Kouteck{\'y} et al. (ICALP 2018) in terms of the number of job types.
For non-decreasing sequence of integers $S=(a_1,a_2, \dots, a_k)$, an $S$-packing coloring of $G$ is a partition of $V(G)$ into $k$ subsets $V_1,V_2,\dots,V_k$ such that the distance between any two distinct vertices $x,y \in V_i$ is at least $a_{i}+1$, $1\leq i\leq k$. We consider the $S$-packing coloring problem on subclasses of subcubic graphs: For $0\le i\le 3$, a subcubic graph $G$ is said to be $i$-saturated if every vertex of degree 3 is adjacent to at most $i$ vertices of degree 3. Furthermore, a vertex of degree 3 in a subcubic graph is called heavy if all its three neighbors are of degree 3, and $G$ is said to be $(3,i)$-saturated if every heavy vertex is adjacent to at most $i$ heavy vertices. We prove that every 1-saturated subcubic graph is $(1,1,3,3)$-packing colorable and $(1,2,2,2,2)$-packing colorable. We also prove that every $(3,0)$-saturated subcubic graph is $(1,2,2,2,2,2)$-packing colorable.
This note provides a basic description of subgaussianity, by defining $(\sigma, \rho)$-subgaussian random variables $X$ ($\sigma>0, \rho>0$) as those satisfying $\mathbb{E}(\exp(\lambda X))\leq \rho\exp(\frac{1}{2}\sigma^2\lambda^2)$ for any $\lambda\in\mathbb{R}$. The introduction of the parameter $\rho$ may be particularly useful for those seeking to refine bounds, or align results from different sources, in the analysis of stochastic processes and concentration inequalities.
A linearly ordered (LO) $k$-colouring of a hypergraph assigns to each vertex a colour from the set $\{0,1,\ldots,k-1\}$ in such a way that each hyperedge has a unique maximum element. Barto, Batistelli, and Berg conjectured that it is NP-hard to find an LO $k$-colouring of an LO 2-colourable 3-uniform hypergraph for any constant $k\geq 2$ [STACS'21] but even the case $k=3$ is still open. Nakajima and \v{Z}ivn\'{y} gave polynomial-time algorithms for finding, given an LO 2-colourable 3-uniform hypergraph, an LO colouring with $O^*(\sqrt{n})$ colours [ICALP'22] and an LO colouring with $O^*(\sqrt[3]{n})$ colours [ACM ToCT'23]. Very recently, Louis, Newman, and Ray gave an SDP-based algorithm with $O^*(\sqrt[5]{n})$ colours. We present two simple polynomial-time algorithms that find an LO colouring with $O(\log_2(n))$ colours, which is an exponential improvement.
In the product $L_1\times L_2$ of two Kripke complete consistent logics, local tabularity of $L_1$ and $L_2$ is necessary for local tabularity of $L_1\times L_2$. However, it is not sufficient: the product of two locally tabular logics can be not locally tabular. We provide extra semantic and axiomatic conditions which give criteria of local tabularity of the product of two locally tabular logics. Then we apply them to identify new families of locally tabular products.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191