Source author record

Anant Godbole

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.HO math.NT math.ST Statistics Theory

Catalog footprint

Research overview

22works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Threshold Progressions in a Variety of Covering and Packing Contexts

Using standard methods (due to Janson, Stein-Chen, and Talagrand) from probabilistic combinatorics, we explore the following general theme: As one progresses from each member of a family of objects ${\cal A}$ being "covered" by at most one object in a random collection ${\cal C}$ , to being covered at most $λ$ times, to being covered at least once, to being covered at least $λ$ times, a hierarchy of thresholds emerge. We will then see how such results vary according to the context, and level of dependence introduced. Examples will be from extremal set theory, combinatorics, and additive number theory.

preprint2016arXiv

Some Results on Superpatterns for Preferential Arrangements

A {\it superpattern} is a string of characters of length $n$ that contains as a subsequence, and in a sense that depends on the context, all the smaller strings of length $k$ in a certain class. We prove structural and probabilistic results on superpatterns for {\em preferential arrangements}, including (i) a theorem that demonstrates that a string is a superpattern for all preferential arrangements if and only if it is a superpattern for all permutations; and (ii) a result that is reminiscent of a still unresolved conjecture of Alon on the smallest permutation on $[n]$ that contains all $k$ -permutations with high probability.

preprint2016arXiv

The Total Acquisition Number of the Randomly Weighted Path

There exists a significant body of work on determining the acquisition number $a_t(G)$ of various graphs when the vertices of those graphs are each initially assigned a unit weight. We determine properties of the acquisition number of the path, star, complete, complete bipartite, cycle, and wheel graphs for variations on this initial weighting scheme, with the majority of our work focusing on the expected acquisition number of randomly weighted graphs. In particular, we bound the expected acquisition number $E(a_t(P_n))$ of the $n$ -path when $n$ distinguishable "units" of integral weight, or chips, are randomly distributed across its vertices between $0.242n$ and $0.375n$ . With computer support, we improve it by showing that $E(a_t(P_n))$ lies between $0.29523n$ and $0.29576n$ . We then use subadditivity to show that the limiting ratio $\lim E(a_t(P_n))/n$ exists, and simulations reveal more exactly what the limiting value equals. The Hoeffding-Azuma inequality is used to prove that the acquisition number is tightly concentrated around its expected value. Additionally, in a different context, we offer a non-optimal acquisition protocol algorithm for the randomly weighted path and exactly compute the expected size of the resultant residual set.

preprint2015arXiv

The Number of Seymour Vertices in Random Tournaments and Digraphs

Seymour's distance two conjecture states that in any digraph there exists a vertex (a "Seymour vertex") that has at least as many neighbors at distance two as it does at distance one. We explore the validity of probabilistic statements along lines suggested by Seymour's conjecture, proving that almost surely there are a "large" number of Seymour vertices in random tournaments and "even more" in general random digraphs.

preprint2015arXiv

Universal and Near-Universal Cycles of Set Partitions

We study universal cycles of the set ${\cal P}(n,k)$ of $k$ -partitions of the set $[n]:=\{1,2,\ldots,n\}$ and prove that the transition digraph associated with ${\cal P}(n,k)$ is Eulerian. But this does not imply that universal cycles (or ucycles) exist, since vertices represent equivalence classes of partitions! We use this result to prove, however, that ucycles of ${\cal P}(n,k)$ exist for all $n \geq 3$ when $k=2$ . We reprove that they exist for odd $n$ when $k = n-1$ and that they do not exist for even $n$ when $k = n-1$ . An infinite family of $(n,k)$ for which ucycles do not exist is shown to be those pairs for which $S(n-2, k-2)$ is odd ( $3 \leq k < n-1$ ). We also show that there exist universal cycles of partitions of $[n]$ into $k$ subsets of distinct sizes when $k$ is sufficiently smaller than $n$ , and therefore that there exist universal packings of the partitions in ${\cal P}(n,k)$ . An analogous result for coverings completes the investigation.

