Source author record

Anant P. 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 Data Structures and Algorithms

Catalog footprint

Research overview

13works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2013arXiv

Logarithmic Representability of Integers as k-Sums

A set A=A_{k,n} in [n]\cup{0} is said to be an additive k-basis if each element in {0,1,...,kn} can be written as a k-sum of elements of A in at least one way. Seeking multiple representations as k-sums, and given any function phi(n), with lim(phi(n))=infinity, we say that A is a truncated phi(n)-representative k-basis for [n] if for each j in [alpha n, (k-alpha)n] the number of ways that j can be represented as a k-sum of elements of A_{k,n} is Theta(phi(n)). In this paper, we follow tradition and focus on the case phi(n)=log n, and show that a randomly selected set in an appropriate probability space is a truncated log-representative basis with probability that tends to one as n tends to infinity. This result is a finite version of a result proved by Erdos (1956) and extended by Erdos and Tetali (1990).

preprint2013arXiv

Shattering Thresholds for Random Systems of Sets, Words, and Permutations

This paper considers a problem that relates to the theories of covering arrays, permutation patterns, Vapnik-Chervonenkis (VC) classes, and probability thresholds. Specifically, we want to find the number of subsets of [n]:={1,2,....,n} we need to randomly select, in a certain probability space, so as to respectively "shatter" all t-subsets of [n]. Moving from subsets to words, we ask for the number of n-letter words on a q-letter alphabet that are needed to shatter all t-subwords of the q^n words of length n. Finally, we explore the number of random permutations of [n] needed to shatter (specializing to t=3), all length 3 permutation patterns in specified positions. We uncover a very sharp zero-one probability threshold for the emergence of such shattering; Talagrand's isoperimetric inequality in product spaces is used as a key tool.

preprint2010arXiv

$t$ -Covering Arrays Generated by a Tiling Probability Model

A $t-\a$ covering array is an $m\times n$ matrix, with entries from an alphabet of size $α$ , such that for any choice of $t$ rows, and any ordered string of $t$ letters of the alphabet, there exists a column such that the "values" of the rows in that column match those of the string of letters. We use the Lovász Local Lemma in conjunction with a new tiling-based probability model to improve the upper bound on the smallest number of columns $N=N(m,t,α)$ of a $t-\a$ covering array.

preprint2010arXiv

Maximal Symmetric Difference-Free Families of Subsets of $[n]$

Union-free families of subsets of $[n]=\{1,... n\}$ have been studied in \cite{FF}. In this paper, we provide a complete characterization of maximal {\it symmetric difference}-free families of subsets of $[n]$ .

preprint2010arXiv

Omnimosaics

An {\it omnimosaic} $O(n,k,a)$ is defined to be an $n\times n$ matrix, with entries from the set ${\cal A}=\{1,2,\...,a\}$ , that contains, as a submatrix, each of the $a^{k^2}$ $k\times k$ matrices over ${\cal A}$ . We provide constructions of omnimosaics and show that for fixed $a$ the smallest possible size $ω(k,a)$ of an $O(n,k,a)$ omnimosaic satisfies $\frac{ka^{k/2}}{e}\le ω(k,a)\le \frac{ka^{k/2}}{e}(1+o(1))$ for a well-specified function $o(1)$ that tends to zero as $k\to\infty$ .

preprint2010arXiv

On Universal Cycles for new Classes of Combinatorial Structures

A universal cycle (u-cycle) is a compact listing of a collection of combinatorial objects. In this paper, we use natural encodings of these objects to show the existence of u-cycles for collections of subsets, matroids, restricted multisets, chains of subsets, multichains, and lattice paths. For subsets, we show that a u-cycle exists for the $k$ -subsets of an $n$ -set if we let $k$ vary in a non zero length interval. We use this result to construct a "covering" of length $(1+o(1))$ $n \choose k$ for all subsets of $[n]$ of size exactly $k$ with a specific formula for the $o(1)$ term. We also show that u-cycles exist for all $n$ -length words over some alphabet $Σ,$ which contain all characters from $R \subset Σ.$ Using this result we provide u-cycles for encodings of Sperner families of size 2 and proper chains of subsets.

preprint2009arXiv

Omnibus Sequences, Coupon Collection, and Missing Word Counts

An {\it Omnibus Sequence} of length $n$ is one that has each possible "message" of length $k$ embedded in it as a subsequence. We study various properties of Omnibus Sequences in this paper, making connections, whenever possible, to the classical coupon collector problem.

preprint2008arXiv

The Lexicographic First Occurrence of a I-II-III pattern

Consider a random permutation $π\in{\cal S}_n$ . In this paper, perhaps best classified as a contribution to discrete probability distribution theory, we study the {\it first} occurrence $X=X_n$ of a I-II-III-pattern, where "first" is interpreted in the lexicographic order induced by the 3-subsets of $[n]=\{1,2,...,n\}$ . Of course if the permutation is I-II-III-avoiding then the first I-II-III-pattern never occurs, and thus $\e(X)=\infty$ for each $n$ ; to avoid this case, we also study the first occurrence of a I-II-III-pattern given a bijection $f:{\bf Z}^+\to{\bf Z}^+$ .

preprint2008arXiv

Universal Cycles of Discrete Functions

