اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدAlgorithmic Traversals of Infinite Graphs
138
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
A traversal of a connected graph is a linear ordering of its vertices all of whose initial segments induce connected subgraphs. Traversals, and their refinements such as breadth-first and depth-first traversals, are computed by various graph searching algorithms. We extend the theory of generic search and breadth-first search from finite graphs to wellordered infinite graphs, recovering the notion of search trees in this context. We also prove tight upper bounds on the extent to which graph search and breadth-first search can modify the order type of the original graph, as well as characterize the traversals computed by these algorithms as lexicographically minimal.
قيم البحث
اقرأ أيضاً
N. Hindman, I. Leader and D. Strauss proved that it is consistent that there is a finite colouring of $mathbb R$ so that no infinite sumset $X+X={x+y:x,yin X}$ is monochromatic. Our aim in this paper is to prove a consistency result in the opposite d
irection: we show that, under certain set-theoretic assumptions, for any $c:mathbb Rto r$ with $r$ finite there is an infinite $Xsubseteq mathbb R$ so that $c$ is constant on $X+X$.
We investigate the transfinite game values arising in infinite chess, providing both upper and lower bounds on the supremum of these values---the omega one of chess---with two senses depending on whether one considers only finite positions or also po
sitions with infinitely many pieces. For lower bounds, we present specific infinite positions with transfinite game values of omega, omega^2, omega^2 times k, and omega^3. By embedding trees into chess, we show that there is a computable infinite chess position that is a win for white if the players are required to play according to a deterministic computable strategy, but which is a draw without that restriction. Finally, we prove that every countable ordinal arises as the game value of a position in infinite three-dimensional chess, and consequently the omega one of infinite three-dimensional chess is as large as it can be, namely, true omega one.
This article discusses some recent trends in Ramsey theory on infinite structures. Trees and their Ramsey theory have been vital to these investigations. The main ideas behind the authors recent method of trees with coding nodes are presented, showin
g how they can be useful both for coding structures with forbidden configurations as well as those with none. Using forcing as a tool for finite searches has allowed the development of Ramsey theory on such trees, leading to solutions for finite big Ramsey degrees of Henson graphs as well as infinite dimensional Ramsey theory of copies of the Rado graph. Possible future directions for applications of these methods are discussed.
We present a position in infinite chess exhibiting an ordinal game value of $omega^4$, thereby improving on the previously largest-known values of $omega^3$ and $omega^3cdot 4$.
We study new relations of the following statements with weak choice principles in ZF and ZFA. 1. For every infinite set X, there exists a permutation of X without fixed points. 2. There is no Hausdorff space X such that every infinite subset of X con
tains an infinite compact subset. 3. If a field has an algebraic closure then it is unique up to isomorphism. 4. Variants of Chain/Antichain principle. 5. Any infinite locally finite connected graph has a spanning subgraph omitting some complete bipartite graphs. 6. Any infinite locally finite connected graph has a spanning m bush for any even integer m greater than 4. We also study the new status of different weak choice principles in the finite partition model (a type of permutation model) introduced by Bruce in 2016. Further, we prove that Van Douwens Choice Principle holds in two recently constructed known permutation models.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
