Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTwo Theorems on the Range of Strategy-proof Rules on a Restricted Domain
141
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Let g be a strategy-proof rule on the domain NP of profiles where no alternative Pareto-dominates any other and let g have range S on NP. We complete the proof of a Gibbard-Satterthwaite result - if S contains more than two elements, then g is dictatorial - by establishing a full range result on two subdomains of NP.
rate research
Read More
In 2020, Cameron et al. introduced the restricted numerical range of a digraph (directed graph) as a tool for characterizing digraphs and studying their algebraic connectivity. In particular, digraphs with a restricted numerical range of a single point, a horizontal line segment, and a vertical line segment were characterized as $k$-imploding stars, directed joins of bidirectional digraphs, and regular tournaments, respectively. In this article, we extend these results by investigating digraphs whose restricted numerical range is a convex polygon in the complex plane. We provide computational methods for identifying these polygonal digraphs and show that these digraphs can be broken into three disjoint classes: normal, restricted-normal, and pseudo-normal digraphs, all of which are closed under the digraph complement. We prove sufficient conditions for normal digraphs and show that the directed join of two normal digraphs results in a restricted-normal digraph. Also, we prove that directed joins are the only restricted-normal digraphs when the order is square-free or twice a square-free number. Finally, we provide methods to construct restricted-normal digraphs that are not directed joins for all orders that are neither square-free nor twice a square-free number.
Finding necessary and sufficient conditions for isomorphism between two semigroups of order-preserving transformations over an infinite domain with restricted range was an open problem in cite{FHQS}. In this paper, we show a proof strategy to answer that question.
In this paper we study a subfamily of a classic lattice path, the emph{Dyck paths}, called emph{restricted $d$-Dyck} paths, in short $d$-Dyck. A valley of a Dyck path $P$ is a local minimum of $P$; if the difference between the heights of two consecutive valleys (from left to right) is at least $d$, we say that $P$ is a restricted $d$-Dyck path. The emph{area} of a Dyck path is the sum of the absolute values of $y$-components of all points in the path. We find the number of peaks and the area of all paths of a given length in the set of $d$-Dyck paths. We give a bivariate generating function to count the number of the $d$-Dyck paths with respect to the the semi-length and number of peaks. After that, we analyze in detail the case $d=-1$. Among other things, we give both, the generating function and a recursive relation for the total area.
Let g be a strategy-proof rule on the domain NP of profiles where no alternative Pareto-dominates any other. Then we establish a result with a Gibbard-Satterthwaite flavor: g is dictatorial if its range contains at least three alternatives.
Komlos conjectured in 1981 that among all graphs with minimum degree at least $d$, the complete graph $K_{d+1}$ minimises the number of Hamiltonian subsets, where a subset of vertices is Hamiltonian if it contains a spanning cycle. We prove this conjecture when $d$ is sufficiently large. In fact we prove a stronger result: for large $d$, any graph $G$ with average degree at least $d$ contains almost twice as many Hamiltonian subsets as $K_{d+1}$, unless $G$ is isomorphic to $K_{d+1}$ or a certain other graph which we specify.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
