Source author record

Bobby Shen

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

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

2works

1topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

The parametric Frobenius problem and parametric exclusion

The Frobenius number of relatively prime positive integers $a_1, \ldots, a_n$ is the largest integer that is not a nononegative integer combination of the $a_i.$ Given positive integers $a_1, \ldots, a_n$ with $n \ge 2,$ the set of multiples of $\gcd(a_1, \ldots, a_n)$ which have less than $m$ distinct representations as a nonnegative integer combination of the $a_i$ is bounded above, so we define $f_{m, \ell}(a_1, \ldots, a_n)$ to be the $\ell^{\text{th}}$ largest multiple of $\gcd(a_1, \ldots, a_n)$ with less than $m$ distinct representations (which generalizes the Frobenius number) and $g_m(a_1, \ldots, a_n)$ to be the number of positive multiples of $\gcd(a_1, \ldots, a_n)$ with less than $m$ distinct representations. In the parametric Frobenius problem, the arguments are polynomials. Let $P_1, \ldots, P_n$ be integer valued polynomials of one variable which are eventually positive. We prove that $f_{m, \ell}(P_1(t), \ldots, P_n(t))$ and $g_m(P_1(t), \ldots, P_n(t)),$ as functions of $t,$ are eventually quasi-polynomial. A function $h$ is eventually quasi-polynomial if there exist $d$ and polynomials $R_0, \ldots, R_{d-1}$ such that for such that for sufficiently large integers $t,$ $h(t)=R_{t \pmod{d}}(t).$ We do so by formulating a type of parametric problem that generalizes the parametric Frobenius Problem, which we call a parametric exclusion problem. We prove that the $\ell^{\text{th}}$ largest value of some polynomial objective function, with multiplicity, for a parametric exclusion problem and the size of its feasible set are eventually quasi-polynomial functions of $t.$

preprint2011arXiv

Acyclic Subgraphs in $k$ -Majority Tournaments

A $k$ -majority digraph is a directed graph created by combining $k$ individual rankings on the same ground set to form a consensus where edges point in the direction indicated by a strict majority of the rankings. The $k$ -majority digraph is used to model voting scenarios, where the vertices correspond to options ranked by $k$ voters. When $k$ is odd, the resulting digraph is always a tournament, called $k$ -majority tournament. Let $f_k(n)$ be the minimum, over all $k$ -majority tournaments with $n$ vertices, of the maximum order of an induced transitive sub-tournament. Recently, Milans, Schreiber, and West proved that $\sqrt n \le f_3(n) \le 2 \sqrt n +1$ . In this paper, we improve the upper bound of $f_3(n)$ by showing that $f_3(n) < \sqrt {2n} +\frac 12$ .

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.

Bobby Shen

Research overview

Is this your work?

2 publications

The parametric Frobenius problem and parametric exclusion

Acyclic Subgraphs in $k$ -Majority Tournaments

See the researcher in context

Building this map preview

Bobby Shen

Research overview

Is this your work?

2 publications

The parametric Frobenius problem and parametric exclusion

Acyclic Subgraphs in kkk-Majority Tournaments

See the researcher in context

Building this map preview

Acyclic Subgraphs in $k$ -Majority Tournaments