Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userImpartial digraphs
65
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 develop 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 (including 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
