BZPEERReading, trust and collaboration for researchDiscover
Workspaces
Network
Opportunities
Account
Researcher profile
Vlady Ravelomanana contributes to research discovery and scholarly infrastructure.
Trust snapshot
Actions
Identity and collaboration
Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.
Log in to claimDirect collaboration
Claim this author entity first to unlock direct invitations.
Research graph
Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
In this paper, we count acyclic and strongly connected uniform directed labeled hypergraphs. For these combinatorial structures, we introduce a specific generating function allowing us to recover and generalize some results on the number of directed acyclic graphs and the number of strongly connected directed graphs.
We introduce a new model of random multigraphs with colored vertices and weighted edges. It is similar to the "inhomogeneous random graph model" of Söderberg (2002), extended by Bollobás, Janson and Riordan (2007). By means of analytic combinatorics, we then analyze the birth of "complex components", which are components with at least two cycles. We apply those results to give a complete picture of the finite size scaling and the critical exponents associated to a rather broad family of decision problems. As applications, we derive new proofs of known results on the 2-colorability problem, already investigated by Pittel and Yeum (2010), and on the enumeration of properly q-colored multigraphs, analyzed by Wright (1972). We also obtain new results on the phase transition of the satisfiability of quantified 2-Xor-formulas, a problem introduced by Creignou, Daudé and Egly (2007).
Consider the uniform random graph $G(n,M)$ with $n$ vertices and $M$ edges. Erdős and Rényi (1960) conjectured that the limit $$ \lim_{n \to \infty} \Pr\{G(n,\textstyle{n\over 2}) is planar}} $$ exists and is a constant strictly between 0 and 1. Łuczak, Pittel and Wierman (1994) proved this conjecture and Janson, Łuczak, Knuth and Pittel (1993) gave lower and upper bounds for this probability. In this paper we determine the exact probability of a random graph being planar near the critical point $M=n/2$. For each $λ$, we find an exact analytic expression for $$ p(λ) = \lim_{n \to \infty} \Pr{G(n,\textstyle{n\over 2}(1+λn^{-1/3})) is planar}.$$ In particular, we obtain $p(0) \approx 0.99780$. We extend these results to classes of graphs closed under taking minors. As an example, we show that the probability of $G(n,\textstyle{n\over 2})$ being series-parallel converges to 0.98003. For the sake of completeness and exposition we reprove in a concise way several basic properties we need of a random graph near the critical point.
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.