This book presents a topological approach to combinatorial configurations, in particular graphs, by introducing a new pair of homology and cohomology via polyhedra. On this basis, a number of problems are solved using...
详细信息
ISBN:
(数字)9783110479492
ISBN:
(纸本)9783110476699
This book presents a topological approach to combinatorial configurations, in particular graphs, by introducing a new pair of homology and cohomology via polyhedra. On this basis, a number of problems are solved using a new approach, such as the embeddability of a graph on a surface (orientable and nonorientable) with given genus, the Gauss crossing conjecture, the graphicness and cographicness of a matroid, and so forth. Notably, the specific case of embeddability on a surface of genus zero leads to a number of corollaries, including the theorems of Lefschetz (on double coverings), of MacLane (on cycle bases), and of Whitney (on duality) for planarity. Relevant problems include the Jordan axiom in polyhedral forms, efficient methods for extremality and for recognizing a variety of embeddings (including rectilinear layouts in VLSI), and pan-polynomials, including those of Jones, Kauffman (on knots), and Tutte (on graphs), among others. ContentsPreliminariesPolyhedraSurfaces Homology on Polyhedra Polyhedra on the Sphere Automorphisms of a Polyhedron Gauss Crossing Sequences Cohomology on graphs Embeddability on Surfaces Embeddings on Sphere Orthogonality on Surfaces Net Embeddings Extremality on Surfaces Matroidal graphicness Knot Polynomials
This paper addresses the issue of effective content-delivery of Computer Science subjects taking advantage of a university intranet. The proposal described herein for teaching a subject like combinatorics and graph Th...
详细信息
This paper addresses the issue of effective content-delivery of Computer Science subjects taking advantage of a university intranet. The proposal described herein for teaching a subject like combinatorics and graph theory (CGT) is to supplement lectures with a moderated online forum against an associated intranet portal, which is referred to as a CGT-portal. The contents of a CGT-portal in a university intranet is required to be assembled by moderators and students during the progress of the CGT course. When completed at the end of a CGT course, a CGT-portal may be seen as a restricted view of the Online Encyclopaedia of Integer Sequences (OEIS: see http://***-the restriction can be with respect to sequences in OEIS that are directly relevant to say CGT). In the context of OEIS, an integer-sequence enthusiast experiences this cycle: understand a page in OEIS-ponder over the contents-read afresh/refresh related content-suggest new additions to OEIS-wait for approval or rejection-repeat this cycle. This experience can be imparted to students of a CGT course with the help of a CGT-portal. For organizing a CGT course, a first task is to partially create a miniature OEIS-like instructor-moderated CGT-portal in a university intranet. During the course of lectures and tutorials in CGT, students are asked to explore/contribute to the CGT-portal and these may be critically augmented/approved by instructors suitably, to find a place in the portal. Moderation also includes feedbacks (in many sense, a form of guidance) to students using/contributing to, the portal. By this, many concepts can be conveyed to the students in an interesting way with the desired results. It is pointed out that the dynamic nature of a CGT-portal promotes active learning philosophy, the success of which depends on understanding the background and psychology of the student population. Some design guidelines associated with the building-up of a CGT-portal e.g., grouping of prerequisites of a logica
We present an improved dynamic programming strategy for DOMINATING SET and related problems on graphs that are given together with a tree decomposition of width k. We obtain an O(4(k) n) algorithm for DOMINATING SET, ...
详细信息
ISBN:
(纸本)3540434003
We present an improved dynamic programming strategy for DOMINATING SET and related problems on graphs that are given together with a tree decomposition of width k. We obtain an O(4(k) n) algorithm for DOMINATING SET, where n is the number of nodes of the tree decomposition. This result improves the previously best known algorithm of Telle and Proskurowski running in time O(9(k) n). The key to our result is an argument on a certain "monotonicity" in the table updating process during dynamic programming. Moreover, various other domination-like problems as discussed by Telle and Proskurowski are treated with our technique. We gain improvements on the base of the exponential term in the running time ranging between 55% and 68% in most of these cases. These results mean significant breakthroughs concerning practical implementations.
In this work we ask the following basic question: assume the vertices of an expander graph are labelled by 0, 1. What "test" functions f : {0, 1}(t) -> {0, 1} cannot distinguish t independent samples from...
详细信息
ISBN:
(纸本)9781450380539
In this work we ask the following basic question: assume the vertices of an expander graph are labelled by 0, 1. What "test" functions f : {0, 1}(t) -> {0, 1} cannot distinguish t independent samples from those obtained by a random walk? The expander hitting property due to Ajtai, Komlos and Szemeredi (STOC 1987) is captured by the AND test function, whereas the fundamental expander Chernoff bound due to Gillman (SICOMP 1998), Heally (Computational Complexity 2008) is about test functions indicating whether the weight is close to the mean. In fact, it is known that all threshold functions are fooled by a random walk (Kipnis and Varadhan, Communications in Mathematical Physics 1986). Recently, it was shown that even the highly sensitive PARITY function is fooled by a random walk Ta-Shma (STOC 2017). We focus on balanced labels. Our first main result is proving that all symmetric functions are fooled by a random walk. Put differently, we prove a central limit theorem (CLT) for expander random walks with respect to the total variation distance, significantly strengthening the classic CLT for Markov Chains that is established with respect to the Kolmogorov distance (Kipnis and Varadhan, Communications in Mathematical Physics 1986). Our approach significantly deviates from prior works. We first study how well a Fourier character xs is fooled by a random walk as a function of S. Then, given a test function f, we expand f in the Fourier basis and combine the above with known results on the Fourier spectrum of f. We also proceed further and consider general test functions not necessarily symmetric. As our approach is Fourier analytic, it is general enough to analyze such versatile test functions. For our second result, we prove that random walks on sufficiently good expander graphs fool tests functions computed by AC(0) circuits, read-once branching programs, and functions with bounded query complexity.
We compare our upper bounds on the exponential growth constant phi(Lambda) characterizing the asymptotic behavior of spanning forests on Archimedean lattices Lambda with recently derived upper bounds. Our upper bounds...
详细信息
We compare our upper bounds on the exponential growth constant phi(Lambda) characterizing the asymptotic behavior of spanning forests on Archimedean lattices Lambda with recently derived upper bounds. Our upper bounds on phi(Lambda), which are very close to the respective values of phi(Lambda) that we have calculated, are shown to be significantly better for these lattices than the new upper bounds.
We consider a quantum fully packed loop model on the square lattice with a frustration-free projector Hamiltonian and ring-exchange interactions acting on plaquettes. A boundary Hamiltonian is added to favor domain-wa...
详细信息
We consider a quantum fully packed loop model on the square lattice with a frustration-free projector Hamiltonian and ring-exchange interactions acting on plaquettes. A boundary Hamiltonian is added to favor domain-wall boundary conditions and link ground state properties to the combinatorics and six-vertex model literature. We discuss how the boundary term fractures the Hilbert space into Krylov subspaces, and we prove that the Hamiltonian is ergodic within each subspace, leading to a series of energy-equidistant exact eigenstates in the lower end of the spectrum. Among them we systematically classify both finitely entangled eigenstates and product eigenstates. Using a recursion relation for enumerating half-plane configurations, we compute numerically the exact entanglement entropy of the ground state, confirming area law scaling. Finally, the spectrum is shown to be gapless in the thermodynamic limit with a trial state constructed by adding a twist to the ground state superposition.
We calculate exponential growth constants phi and sigma describing the asymptotic behavior of spanning forests and connected spanning subgraphs on strip graphs, with arbitrarily great length, of several two-dimensiona...
详细信息
We calculate exponential growth constants phi and sigma describing the asymptotic behavior of spanning forests and connected spanning subgraphs on strip graphs, with arbitrarily great length, of several two-dimensional lattices, including square, triangular, honeycomb, and certain heteropolygonal Archimedean lattices. By studying the limiting values as the strip widths get large, we infer lower and upper bounds on these exponential growth constants for the respective infinite lattices. Since our lower and upper bounds are quite close to each other, we can infer very accurate approximate values for these exponential growth constants, with fractional uncertainties ranging from O(10(-4)) to O(10(-2)). We show that phi and sigma are monotonically increasing functions of vertex degree for these lattices.
暂无评论