Mathematics – Combinatorics
Scientific paper
2004-11-06
Proceedings of FPSAC'04 (2004) 91-105
Mathematics
Combinatorics
Presented (as a poster) to the conference Formal Power Series and Algebraic Combinatorics (Vancouver, 2004), electronic procee
Scientific paper
In this article, we study directed graphs (digraphs) with a coloring constraint due to Von Neumann and related to Nim-type games. This is equivalent to the notion of kernels of digraphs, which appears in numerous fields of research such as game theory, complexity theory, artificial intelligence (default logic, argumentation in multi-agent systems), 0-1 laws in monadic second order logic, combinatorics (perfect graphs)... Kernels of digraphs lead to numerous difficult questions (in the sense of NP-completeness, #P-completeness). However, we show here that it is possible to use a generating function approach to get new informations: we use technique of symbolic and analytic combinatorics (generating functions and their singularities) in order to get exact and asymptotic results, e.g. for the existence of a kernel in a circuit or in a unicircuit digraph. This is a first step toward a generatingfunctionology treatment of kernels, while using, e.g., an approach "a la Wright". Our method could be applied to more general "local coloring constraints" in decomposable combinatorial structures.
Banderier Cyril
Bars Jean-Marie Le
Ravelomanana Vlady
No associations
LandOfFree
Generating Functions For Kernels of Digraphs (Enumeration & Asymptotics for Nim Games) does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Generating Functions For Kernels of Digraphs (Enumeration & Asymptotics for Nim Games), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generating Functions For Kernels of Digraphs (Enumeration & Asymptotics for Nim Games) will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-25246