检索结果-内蒙古大学图书馆

2017年

作者： Liu, Yanpei

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

关键词： mathematics combinatorics and graph theory

来源：评论

学校读者我要写书评

暂无评论

A dynamic intranet-based online-portal support for Computer Science teaching

引用

EDUCATION AND INFORMATION TECHNOLOGIES 2017年第3期22卷 827-840页

作者： Iyer, Viswanathan K. Natl Inst Technol Dept Comp Sci & Engn Tiruchirappalli 620015 Tamil Nadu India

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

关键词： Computer-assisted learning Learning portal Active learning OEIS Intranet portal Undergraduate teaching combinatorics and graph theory

来源：评论

学校读者我要写书评

暂无评论

Improved tree decomposition based algorithms for domination-like problems 5

引用

5th Latin American Symposium on Theoretical Informatics (LATIN 2002)

作者： Alber, J Niedermeier, R Univ Tubingen Wilhelm Schickard Inst Informat D-72076 Tubingen Germany

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.

关键词： algorithms and data structures combinatorics and graph theory computational complexity

来源：评论

学校读者我要写书评

暂无评论

Expander Random Walks: A Fourier-Analytic Approach 2021

Expander Random Walks: A Fourier-Analytic Approach

引用

53rd Annual ACM SIGACT Symposium on theory of Computing (STOC)

作者： Cohen, Gil Peri, Noam Ta-Shma, Amnon Tel Aviv Univ Tel Aviv Israel

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.

关键词： combinatorics and graph theory Computational complexity Randomness in computing

来源：评论

学校读者我要写书评

暂无评论

Exponential growth constants for spanning forests on Archimedean lattices: Values and comparisons of upper bounds

引用

INTERNATIONAL JOURNAL OF MODERN PHYSICS B 2021年第6期35卷

作者： Chang, Shu-Chiuan Shrock, Robert Natl Cheng Kung Univ Dept Phys Tainan 70101 Taiwan SUNY Stony Brook CN Yang Inst Theoret Phys Stony Brook NY 11794 USA SUNY Stony Brook Dept Phys & Astron Stony Brook NY 11794 USA

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.

关键词： combinatorics and graph theory general statistical methods classical statistical mechanics

来源：评论

学校读者我要写书评

暂无评论

The frustration-free fully packed loop model

引用

JOURNAL OF PHYSICS A-MATHEMATICAL AND THEORETICAL 2023年第19期56卷 194001-194001页

作者： Zhang, Zhao Roising, Henrik Schou Sez Trieste SISSA via Bonomea 265 I-34136 Trieste Italy Sez Trieste INFN via Bonomea 265 I-34136 Trieste Italy KTH Royal Inst Technol Nordita Hannes Alfvens vag 12 SE-10691 Stockholm Sweden Stockholm Univ Hannes Alfvens vag 12 SE-10691 Stockholm Sweden Univ Copenhagen Niels Bohr Inst Jagtvej 155A DK-2200 Copenhagen Denmark

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.

关键词： self-avoiding walks two-dimensional spin models lattice models in condensed matter quantum entanglement exact enumeration combinatorics and graph theory

来源：评论

学校读者我要写书评

暂无评论

Asymptotic behavior of spanning forests and connected spanning subgraphs on two-dimensional lattices

引用

INTERNATIONAL JOURNAL OF MODERN PHYSICS B 2020年第27期34卷

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.

关键词： combinatorics and graph theory general statistical methods classical statistical mechanic

来源：评论

学校读者我要写书评

暂无评论

Scalable Computational Methods for the Analysis of High-Throughput Biological Data

Scalable Computational Methods for the Analysis of High-Thro...

引用

作者： Langston, Michael A University of Tennessee Knoxville TN

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：