preprint2014arXiv

Covering Array Bounds Using Analytical Techniques

A $t$ -covering array with entries from the alphabet ${\cal Q}=\{0,1,\ldots,q-1\}$ is a $k\times n$ stack, so that for any choice of $t$ (typically non-consecutive) columns, each of the $q^{t}$ possible $t$ -letter words over ${\cal Q}$ appear at least once among the rows of the selected columns. We will show how a combination of the Lovász local lemma; combinatorial analysis; Stirling's formula; and Calculus enables one to find better asymptotic bounds for the minimum size of $t$ -covering arrays, notably for $t = 3, 4$ . Here size is measured in the number of rows, as expressed in terms of the number of columns.

preprint2014arXiv

Distribution of the Maximum and Minimum of a Random Number of Bounded Random Variables

We study a new family of random variables, that each arise as the distribution of the maximum or minimum of a random number $N$ of i.i.d.~random variables $X_1,X_2,\ldots,X_N$ , each distributed as a variable $X$ with support on $[0,1]$ . The general scheme is first outlined, and several special cases are studied in detail. Wherever appropriate, we find estimates of the parameter $θ$ in the one-parameter family in question.

preprint2014arXiv

On the Longest Common Pattern Contained in Two or More Random Permutations

We provide upper and lower bounds for the expected length $\mathbb E(L_{n,m})$ of the longest common pattern contained in $m$ random permutations of length $n$ . We also address the tightness of the concentration of $L_{n,m}$ around $\mathbb E(L_{n,m})$ .

preprint2014arXiv

Telescoping Sums, Permutations, and First Occurrence Distributions

Telescoping sums very naturally lead to probability distributions on ${\mathbb Z}^+$ . But are these distributions typically cosmetic and devoid of motivation? In this paper we give three examples of "first occurrence" distributions, each defined by telescoping sums, and that each arise from concrete questions about the structure of permutations.

preprint2014arXiv

The Location of the First Ascent in a 123-Avoiding Permutation

It is natural to ask, given a permutation with no three-term ascending subsequence, at what index the first ascent occurs. We shall show, using both a recursion and a bijection, that the number of 123-avoiding permutations at which the first ascent occurs at positions $k,k+1$ is given by the $k$ -fold Catalan convolution $C_{n,k}$ . For $1\le k\le n$ , $C_{n,k}$ is also seen to enumerate the number of 123-avoiding permutations with $n$ being in the $k$ th position. Two interesting discrete probability distributions, related obliquely to the Poisson and geometric random variables, are derived as a result.

preprint2014arXiv

Universal and Overlap Cycles for Posets, Words, and Juggling Patterns

We discuss results dealing with universal cycles (u-cycles) and $s$ -overlap cycles, and contribute to the body of those results by proving existence of universal cycles of naturally labeled posets (NL posets), $s$ -overlap cycles of words of weight $k$ , and juggling patterns. The result on posets is, to the best of our knowledge, the first demonstration of the existence of a u-cycle whose length is unknown.

preprint2013arXiv

Bounds on the Maximum Number of Minimum Dominating Sets

We use probabilistic methods to find lower bounds on the maximum number, in a graph with domination number γ, of dominating sets of size γ. We find that we can randomly generate a graph that, w.h.p., is dominated by almost all sets of size γ. At the same time, we use a modified adjacency matrix to obtain lower bounds on the number of sets of a given size that do not dominate a graph on n vertices

preprint2013arXiv

Contributions to the theory of de Bruijn cycles

