The metric dimension dim(G) of a graph $G$ is the minimum cardinality of a subset $S$ of vertices of $G$ such that each vertex of $G$ is uniquely determined by its distances to $S$. It is well-known that the metric dimension of a graph can be drastically increased by the modification of a single edge. Our main result consists in proving that the increase of the metric dimension of an edge addition can be amortized in the sense that if the graph consists of a spanning tree $T$ plus $c$ edges, then the metric dimension of $G$ is at most the metric dimension of $T$ plus $6c$. We then use this result to prove a weakening of a conjecture of Eroh et al. The zero forcing number $Z(G)$ of $G$ is the minimum cardinality of a subset $S$ of black vertices (whereas the other vertices are colored white) of $G$ such that all the vertices will turned black after applying finitely many times the following rule: a white vertex is turned black if it is the only white neighbor of a black vertex. Eroh et al. conjectured that, for any graph $G$, $dim(G)\leq Z(G) + c(G)$, where $c(G)$ is the number of edges that have to be removed from $G$ to get a forest. They proved the conjecture is true for trees and unicyclic graphs. We prove a weaker version of the conjecture: $dim(G)\leq Z(G)+6c(G)$ holds for any graph. We also prove that the conjecture is true for graphs with edge disjoint cycles, widely generalizing the unicyclic result of Eroh et al.
相關內容
A \emph{general branch-and-bound tree} is a branch-and-bound tree which is allowed to use general disjunctions of the form $\pi^{\top} x \leq \pi_0 \,\vee\, \pi^{\top}x \geq \pi_0 + 1$, where $\pi$ is an integer vector and $\pi_0$ is an integer scalar, to create child nodes. We construct a packing instance, a set covering instance, and a Traveling Salesman Problem instance, such that any general branch-and-bound tree that solves these instances must be of exponential size. We also verify that an exponential lower bound on the size of general branch-and-bound trees persists when we add Gaussian noise to the coefficients of the cross polytope, thus showing that polynomial-size "smoothed analysis" upper bound is not possible. The results in this paper can be viewed as the branch-and-bound analog of the seminal paper by Chv\'atal et al. \cite{chvatal1989cutting}, who proved lower bounds for the Chv\'atal-Gomory rank.
In this paper, we prove a local limit theorem for the chi-square distribution with $r > 0$ degrees of freedom and noncentrality parameter $\lambda \geq 0$. We use it to develop refined normal approximations for the survival function. Our maximal errors go down to an order of $r^{-2}$, which is significantly smaller than the maximal error bounds of order $r^{-1/2}$ recently found by Horgan & Murphy (2013) and Seri (2015). Our results allow us to drastically reduce the number of observations required to obtain negligible errors in the energy detection problem, from $250$, as recommended in the seminal work of Urkowitz (1967), to only $8$ here with our new approximations. We also obtain an upper bound on several probability metrics between the central and noncentral chi-square distributions and the standard normal distribution, and we obtain an approximation for the median that improves the lower bound previously obtained by Robert (1990).
We improve the bound on K\"uhnel's problem to determine the smallest $n$ such that the $k$-skeleton of an $n$-simplex $\Delta_n^{(k)}$ does not embed into a compact PL $2k$-manifold $M$ by showing that if $\Delta_n^{(k)}$ embeds into $M$, then $n\leq (2k+1)+(k+1)\beta_k(M;\mathbb Z_2)$. As a consequence we obtain improved Radon and Helly type results for set systems in such manifolds. Our main tool is a new description of an obstruction for embeddability of a $k$-complex $K$ into a compact PL $2k$-manifold $M$ via the intersection form on $M$. In our approach we need that for every map $f\colon K\to M$ the restriction to the $(k-1)$-skeleton of $K$ is nullhomotopic. In particular, this condition is satisfied in interesting cases if $K$ is $(k-1)$-connected, for example a $k$-skeleton of $n$-simplex, or if $M$ is $(k-1)$-connected. In addition, if $M$ is $(k-1)$-connected and $k\geq 3$, the obstruction is complete, meaning that a $k$-complex $K$ embeds into $M$ if and only if the obstruction vanishes. For trivial intersection forms, our obstruction coincides with the standard van Kampen obstruction. However, if the form is non-trivial, the obstruction is not linear but rather 'quadratic' in a sense that it vanishes if and only if certain system of quadratic diophantine equations is solvable. This may potentially be useful in attacking algorithmic decidability of embeddability of $k$-complexes into PL $2k$-manifolds.
A proof labelling scheme for a graph class $\mathcal{C}$ is an assignment of certificates to the vertices of any graph in the class $\mathcal{C}$, such that upon reading its certificate and the certificates of its neighbors, every vertex from a graph $G\in \mathcal{C}$ accepts the instance, while if $G\not\in \mathcal{C}$, for every possible assignment of certificates, at least one vertex rejects the instance. It was proved recently that for any fixed surface $\Sigma$, the class of graphs embeddable in $\Sigma$ has a proof labelling scheme in which each vertex of an $n$-vertex graph receives a certificate of at most $O(\log n)$ bits. The proof is quite long and intricate and heavily relies on an earlier result for planar graphs. Here we give a very short proof for any surface. The main idea is to encode a rotation system locally, together with a spanning tree supporting the local computation of the genus via Euler's formula.
Recently, random walks on dynamic graphs have been studied because of their adaptivity to the time-varying structure of real-world networks. In general, there is a tremendous gap between static and dynamic graph settings for the lazy simple random walk: Although $O(n^3)$ cover time was shown for any static graphs of $n$ vertices, there is an edge-changing dynamic graph with an exponential hitting time. On the other hand, previous works indicate that the random walk on a dynamic graph with a time-homogeneous stationary distribution behaves almost identically to that on a static graph. In this paper, we strengthen this insight by obtaining general and improved bounds. Specifically, we consider a random walk according to a sequence $(P_t)_{t\geq 1}$ of irreducible and reversible transition matrices such that all $P_t$ have the same stationary distribution. We bound the mixing, hitting, and cover times in terms of the hitting and relaxation times of the random walk according to the worst fixed $P_t$. Moreover, we obtain the first bounds of the hitting and cover times of multiple random walks and the coalescing time on dynamic graphs. These bounds can be seen as an extension of the well-known bounds of random walks on static graphs. Our results generalize the previous upper bounds for specific random walks on dynamic graphs, e.g., lazy simple random walks and $d_{\max}$-lazy walks, and give improved and tight upper bounds in various cases. As an interesting consequence of our generalization, we obtain tight bounds for the lazy Metropolis walk [Nonaka, Ono, Sadakane, and Yamashita, TCS10] on any dynamic graph: $O(n^2)$ mixing time, $O(n^2)$ hitting time, and $O(n^2\log n)$ cover time. Additionally, our coalescing time bound implies the consensus time bound of the pull voting on a dynamic graph.
In simplicial complexes it is well known that many of the global properties of the complex, can be deduced from expansion properties of its links. This phenomenon was first discovered by Garland [G]. In this work we develop a local to global machinery for general posets. We first show that the basic localization principle of Garland generalizes to more general posets. We then show that notable local to global theorems for simplicial complexes arise from general principles for general posets with expanding links. Specifically, we prove the following theorems for general posets satisfying some assumptions: Expanding links (one sided expansion) imply fast convergence of high dimensional random walks (generalization [KO,AL]); Expanding links imply Trickling down theorem (generalizing [O]); and a poset has expanding links (with two sided expansion) iff it satisfies a global random walk convergence property (generalization [DDFH]). We axiomatize general conditions on posets that imply local to global theorems. By developing this local to global machinery for general posets we discover that some posets behave better than simplicial complexes with respect to local to global implications. Specifically, we get a trickling down theorem for some posets (e.g. the Grassmanian poset) which is better behaved than the trickling down theorem known for simplicial complexes. In addition to this machinery, we also present a method to construct a new poset out of a pair of an initial poset and an auxiliary simplicial complex. By applying this procedure to the case where the pair is the Grassmanian poset and a bounded degree high dimensional expander, we obtain a bounded degree Grassmanian poset. We prove, using the tools described above, that this poset is a bounded degree expanding Grassmanian poset, partially proving a conjecture of [DDFH].
A strict bramble of a graph $G$ is a collection of pairwise-intersecting connected subgraphs of $G.$ The order of a strict bramble ${\cal B}$ is the minimum size of a set of vertices intersecting all sets of ${\cal B}.$ The strict bramble number of $G,$ denoted by ${\sf sbn}(G),$ is the maximum order of a strict bramble in $G.$ The strict bramble number of $G$ can be seen as a way to extend the notion of acyclicity, departing from the fact that (non-empty) acyclic graphs are exactly the graphs where every strict bramble has order one. We initiate the study of this graph parameter by providing three alternative definitions, each revealing different structural characteristics. The first is a min-max theorem asserting that ${\sf sbn}(G)$ is equal to the minimum $k$ for which $G$ is a minor of the lexicographic product of a tree and a clique on $k$ vertices (also known as the lexicographic tree product number). The second characterization is in terms of a new variant of a tree decomposition called lenient tree decomposition. We prove that ${\sf sbn}(G)$ is equal to the minimum $k$ for which there exists a lenient tree decomposition of $G$ of width at most $k.$ The third characterization is in terms of extremal graphs. For this, we define, for each $k,$ the concept of a $k$-domino-tree and we prove that every edge-maximal graph of strict bramble number at most $k$ is a $k$-domino-tree. We also identify three graphs that constitute the minor-obstruction set of the class of graphs with strict bramble number at most two. We complete our results by proving that, given some $G$ and $k,$ deciding whether ${\sf sbn}(G) \leq k$ is an ${\sf NP}$-complete problem.
An $n$-person game is specified by $n$ tensors of the same format. We view its equilibria as points in that tensor space. Dependency equilibria are defined by linear constraints on conditional probabilities, and thus by determinantal quadrics in the tensor entries. These equations cut out the Spohn variety, named after the philosopher who introduced dependency equilibria. The Nash equilibria among these are the tensors of rank one. We study the real algebraic geometry of the Spohn variety. This variety is rational, except for $2 \times 2$ games, when it is an elliptic curve. For $3 \times 2$ games, it is a del Pezzo surface of degree two. We characterize the payoff regions and their boundaries using oriented matroids, and we develop the connection to Bayesian networks in statistics.
We study the following two fixed-cardinality optimization problems (a maximization and a minimization variant). For a fixed $\alpha$ between zero and one we are given a graph and two numbers $k \in \mathbb{N}$ and $t \in \mathbb{Q}$. The task is to find a vertex subset $S$ of exactly $k$ vertices that has value at least (resp. at most for minimization) $t$. Here, the value of a vertex set computes as $\alpha$ times the number of edges with exactly one endpoint in $S$ plus $1-\alpha$ times the number of edges with both endpoints in $S$. These two problems generalize many prominent graph problems, such as Densest $k$-Subgraph, Sparsest $k$-Subgraph, Partial Vertex Cover, and Max ($k$,$n-k$)-Cut. In this work, we complete the picture of their parameterized complexity on several types of sparse graphs that are described by structural parameters. In particular, we provide kernelization algorithms and kernel lower bounds for these problems. A somewhat surprising consequence of our kernelizations is that Partial Vertex Cover and Max $(k,n-k)$-Cut not only behave in the same way but that the kernels for both problems can be obtained by the same algorithms.
In 1954, Alston S. Householder published Principles of Numerical Analysis, one of the first modern treatments on matrix decomposition that favored a (block) LU decomposition-the factorization of a matrix into the product of lower and upper triangular matrices. And now, matrix decomposition has become a core technology in machine learning, largely due to the development of the back propagation algorithm in fitting a neural network. The sole aim of this survey is to give a self-contained introduction to concepts and mathematical tools in numerical linear algebra and matrix analysis in order to seamlessly introduce matrix decomposition techniques and their applications in subsequent sections. However, we clearly realize our inability to cover all the useful and interesting results concerning matrix decomposition and given the paucity of scope to present this discussion, e.g., the separated analysis of the Euclidean space, Hermitian space, Hilbert space, and things in the complex domain. We refer the reader to literature in the field of linear algebra for a more detailed introduction to the related fields.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191