The discrete-mathematics tag has no usage guidance.

**6**

votes

**0**answers

738 views

### How many 2L-bit numbers are the product of two L-bit numbers?

If I multiply two integers $x, y $ in $[0,2^L)$, I get an integer in $[0,2^{2L})$. Clearly, this map from $[0,2^L) \times [0,2^L) \to [0,2^{2L})$ is not bijective.
I am interested in the size of ...

**5**

votes

**0**answers

84 views

### Diameter of the modified bubble-sort graph

The modified bubble-sort graph is the Cayley graph $Cay(S_n,S)$ of $S_n$ generated by $n$ cyclically adjacent transpositions. Thus $S = \{ (1,2),(2,3),\ldots,(n,1)\}$. I was wondering whether the ...

**5**

votes

**0**answers

522 views

### Optimal Gear Trains

Suppose you need to slow down a turning motor so that a gear turns at
an angular velocity $\frac{a}{b}$ of that of the motor shaft, where $a$ and
$b$ are natural numbers. For example, this set of ...

**5**

votes

**0**answers

805 views

### On “The Average Height of Planted Plane Trees” by Knuth, de Bruijn and Rice (1972)

I am trying to derive the classic paper in the title only by elementary means (no generating functions, no complex analysis, no Fourier analysis) although with much less precision. In short, I "only" ...

**4**

votes

**0**answers

221 views

### Domination in Nice Lattices

Let an integer vector be nice when it has only two nonzero components, which sum to zero. So (0, 0, 3, 0, -3) and (-1, 0, 1, 0, 0) are examples of nice vectors in $n=5$ dimensions.
Call a lattice ...

**3**

votes

**0**answers

117 views

### Generating function of a sequence involving reciprocals of binomial coefficients

Question: Is there a closed-form expression for the following sum
$$
F(z,k,r)=\sum_{n=0}^{r} \frac{z^n}{{n+k} \choose {k}}\label{sum}\tag{1}
$$
where $z\in\mathbb{C}$, and $r$, $k$ are non-negative ...

**3**

votes

**0**answers

61 views

### What is the maximal number of partitions with this maximal intersection property?

Let $X = \{ 1, \dots, n = sk \}$ be a finite set. Let $\mathscr P, \mathscr Q$ be equi-partitions of $X$ into $k$ sets of size $s$. Denote by $V(\mathscr P, \mathscr Q)$ the maximum size of ...

**3**

votes

**0**answers

102 views

### “Standard” notation for symmetric functions?

Here is what I encountered in the paper "The Optimal Lattice Quantizer in Three dimensions" by Barnes and Sloane.
Here is the setup:
Let $\Lambda$ be a lattice in $\mathbb{R}^3$. Around each ...

**3**

votes

**0**answers

127 views

### Citation for subset complement result

Let $S=\lbrace s_1,\ldots,s_n \rbrace \subset \lbrace1,\ldots,2n\rbrace$. Consider two operations on $S$: the complement $C(S)=\lbrace 1,\ldots,2n \rbrace \setminus S$ and a reflection* ...

**3**

votes

**0**answers

122 views

### Are there existing resources on modular-esque recurrence relations?

Does anyone know where I would be able to get information on analyzing a class of polynomial recurrence relations of a form like this?
$\begin{align*}
f_{n,k}(x) & ...

**3**

votes

**0**answers

135 views

### A fast way to test whether a partial function can be extended to a chirotope of rank 3 ?

Hello,
What is a fast way to test whether a partial function can be extended to a chirotope of rank 3 ? That is: I have a domain
$E = \{1,...,n\}$
and a partial function
$f: E^3 \to \{-1, 0, 1\}$
...

**3**

votes

**0**answers

748 views

### Method for variable substitution in multiple summation

I want to ask: is there any general method for variable substitution in multiple summation?
For example in the following equation a new variable $\lambda=n+m-2\mu$ is introduced to transform the LHS ...

**2**

votes

**0**answers

95 views

### What kinds of complexes can be collapsed to?

A simplicial complex $S$ is collapsible if there is a sequence of elementary collapses that bring $S$ down to a single point; I'll denote this as $S \searrow \{pt\}$. I am wondering about a similar ...

**2**

votes

**0**answers

44 views

### A weaker version of Randell Isotopy Theorem

I am studying a problem in hyperplane arrangement theory related to the homotopy type of the complement manifold of a certain class of hyperplane arrangements.
In a well celebrated paper Richard ...

**2**

votes

**0**answers

473 views

### Guessing game with guess cost

This is a question about Problem 328 on the website Project Euler. A description of the problem is provided in the previous link. I was wondering if there has been any research done on this question. ...

**2**

votes

**0**answers

180 views

### Number of breakpoints in parametric maximum flow problems

