اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدExtending Precolorings to Distinguish Group Actions
97
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Given a group $Gamma$ acting on a set $X$, a $k$-coloring $phi:Xto{1,dots,k}$ of $X$ is distinguishing with respect to $Gamma$ if the only $gammain Gamma$ that fixes $phi$ is the identity action. The distinguishing number of the action $Gamma$, denoted $D_{Gamma}(X)$, is then the smallest positive integer $k$ such that there is a distinguishing $k$-coloring of $X$ with respect to $Gamma$. This notion has been studied in a number of settings, but by far the largest body of work has been concerned with finding the distinguishing number of the action of the automorphism group of a graph $G$ upon its vertex set, which is referred to as the distinguishing number of $G$. The distinguishing number of a group action is a measure of how difficult it is to break all of the permutations arising from that action. In this paper, we aim to further differentiate the resilience of group actions with the same distinguishing number. In particular, we introduce a precoloring extension framework to address this issue. A set $S subseteq X$ is a fixing set for $Gamma$ if for every non-identity element $gamma in Gamma$ there is an element $s in S$ such that $gamma(s) eq s$. The distinguishing extension number $operatorname{ext}_D(X,Gamma;k)$ is the minimum number $m$ such that for all fixing sets $W subseteq X$ with $|W| geq m$, every $k$-coloring $c : X setminus W to [k]$ can be extended to a $k$-coloring that distinguishes $X$. In this paper, we prove that $operatorname{ext}_D(mathbb{R},operatorname{Aut}(mathbb{R}),2) =4$, where $operatorname{Aut}(mathbb{R})$ is comprised of compositions of translations and reflections. We also consider the distinguishing extension number of the circle and (finite) cycles, obtaining several exact results and bounds.
قيم البحث
اقرأ أيضاً
Speakers communicate to influence their partners beliefs and shape their actions. Belief- and action-based objectives have been explored independently in recent computational models, but it has been challenging to explicitly compare or integrate them
. Indeed, we find that they are conflated in standard referential communication tasks. To distinguish these accounts, we introduce a new paradigm called signaling bandits, generalizing classic Lewis signaling games to a multi-armed bandit setting where all targets in the context have some relative value. We develop three speaker models: a belief-oriented speaker with a purely informative objective; an action-oriented speaker with an instrumental objective; and a combined speaker which integrates the two by inducing listener beliefs that generally lead to desirable actions. We then present a series of simulations demonstrating that grounding production choices in future listener actions results in relevance effects and flexible uses of nonliteral language. More broadly, our findings suggest that language games based on richer decision problems are a promising avenue for insight into rational communication.
We provide combinatorial interpretation for the $gamma$-coefficients of the basic Eulerian polynomials that enumerate permutations by the excedance statistic and the major index as well as the corresponding $gamma$-coefficients for derangements. Our
results refine the classical $gamma$-positivity results for the Eulerian polynomials and the derangement polynomials. The main tools are Brandens modified Foata--Strehl action on permutations and the recent triple statistic (des, rix,aid) equidistibuted with (exc, fix, maj).
We study maps on the set of permutations of n generated by the Renyi-Foata map intertwined with other dihedral symmetries (of a permutation considered as a 0-1 matrix). Iterating these maps leads to dynamical systems that in some cases exhibit intere
sting orbit structures, e.g., every orbit size being a power of two, and homomesic statistics (ones which have the same average over each orbit). In particular, the number of fixed points (aka 1-cycles) of a permutation appears to be homomesic with respect to three of these maps, even in one case where the orbit structures are far from nice. For the most interesting such Foatic action, we give a heap analysis and recursive structure that allows us to prove the fixed-point homomesy and orbit properties, but two other cases remain conjectural.
Let $G$ be a connected finite graph. Backman, Baker, and Yuen have constructed a family of explicit and easy-to-describe bijections $g_{sigma,sigma^*}$ between spanning trees of $G$ and $(sigma,sigma^*)$-compatible orientations, where the $(sigma,sig
ma^*)$-compatible orientations are the representatives of equivalence classes of orientations up to cycle-cocycle reversal which are determined by a cycle signature $sigma$ and a cocycle signature $sigma^*$. Their proof makes use of zonotopal subdivisions and the bijections $g_{sigma,sigma^*}$ are called emph{geometric bijections}. In this paper, we extend the geometric bijections to subgraph-orientation correspondences. Moreover, we extend the geometric constructions accordingly. Our proofs are purely combinatorial, even for the geometric constructions. We also provide geometric proofs for partial results, which make use of zonotopal tiling, relate to Backman, Baker, and Yuens method, and motivate our combinatorial constructions. Finally, we explain that the main results hold for emph{regular matroids}.
Given discrete groups $Gamma subset Delta$ we characterize $(Gamma,sigma)$-invariant spaces that are also invariant under $Delta$. This will be done in terms of subspaces that we define using an appropriate Zak transform and a particular partition of
the underlying group. On the way, we obtain a new characterization of principal $(Gamma,sigma)$-invariant spaces in terms of the Zak transform of its generator. This result is in the spirit of the analogous in the context of shift-invariant spaces in terms of the Fourier transform, which is very well-known. As a consequence of our results, we give a solution for the problem of finding the $(Gamma,sigma)$-invariant space nearest - in the sense of least squares - to a given set of data.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