A de Bruijn cycle is a cyclic listing of length A, of a collection of A combinatorial objects, so that each object appears exactly once as a set of consecutive elements in the cycle. In this paper, we show the power of de Bruijn's original theorem, namely that the cycles bearing his name exist for n-letter words on a k-letter alphabet for all values of k,n, to prove that we can create de Bruijn cycles for the assignment of elements of [n]={1,2,....,n} to the sets in any labeled subposet of the Boolean lattice; de Bruijn's theorem corresponds to the case when the subposet in question consists of a single ground element. The landmark work of Chung, Diaconis, and Graham extended the agenda of finding de Bruijn cycles to possibly the next most natural set of combinatorial objects, namely k-subsets of [n]. In this area, important contributions have been those of Hurlbert and Rudoy. Here we follow the direction of Blanca and Godbole, who proved that, in a suitable encoding, de Bruijn cycles can be created for the subsets of [n $of size in the interval [s,t]; 0<=s<t<=n$ . In this paper we generalize this result to exhibit existence of de Bruijn cycles for words with weight between s and t, where these parameters are suitably restricted.

preprint2013arXiv

Maximum Number of Minimum Dominating and Minimum Total Dominating Sets

Given a connected graph with domination (or total domination) number γ>=2, we ask for the maximum number m_γand m_{γ,T} of dominating and total dominating sets of size γ. An exact answer is provided for γ=2and lower bounds are given for γ>=3.

preprint2013arXiv

Pattern Avoidance in Ordered Set Partitions

In this paper we consider the enumeration of ordered set partitions avoiding a permutation pattern of length 2 or 3. We provide an exact enumeration for avoiding the permutation 12. We also give exact enumeration for ordered partitions with 3 blocks and ordered partitions with n-1 blocks avoiding a permutation of length 3. We use enumeration schemes to recursively enumerate 123-avoiding ordered partitions with any block sizes. Finally, we give some asymptotic results for the growth rates of the number of ordered set partitions avoiding a single pattern; including a Stanley-Wilf type that exhibits existence of such growth rates.

preprint2013arXiv

Universal Cycles of Complementary Classes

Universal Cycles, or U-cycles, as originally defined by de Bruijn, are an efficient method to exhibit a large class of combinatorial objects in a compressed fashion, and with no repeats. de Bruijn's theorem states that U-cycles for $n$ letter words on a $k$ letter alphabet exist for all $k$ and $n$ . Much has already been proved about Universal Cycles for a variety of other objects. This work is intended to augment the current research in the area by exhibiting U-cycles for {\it complementary classes}. Results will be presented that exhibit the existence of U-cycles for class-alternating words such as alternating vowel-consonant (VCVC) words; words with at least one repeated letter (non-injective functions); words with at least one letter of the alphabet missing (functions that are not onto); words that represent illegal tournament rankings; and words that do not constitute "strong" legal computer passwords. As with previous papers pertaining to U-cycles, connectedness proves to be a nontrivial step.

preprint2013arXiv

Waiting Time Distribution for the Emergence of Superpatterns

Consider a sequence X_1, X_2,... of i.i.d. uniform random variables taking values in the alphabet set {1,2,...,d}. A k-superpattern is a realization of X_1,...,X_t that contains, as an embedded subsequence, each of the non-order-isomorphic subpatterns of length k. We focus on the non-trivial case of d=k=3 and study the waiting time distribution of tau=inf{t>=7: X_1,...,X_t is a superpattern}

preprint2012arXiv

Covering n-Permutations with (n+1)-Permutations

Let S_n be the set of all permutations on [n]:={1,2,....,n}. We denote by kappa_n the smallest cardinality of a subset A of S_{n+1} that "covers" S_n, in the sense that each pi in S_n may be found as an order-isomorphic subsequence of some pi' in A. What are general upper bounds on kappa_n? If we randomly select nu_n elements of S_{n+1}, when does the probability that they cover S_n transition from 0 to 1? Can we provide a fine-magnification analysis that provides the "probability of coverage" when nu_n is around the level given by the phase transition? In this paper we answer these questions and raise others.

preprint2012arXiv

Sharp Concentration of Hitting Size for Random Set Systems

Consider the random set system of {1,2,...,n}, where each subset in the power set is chosen independently with probability p. A set H is said to be a hitting set if it intersects each chosen set. The second moment method is used to exhibit the sharp concentration of the minimal size of H for a variety of values of p.

preprint2012arXiv

Sharp Threshold Asymptotics for the Emergence of Additive Bases

A subset A of {0,1,...,n} is said to be a 2-additive basis for {1,2,...,n} if each j in {1,2,...,n} can be written as j=x+y, x,y in A, x<=y. If we pick each integer in {0,1,...,n} independently with probability p=p_n tending to 0, thus getting a random set A, what is the probability that we have obtained a 2-additive basis? We address this question when the target sum-set is [(1-alpha)n,(1+alpha)n] (or equivalently [alpha n, (2-alpha) n]) for some 0<alpha<1. Under either model, the Stein-Chen method of Poisson approximation is used, in conjunction with Janson's inequalities, to tease out a very sharp threshold for the emergence of a 2-additive basis. Generalizations to k-additive bases are then given.

preprint2009arXiv

Universal Cycles of Restricted Classes of Words

It is well known that Universal Cycles of $k$ -letter words on an $n$ -letter alphabet exist for all $k$ and $n$ . In this paper, we prove that Universal Cycles exist for restricted classes of words, including: non-bijections, equitable words (under suitable restrictions), ranked permutations, and "passwords".

preprint2008arXiv

Competition between Discrete Random Variables, with Applications to Occupancy Problems

Consider $n$ players whose "scores" are independent and identically distributed values $\{X_i\}_{i=1}^n$ from some discrete distribution $F$ . We pay special attention to the cases where (i) $F$ is geometric with parameter $p\to0$ and (ii) $F$ is uniform on $\{1,2,...,N\}$ ; the latter case clearly corresponds to the classical occupancy problem. The quantities of interest to us are, first, the $U$ -statistic $W$ which counts the number of "ties" between pairs $i,j$ ; second, the univariate statistic $Y_r$ , which counts the number of strict $r$ -way ties between contestants, i.e., episodes of the form ${X_i}_1={X_i}_2=...={X_i}_r$ ; $X_j\ne {X_i}_1;j\ne i_1,i_2,...,i_r$ ; and, last but not least, the multivariate vector $Z_{AB}=(Y_A,Y_{A+1},...,Y_B)$ . We provide Poisson approximations for the distributions of $W$ , $Y_r$ and $Z_{AB}$ under some general conditions. New results on the joint distribution of cell counts in the occupancy problem are derived as a corollary.

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.

Anant Godbole

Research overview

Is this your work?

22 publications

Threshold Progressions in a Variety of Covering and Packing Contexts

Some Results on Superpatterns for Preferential Arrangements

The Total Acquisition Number of the Randomly Weighted Path

The Number of Seymour Vertices in Random Tournaments and Digraphs

Universal and Near-Universal Cycles of Set Partitions

Covering Array Bounds Using Analytical Techniques

Distribution of the Maximum and Minimum of a Random Number of Bounded Random Variables

On the Longest Common Pattern Contained in Two or More Random Permutations

Telescoping Sums, Permutations, and First Occurrence Distributions

The Location of the First Ascent in a 123-Avoiding Permutation

Universal and Overlap Cycles for Posets, Words, and Juggling Patterns

Bounds on the Maximum Number of Minimum Dominating Sets

Contributions to the theory of de Bruijn cycles

Maximum Number of Minimum Dominating and Minimum Total Dominating Sets

Pattern Avoidance in Ordered Set Partitions

Universal Cycles of Complementary Classes

Waiting Time Distribution for the Emergence of Superpatterns

Covering n-Permutations with (n+1)-Permutations

Sharp Concentration of Hitting Size for Random Set Systems

Sharp Threshold Asymptotics for the Emergence of Additive Bases

Universal Cycles of Restricted Classes of Words

Competition between Discrete Random Variables, with Applications to Occupancy Problems

See the researcher in context

Building this map preview