The parametric maximum flow problem can be formulated as
$$f(\lambda) = \min_{x\in\{0,1\}^n} \left( \sum_{i}(a_i + b_i\lambda)x_i + \sum_{i,j}c_{ij}x_ix_j \right),
$$
where all $c_{ij}<0$ (so that ...

**1**

vote

**0**answers

9 views

### Factoring a multiset into a product of two multisets

Given a multiset $S$ of $mn$ numbers, how hard is to find multisets $A$ and $B$, of $m$ and $n$ numbers respectively, such that
$$ S = \{ xy \mid x\in A, y\in B \}~~~~\text{(multiset sense)}, $$
or ...

**1**

vote

**0**answers

23 views

### Some confusion regarding the definition of NPO reduction

I've seen the following definition in a paper on approximation preserving reductions.
Definition:Let $\pi_{1}$ and $\pi_{2}$ be two NPO maximization problems. Then we say that $\pi_{1} \leq_{R} ...

**1**

vote

**0**answers

54 views

### Building an orthogonal embedding for a 4-planar graph

I'm interested in the following paper http://www.computer.org/csdl/trans/tc/1981/02/06312176.pdf
In particular i'm interested in the construction Valiant describes to prove that it is possible to ...

**1**

vote

**0**answers

65 views

### Presentation of the Rybnikov matroid

In this well celebrated work Gregory Rybnikov exhibit an example of two arrangements with the same underlying matroid, but with fundamental groups which are not isomorphic. This is a key ...

**1**

vote

**0**answers

37 views

### Estimates for derivatives of a positive discrete harmonic function

There is the following estimation (Duffin, Discrete potential theory, Theorem 5):
Let $f$ be a discrete harmonic function in a sphere of radius $R$ with the center $p$, all in $\mathbb Z^3$. Then, if ...

**1**

vote

**0**answers

44 views

### Simplifying closed form for Meta Operator

I was consider the set of linear operators:
$$O_{a,k} = \frac{f(ax^k) - f(x)}{ax^k - x} $$'
Particularly I am looking for the closed forms of the eigenfunctions of this operator, that is the ...

**1**

vote

**0**answers

88 views

### Cross-correlation of two functions which are not fixed

I am trying to cross-correlate two functions, but one of which is changing each 'step' of the cross-correlation.
I want to cross-correlate T(f) and ...

**1**

vote

**0**answers

211 views

### Trigonometric semialgebraic conditions for two floors to be unequal [edited]

EDIT: Since posting my original question I have simplified the problem to finding a sufficient condition for $\lfloor \frac{a}{\phi}\rfloor \neq \lfloor \frac{b}{\phi}\rfloor$ which is trigonometric ...

**1**

vote

**0**answers

170 views

### recursion formula for odd holonomic function

suppose we have a map
$f:\mathbb{Z}\longrightarrow\mathbb{C}[t^{\pm}]$
with property that $f(i)=-f(-i)$.
The algebra
$\mathcal{T}=\mathbb{C}[t^{\pm}][L^{\pm},M^{\pm}]/[LM=tML]$ acts on $f$ by
...

**1**

vote

**0**answers

433 views

### Zeroes of a tricky function.

I am attempting to show that there does not exist an N past which every open unit interval (k, k+1) -where k is an integer- contains a zero of the following function:
$h(x)=\sum_{n=2}^{[\sqrt(x)]} ...

**0**

votes

**0**answers

10 views

### Approximation preserving reductions

I've seen in the following document
https://hal.archives-ouvertes.fr/hal-00958028/document
A definition of the $\leq_{S}$ reduction defined specifically for minimisation problems at the bottom of ...

**0**

votes

**0**answers

50 views

### Question on abstract polytopes

Let $(P,\le)$ be an abstract $n$-polytope, with $n\ge 2$. Let $H,H',K$ be $m$-faces, with $0\le m \le n-2$. Is it true that there is a sequence $\{H_0=H,H_1,...,H_{r-1},H_r=H' \} \subseteq P$ so that ...

**0**

votes

**0**answers

8 views

### Maximization the difference of a monotone submodular function and a linear function with a cardinality constraint

Maximizing a monotone submodular function with a cardinality constraint can be solved by using a simple greedy heuristic. However, if the submodular function is non-monotone, the greedy heuristic can ...

**0**

votes

**0**answers

56 views

### Factorial Sums over Compositions or ``Unlabeled Permutations"

Let $C_n$ denote subset of integer compositions of $n$ and $c=(c_1,c_2,\dots c_n)$
In a divergent sum, the sequence
$$
a_n=\sum_{c\in C_n} \prod_{c_i\in c} c_i!
$$
frequently shows up and one ...

**0**

votes

**0**answers

75 views

### Summing up costs over a Markov chain

I apologize in advance if this question is too simplistic to be appropriate for MathOverflow. I have inquired in multiple places but have found little to indicate that this is a previously studied ...

**0**

votes

**0**answers

35 views

### On the stability analysis of a discrete difference system with multiplicative noise

If we assume that
\begin{equation*}
\rho \{\phi \otimes \phi+\psi \otimes \psi\}<1,
\end{equation*}
where $\rho$ denotes the spectral radius, then can we verify that the following inequality ...

**0**

votes

**0**answers

169 views

### Lattice basis reductions and finding minimal values

While reading several articles about lattice basis reduction I am left with a few questions.
For one, I came across this piece of text
Let $\alpha$ and $\beta \in \mathbb{R}$. Also let $X>0$ and ...

**0**

votes

**0**answers

133 views

### A good upper bound on the size of k-biclique in random bipartite graphs.

Let $G = (X \cup Y, E)$ be a random bipartite graph, where $X$ and $Y$ are the set of vertices and $E$ the set of edges. I want to find an upper bound of the largest biclique in which exactly $k$ ...

**0**

votes

**0**answers

85 views

### An upperbound related to inductively reducing a set by adding the two least elements

I hope this is not too trivial to be asked here, but here it goes anyway. This is just out of curiosity (regarding a problem with graphs but I have "reduced" it to the problem below:)
Let ...

**0**

votes

**0**answers

224 views

### Partial Recurrence Equation

Hey people
I have the following equation, which I don't manage to solve.
The background of the problem is the clustergrowth of two chemical species, resulting in a final relation I'd like to solve:
...