اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدImpartial digraphs
65
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We prove a conjecture of Fox, Huang, and Lee that characterizes directed graphs that have constant density in all tournaments: they are disjoint unions of trees that are each constructed in a certain recursive way.
قيم البحث
اقرأ أيضاً
We study a game where two players take turns selecting points of a convex geometry until the convex closure of the jointly selected points contains all the points of a given winning set. The winner of the game is the last player able to move. We deve
lop a structure theory for these games and use it to determine the nim number for several classes of convex geometries, including one-dimensional affine geometries, vertex geometries of trees, and games with a winning set consisting of extreme points.
We study an impartial avoidance game introduced by Anderson and Harary. The game is played by two players who alternately select previously unselected elements of a finite group. The first player who cannot select an element without making the set of
jointly-selected elements into a generating set for the group loses the game. We develop criteria on the maximal subgroups that determine the nim-numbers of these games and use our criteria to study our game for several families of groups, including nilpotent, sporadic, and symmetric groups.
A digraph is {em $d$-dominating} if every set of at most $d$ vertices has a common out-neighbor. For all integers $dgeq 2$, let $f(d)$ be the smallest integer such that the vertices of every 2-edge-colored (finite or infinite) complete digraph (inclu
ding loops) can be covered by the vertices of at most $f(d)$ monochromatic $d$-dominating subgraphs. Note that the existence of $f(d)$ is not obvious -- indeed, the question which motivated this paper was simply to determine whether $f(d)$ is bounded, even for $d=2$. We answer this question affirmatively for all $dgeq 2$, proving $4leq f(2)le 8$ and $2dleq f(d)le 2dleft(frac{d^{d}-1}{d-1}right)$ for all $dge 3$. We also give an example to show that there is no analogous bound for more than two colors. Our result provides a positive answer to a question regarding an infinite analogue of the Burr-ErdH{o}s conjecture on the Ramsey numbers of $d$-degenerate graphs. Moreover, a special case of our result is related to properties of $d$-paradoxical tournaments.
We study an impartial game introduced by Anderson and Harary. This game is played by two players who alternately choose previously-unselected elements of a finite group. The first player who builds a generating set from the jointly-selected elements
wins. We determine the nim-numbers of this game for generalized dihedral groups, which are of the form $operatorname{Dih}(A)= mathbb{Z}_2 ltimes A$ for a finite abelian group $A$.
Ramanujan graphs have fascinating properties and history. In this paper we explore a parallel notion of Ramanujan digraphs, collecting relevant results from old and recent papers, and proving some new ones. Almost-normal Ramanujan digraphs are shown
to be of special interest, as they are extreme in the sense of an Alon-Boppana theorem, and they have remarkable combinatorial features, such as small diameter, Chernoff bound for sampling, optimal covering time and sharp cutoff. Other topics explored are the connection to Cayley graphs and digraphs, the spectral radius of universal covers, Alons conjecture for random digraphs, and explicit constructions of almost-normal Ramanujan digraphs.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
