Source author record

Sukhada Fadnavis

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.PR math.ST Statistics Theory

Catalog footprint

Research overview

5works

4topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Asymptotic quantization of exponential random graphs

We describe the asymptotic properties of the edge-triangle exponential random graph model as the natural parameters diverge along straight lines. We show that as we continuously vary the slopes of these lines, a typical graph drawn from this model exhibits quantized behavior, jumping from one complete multipartite graph to another, and the jumps happen precisely at the normal lines of a polyhedral set with infinitely many facets. As a result, we provide a complete description of all asymptotic extremal behaviors of the model.

preprint2015arXiv

A generalization of the Birthday problem and the chromatic polynomial

The birthday paradox states that there is at least a 50% chance that some two out of twenty-three randomly chosen people will share the same birth date. The calculation for this problem assumes that all birth dates are equally likely. We consider the following two modifications of this question. If the distribution of birthdays is non-uniform, does that increase or decrease the probability of matching birth dates? Further, what if we focus on birthdays shared by some particular pairs rather than any two people. Does a non-uniform distribution on birth dates increase or decrease the probability of a matching pair? In this paper we present our results in this generalized setting. We use some results and methods due to Sokal concerning bounds on the roots of chromatic polynomials to prove our results.

preprint2015arXiv

A note on the shameful conjecture

Let $P_G(q)$ denote the chromatic polynomial of a graph $G$ on $n$ vertices. The `shameful conjecture' due to Bartels and Welsh states that, $\frac{P_G(n)}{P_G(n-1)} \geq \frac{n^n}{(n-1)^n}.$ Let $μ(G)$ denote the expected number of colors used in a uniformly random proper $n$ -coloring of $G$ . The above inequality can be interpreted as saying that $μ(G) \geq μ(O_n)$ , where $O_n$ is the empty graph on $n$ nodes. This conjecture was proved by F. M. Dong, who in fact showed that, $\frac{P_G(q)}{P_G(q-1)} \geq \frac{q^n}{(q-1)^n}$ for all $q \geq n$ . There are examples showing that this inequality is not true for all $q \geq 2$ . In this paper, we show that the above inequality holds for all $q \geq 36D^{3/2}$ , where $D$ is the largest degree of $G$ . It is also shown that the above inequality holds true for all $q \geq 2$ when $G$ is a claw-free graph.

preprint2015arXiv

On the roots of hypergraph chromatic polynomials

Let $G = (V,E)$ be a finite, simple, connected graph with chromatic polynomial $P_G(q)$ . Sokal \cite{sokal} proved that the roots of the chromatic polynomial of $G$ are bounded in absolute value by $KD$ where, $D$ is the maximum degree of the graph and $7< K < 8$ is a constant. In this paper we generalize this result to uniform hypergraphs. To prove our results we will use the theory of the bounded exponential type graph polynomials.

preprint2011arXiv

On Brenti's conjecture about the log-concavity of the chromatic polynomial

The chromatic polynomial is a well studied object in graph theory. There are many results and conjectures about the log-concavity of the chromatic polynomial and other polynomials related to it. The location of the roots of these polynomials has also been well studied. One famous result due to A. Sokal and C. Borgs provides a bound on the absolute value of the roots of the chromatic polynomial in terms of the highest degree of the graph. We use this result to prove a modification of a log-concavity conjecture due to F. Brenti. The original conjecture of Brenti was that the chromatic polynomial is log-concave on the natural numbers. This was disproved by Paul Seymour by presenting a counter example. We show that the chromatic polynomial $P_G(q)$ of graph $G$ is in fact log-concave for all $q > CΔ+ 1$ for an explicit constant $C < 10$ , where $Δ$ denotes the highest degree of $G$ . We also provide an example which shows that the result is not true for constants $C$ smaller than 1.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Sukhada Fadnavis

Research overview

Is this your work?

5 publications

Asymptotic quantization of exponential random graphs

A generalization of the Birthday problem and the chromatic polynomial

A note on the shameful conjecture

On the roots of hypergraph chromatic polynomials

On Brenti's conjecture about the log-concavity of the chromatic polynomial

See the researcher in context

Building this map preview