A connected digraph in which the in-degree of any vertex equals its out-degree is Eulerian; this baseline result is used as the basis of existence proofs for universal cycles (also known as deBruijn cycles or $U$ -cycles) of several combinatorial objects. We present new results on the existence of universal cycles of certain classes of functions. These include onto functions, and 1-inequitable sequences on a binary alphabet. In each case the connectedness of the underlying graph is the non-trivial aspect to be established.

preprint2005arXiv

Improved Pebbling Bounds

Consider a configuration of pebbles distributed on the vertices of a connected graph of order $n$ . A pebbling step consists of removing two pebbles from a given vertex and placing one pebble on an adjacent vertex. A distribution of pebbles on a graph is called solvable if it is possible to place a pebble on any given vertex using a sequence of pebbling steps. The pebbling number of a graph, denoted $f(G)$ , is the minimal number of pebbles such that every configuration of $f(G)$ pebbles on $G$ is solvable. We derive several general upper bounds on the pebbling number, improving previous results.

preprint2005arXiv

Partial covering arrays and a generalized Erdos-Ko-Rado property

The classical Erd\H os-Ko-Rado theorem states that if $k\le\floor{n/2}$ then the largest family of pairwise intersecting $k$ -subsets of $[n]=\{0,1,...,n\}$ is of size ${{n-1}\choose{k-1}}$ . A family of $k$ subsets satisfying this pairwise intersecting property is called an EKR family. We generalize the EKR property and provide asymptotic lower bounds on the size of the largest family ${\cal A}$ of $k$ -subsets of $[n]$ that satisfies the following property: For each $A,B,C\in{\cal A}$ , each of the four sets $A\cap B\cap C;A\cap B\cap C^C; A\cap B^C\cap C; A^C\cap B\cap C$ are non-empty. This generalized EKR (GEKR) property is motivated, generalizations are suggested, and a comparison is made with fixed weight 3-covering arrays. Our techniques are probabilistic.

preprint2005arXiv

Probabilistic Extensions of the Erd\H os-Ko-Rado Property

The classical Erd\H os-Ko-Rado (EKR) Theorem states that if we choose a family of subsets, each of size (k), from a fixed set of size (n (n > 2k)), then the largest possible pairwise intersecting family has size (t ={n-1\choose k-1}). We consider the probability that a randomly selected family of size (t=t_n) has the EKR property (pairwise nonempty intersection) as $n$ and $k=k_n$ tend to infinity, the latter at a specific rate. As $t$ gets large, the EKR property is less likely to occur, while as $t$ gets smaller, the EKR property is satisfied with high probability. We derive the threshold value for $t$ using Janson's inequality. Using the Stein-Chen method we show that the distribution of $X_0$ , defined as the number of disjoint pairs of subsets in our family, can be approximated by a Poisson distribution. We extend our results to yield similar conclusions for $X_i$ , the number of pairs of subsets that overlap in exactly $i$ elements. Finally, we show that the joint distribution $(X_0, X_1, ..., X_b)$ can be approximated by a multidimensional Poisson vector with independent components.

preprint2005arXiv

Sierpi\' nski Gasket Graphs and Some of Their Properties

The {\it Sierpiński fractal} or {\it Sierpiński gasket} $Σ$ is a familiar object studied by specialists in dynamical systems and probability. In this paper, we consider a graph $S_n$ derived from the first $n$ iterations of the process that leads to $Σ$ , and study some of its properties, including its cycle structure, domination number and pebbling number. Various open questions are posed.

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 P. Godbole

Research overview

Is this your work?

13 publications

Logarithmic Representability of Integers as k-Sums

Shattering Thresholds for Random Systems of Sets, Words, and Permutations

$t$ -Covering Arrays Generated by a Tiling Probability Model

Maximal Symmetric Difference-Free Families of Subsets of $[n]$

Omnimosaics

On Universal Cycles for new Classes of Combinatorial Structures

Omnibus Sequences, Coupon Collection, and Missing Word Counts

The Lexicographic First Occurrence of a I-II-III pattern

Universal Cycles of Discrete Functions

Improved Pebbling Bounds

Partial covering arrays and a generalized Erdos-Ko-Rado property

Probabilistic Extensions of the Erd\H os-Ko-Rado Property

Sierpi\' nski Gasket Graphs and Some of Their Properties

See the researcher in context

Building this map preview

Anant P. Godbole

Research overview

Is this your work?

13 publications

Logarithmic Representability of Integers as k-Sums

Shattering Thresholds for Random Systems of Sets, Words, and Permutations

ttt-Covering Arrays Generated by a Tiling Probability Model

Maximal Symmetric Difference-Free Families of Subsets of [n][n][n]

Omnimosaics

On Universal Cycles for new Classes of Combinatorial Structures

Omnibus Sequences, Coupon Collection, and Missing Word Counts

The Lexicographic First Occurrence of a I-II-III pattern

Universal Cycles of Discrete Functions

Improved Pebbling Bounds

Partial covering arrays and a generalized Erdos-Ko-Rado property

Probabilistic Extensions of the Erd\H os-Ko-Rado Property

Sierpi\' nski Gasket Graphs and Some of Their Properties

See the researcher in context

Building this map preview

$t$ -Covering Arrays Generated by a Tiling Probability Model

Maximal Symmetric Difference-Free Families of Subsets of $[n]$