BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
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.
Let G(n,M) be the uniform random graph with n vertices and M edges. Let Bn be the maximum block-size of G(n,M) or the maximum size of its maximal 2-connected induced subgraphs. We determine the expectation of Bn near the critical point M=n/2. As n−2M≫n2/3, we find a constant c1 such that c1=limn→∞(1−n2M)EBn. Inside the window of transition of G(n,M) with M=2n(1+λn−1/3), where λ is any real number, we find an exact analytic expression for c2(λ)=limn→∞n1/3EBn. This study relies on the symbolic method and analytic tools coming from generating function theory which enable us to describe the evolution of n−1/3EBn as a function of λ.
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).
We analyze the cost used by a naive exhaustive search algorithm for finding a maximum independent set in random graphs under the usual G_{n,p} -model where each possible edge appears independently with the same probability p. The expected cost turns out to be of the less common asymptotic order n^{c\log n}, which we explore from several different perspectives. Also we collect many instances where such an order appears, from algorithmics to analysis, from probability to algebra. The limiting distribution of the cost required by the algorithm under a purely idealized random model is proved to be normal. The approach we develop is of some generality and is amenable for other graph algorithms.
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(λ)=limn→∞PrG(n,2n(1+λn−1/3))isplanar. In particular, we obtain p(0)≈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,2n) 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.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.