Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userNotes on sets of first return
92
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We prove in this note that, for an alphabet with three letters, the set of first return to a given word in a set satisfying the tree condition is a basis of the free group.
rate research
Read More
Tree-chromatic number is a chromatic version of treewidth, where the cost of a bag in a tree-decomposition is measured by its chromatic number rather than its size. Path-chromatic number is defined analogously. These parameters were introduced by Seymour (JCTB 2016). In this paper, we survey all the known results on tree- and path-chromatic number and then present some new results and conjectures. In particular, we propose a version of Hadwigers Conjecture for tree-chromatic number. As evidence that our conjecture may be more tractable than Hadwigers Conjecture, we give a short proof that every $K_5$-minor-free graph has tree-chromatic number at most $4$, which avoids the Four Colour Theorem. We also present some hardness results and conjectures for computing tree- and path-chromatic number.
The promise of reinforcement learning is to solve complex sequential decision problems autonomously by specifying a high-level reward function only. However, reinforcement learning algorithms struggle when, as is often the case, simple and intuitive rewards provide sparse and deceptive feedback. Avoiding these pitfalls requires thoroughly exploring the environment, but creating algorithms that can do so remains one of the central challenges of the field. We hypothesise that the main impediment to effective exploration originates from algorithms forgetting how to reach previously visited states (detachment) and from failing to first return to a state before exploring from it (derailment). We introduce Go-Explore, a family of algorithms that addresses these two challenges directly through the simple principles of explicitly remembering promising states and first returning to such states before intentionally exploring. Go-Explore solves all heretofore unsolved Atari games and surpasses the state of the art on all hard-exploration games, with orders of magnitude improvements on the grand challenges Montezumas Revenge and Pitfall. We also demonstrate the practical potential of Go-Explore on a sparse-reward pick-and-place robotics task. Additionally, we show that adding a goal-conditioned policy can further improve Go-Explores exploration efficiency and enable it to handle stochasticity throughout training. The substantial performance gains from Go-Explore suggest that the simple principles of remembering states, returning to them, and exploring from them are a powerful and general approach to exploration, an insight that may prove critical to the creation of truly intelligent learning agents.
A subset $X$ in the $d$-dimensional Euclidean space is called a $k$-distance set if there are exactly $k$ distinct distances between two distinct points in $X$ and a subset $X$ is called a locally $k$-distance set if for any point $x$ in $X$, there are at most $k$ distinct distances between $x$ and other points in $X$. Delsarte, Goethals, and Seidel gave the Fisher type upper bound for the cardinalities of $k$-distance sets on a sphere in 1977. In the same way, we are able to give the same bound for locally $k$-distance sets on a sphere. In the first part of this paper, we prove that if $X$ is a locally $k$-distance set attaining the Fisher type upper bound, then determining a weight function $w$, $(X,w)$ is a tight weighted spherical $2k$-design. This result implies that locally $k$-distance sets attaining the Fisher type upper bound are $k$-distance sets. In the second part, we give a new absolute bound for the cardinalities of $k$-distance sets on a sphere. This upper bound is useful for $k$-distance sets for which the linear programming bound is not applicable. In the third part, we discuss about locally two-distance sets in Euclidean spaces. We give an upper bound for the cardinalities of locally two-distance sets in Euclidean spaces. Moreover, we prove that the existence of a spherical two-distance set in $(d-1)$-space which attains the Fisher type upper bound is equivalent to the existence of a locally two-distance set but not a two-distance set in $d$-space with more than $d(d+1)/2$ points. We also classify optimal (largest possible) locally two-distance sets for dimensions less than eight. In addition, we determine the maximum cardinalities of locally two-distance sets on a sphere for dimensions less than forty.
We study point sets arising from cut-and-project constructions. An important class is weak model sets, which include squarefree numbers and visible lattice points. For such model sets, we give a non-trivial upper bound on their pattern entropy in terms of the volume of the window boundary in internal space. This proves a conjecture by R.V. Moody.
A set $Ssubseteq 2^E$ of subsets of a finite set $E$ is emph{powerful} if, for all $Xsubseteq E$, the number of subsets of $X$ in $S$ is a power of 2. Each powerful set is associated with a non-negative integer valued function, which we call the rank function. Powerful sets were introduced by Farr and Wang as a generalisation of binary matroids, as the cocircuit space of a binary matroid gives a powerful set with the corresponding matroid rank function. In this paper we investigate how structural properties of a powerful set can be characterised in terms of its rank function. Powerful sets have four types of degenerate elements, including loops and coloops. We show that certain evaluations of the rank function of a powerful set determine the degenerate elements. We introduce powerful multisets and prove some fundamental results on them. We show that a powerful set corresponds to a binary matroid if and only if its rank function is subcardinal. This paper answers the two conjectures made by Farr and Wang in the affirmative.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
