# Questions tagged [discrete-mathematics]

Deprecated; do NOT use this tag. Instead you might use co.combinatorics or various more specific tags.

**0**

votes

**1**answer

353 views

### “Mathematics is the science of the infinite” [closed]

The title is the first sentence of Hermann Weyl's 1930 essay,
"Levels of Infinity."
He focuses on
"the distinction between actuality and potentiality, between
Being and Possibility."
He opines
...

**54**

votes

**19**answers

8k views

### When has discrete understanding preceded continuous?

From my limited perspective, it appears that the understanding
of a mathematical phenomenon has usually been achieved,
historically, in a continuous setting
before it was fully explored in a discrete ...

**6**

votes

**0**answers

109 views

### Random Balanced Assignment

A balanced assignment from from $N$ objects to $K$ classes is a mapping $\sigma\colon \{ 1, \ldots, N\} \rightarrow \{ 1, \ldots, K\}$ such that
$$
\textrm{Card}( \sigma^{-1} \{j \} ) = \textrm{Card} ...

**2**

votes

**1**answer

105 views

### Connection between graph spectra and graph homomorphisms [closed]

Since there are many properties of graph which can be expressed in terms of both existence of graph homomorphisms and graph spectra I expect there are some papers exploring this connection between ...

**9**

votes

**2**answers

1k views

### Approximation of sum of the first binomial coefficients for fixed N

I'd like to compute $\sum_{i=0}^k {{N}\choose{i}}$. Is there a computable approximation for that?

**5**

votes

**2**answers

136 views

### An interesting variant on the maximum independent set problem.

Suppose i have a graph $G=(V,E)$ with $|V|=n$. Furthermore suppose i give you a maximum independent set $\mathcal{I}$ in $G$. Now suppose i obtain a new graph $G'$ from $G$ by removing a single vertex ...

**0**

votes

**0**answers

103 views

### Simple automorphisms of finite relations

Finding automorphisms is a hard problem in general, but I am studying some simple subgroups of automorphisms, which are easy to find.
I have some r-ary relation R on a finite set U (if it was a ...

**6**

votes

**1**answer

192 views

### counting monomials and integrality

For $n\in\mathbb{Z}^{+}$, consider the polynomials
$$P_n(x)=\prod_{k=0}^{n-1}(x^n-x^k).$$
QUESTION. Is it possible to find a closed formula for the number of monomials in $P_n(x)$, after expansion?
...

**-3**

votes

**1**answer

166 views

### why do the Computability theory choose the natural number as the object of study? [closed]

I am wondering why the computable function is defined in the natural number set.Can people giveme the answer or some resources that can solve my puzzle.

**2**

votes

**0**answers

68 views

### Sequence of formulae and limit objects

Let $(G_i,x_i)$ be a sequence of rooted graphs that we can assume to have uniformly bounded (finite) maximum degrees, and let $P_i$ be a sequence of first order formulae (in the language of graph ...

**3**

votes

**0**answers

141 views

### asymptotics of the largest real root

Suppose you have a family of polynomials
$$P_n(x)=\sum_{k=0}^n(-1)^ka_k^{(n)}x^k$$
for $n=0,1,2,\dots$.
Further assumptions:
(1) the coefficients $a_k^{(n)}$ are recursively related to the $a_j^{(n-1)...

**2**

votes

**0**answers

59 views

### A question related to Boolean functions? [closed]

Let $Z_2=\{0,1\}$, $Z_2^r=Z_2\times Z_2 \times...\times Z_2,$ $S_1\subset Z_2^{n_1}$ and $S_2\subset Z_2^{n_2}$, $S=(S_2,S_1)\subset Z_2^{n_1+n_2}$, I'd like to construct $S_1$ and $S_2$ s.t the ...

**10**

votes

**2**answers

274 views

### Whether a total order set of size $n$ has the fewest endomorphisms among posets of size $n$

A function $f: P \to P$ is an endomorphism iff for any $x \le y$ in the poset $P$ , $f(x) \le f(y)$. So among posets of size $n$, whether the total order set $[n]$ (with the usual ordering) has the ...

**4**

votes

**2**answers

121 views

### Size of biggest mutually 0-1 string with odd mutual 1

Let $q$ be an odd number...
consider $0-1$ strings of length $2q$ with $q$ ones. [with total number of $C(2q,q)$]
I want to find an upper bound for a set of these strings such that the number of ...

**1**

vote

**0**answers

87 views

### Discrete Calderon-Zygmund operators

I would like to know whether there exists a Calderon-Zygmund theory discrete singular kernels. In particular I am interested when the discrete operator $T$ with kernel $K(n,m)$ given by
$$(Tf)(n)=\...

**0**

votes

**0**answers

115 views

### How does the Zipf parameter affect its PMF and CDF?

For a Zipf distribution, the PMF and the CDF are $f(k,\alpha,N)=\frac{1/k^\alpha}{\sum_{n=1}^N (1/n^\alpha)}$ and $F(k,\alpha,N)=\frac{\sum_{n=1}^k (1/n^\alpha)}{\sum_{n=1}^N (1/n^\alpha)}$, ...

**4**

votes

**0**answers

99 views

### Level sets of function of inner products of vectors on hypercube

Let $H = \{ 0, 1\}^d$ be the $d$-th Cartesian product of $\{0, 1\}$ in $\mathbb{R}^d$. Suppose $v_1, \ldots, v_k$ are $k$ vectors in $H$ in general position. We define function $F \colon H^{k}\...

**2**

votes

**1**answer

268 views

### Number of subsets that sum to $0$

Suppose you choose $n$ distinct random numbers from a contiguous subset of cardinality $f({\beta, n})$ with at least $f({\alpha_+, n})$ positive and at least $f({\alpha_-, n})$ negative values from a ...

**2**

votes

**1**answer

115 views

### Calculating greatest common divisor series [closed]

How to compute the value of [G(1,x)+G(2,x)+G(3,x)+....+G(x,x)] efficiently?
When x can be as large as million.G = greatest common divisor.

**1**

vote

**0**answers

45 views

### Separation on discrete set

Consider the set $L = \prod_{i=1}^n\{1,0\}$, i.e. L consists of the element of n-tuples whose entries are 0 or 1. Also we can regard $L$ as a subset of $R^n$.
Define linear functions $f(x)= a_1x_1+ \...

**1**

vote

**0**answers

117 views

### bounded degree graph colouring.

I was wondering if anyone could provide references on the following:
Is determining the chromatic number of a bounded degree graph APX-complete?
2.I've seen the result that states it is NP-hard to ...

**3**

votes

**0**answers

105 views

### Hypergraph edge colouring

I'm interested in knowing if finding the edge-chromatic number of a $k$-uniform $k$-partite hypergraph is NP-hard for $k\geq 3$ Could anyone provide a reference for the result? By edge-chromatic ...

**4**

votes

**1**answer

71 views

### Separate a special poset by function

Assume $A = \prod_{i=1}^n\{0,1\}$, i.e. element $(a_1,\cdots,a_n)=a\in A$ is n-tuples like $(1,0,1,\cdots)$.
There is an obvious partial order on the $A$: say $a < b$ for $a,b\in A$ if and only ...

**4**

votes

**0**answers

204 views

### The properties of Pos

Given $n\in\mathbb{N}$, and $f:\mathbb{N}^*\rightarrow \mathbb{N}$, let define $Pos$ as:
$$Pos(f)(n)= |\{x \leq n, f(x)=f(n)\}|$$
When given $n\in\mathbb{N}$, this function gives the 'position' of $...

**4**

votes

**3**answers

259 views

### Relation between diametral path and regularity of a graph

Let $G(V,E)$ be a graph. A path whose length is equal to the diameter of a graph is called a diametral path. In a cycle graph every vertex has $2$ diametral paths. Now I need to prove that this:
If ...

**1**

vote

**0**answers

74 views

### Discrete Mathematics Uses [closed]

I am trying to explain how and why discrete maths is used in areas such as programming, correctness, data types, state transistion and conditionals. I'm having a really hard time articulating it ...

**3**

votes

**0**answers

115 views

### Growth of inner products between two random vectors on the sparse hypercube

We define the $s$-sparse hypercube in $\mathbb{R}^d$ as
\begin{align}
\mathbb{H}_s = \bigl \{ {\bf{v}} \in \{ -1, 0 , 1\}^d \colon \| {\bf{v}} \|_0 = s \bigr\},
\end{align}
where $ \| {\bf v} \|_0 $ ...

**2**

votes

**0**answers

61 views

### What do you call the collection of all sets shattered by $F$?

The proof of Pajor's lemma uses the collection of all sets $S\subseteq X$ shattered by some $F\subseteq 2^X$. Is there a standard term for the former object? I've been privately referring to it as the ...

**11**

votes

**1**answer

261 views

### Generating function of a sequence is not algebraic

Let we have a sequence $\{a_{n}\}$, such that $\forall n \,\, a_{n}>0$ and $a_{n} \rightarrow\infty, n\rightarrow\infty$. Also let's suppose that we have a subsequence $\{a_{n_{k}}\}$ such that $\...

**1**

vote

**1**answer

156 views

### Building the string on $\{0,1\}$ alphabet with $\Omega(n^{2})$ different substrings [closed]

As we know the number of different substrings has the upper bound $O(n^{2})$.
Consider the strings on $\{0,1\}$ alphabet. Can I build a string with $\Omega(n^{2})$ different substrings?
Actually I ...

**0**

votes

**0**answers

56 views

### Approximation to colouring for bounded degree graphs

I have already asked one question on colouring, this question is more specific.
Given a bounded degree graph $G$ with $\Delta(G)=2d$, is there a well know algorithm to achieve an approximation ratio ...

**1**

vote

**1**answer

102 views

### Graph colouring for bounded degree graphs

I'm fairly new to colourings on bounded degree graphs i'm interested in the following questions,
For planar graphs with bounded degree $4$ is finding the colouring number $NP$-hard? So is ...

**4**

votes

**0**answers

199 views

### Find the number of boolean functions of n variable that satisfy the following condition

For how many boolean functions is this true? The length of the shortest disjunctive normal form of that functions is equal to 2^(n-1). And the the number of variable entries in the minimal dnf of that ...

**2**

votes

**1**answer

71 views

### Directed edge-colouring

I'm interested to know whether the following problem is NP-complete or if there is an algorithm to solve it.
Suppose we are given a directed graph $G=(V,E^{\rightarrow})$ and we want to colour the ...

**1**

vote

**0**answers

48 views

### Is the complement of a vertex figure in an (abstract) polytope connected?

I consider an (abstract) regular polytope $P$, and $H$ a vertex figure of $P$. Is the complement $P \setminus H$ connected (as a poset, in the sense that its Hasse diagram, ignoring the improper faces,...

**8**

votes

**1**answer

196 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

31 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} \pi_{...

**2**

votes

**1**answer

96 views

### Orthogonal embeddings and edge lengths

I'm interested in orthogonal embeddings of graphs into the 2-dimensional, i.e where vertices are placed at integer co-ordinates and edges are routed along the grid lines and are not allowed to ...

**1**

vote

**1**answer

550 views

### Determinant of discrete Laplacian

It can easy be shown by induction that the determinant of the $(N-1)\times (N-1)$ matrix
$$\begin{pmatrix}
2 & -1 & & \\
-1 & 2 & \ddots & \\
& \...

**1**

vote

**0**answers

93 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

45 views

### Maximization of 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 ...

**2**

votes

**1**answer

235 views

### Alternating sign binomial identity [closed]

I recently noticed that for a triple of integers $k \geq 2$, $k \geq m \geq t \geq 1$, the following identity seems to hold
$\sum_{j=0}^{m-t} (-1)^{m-t-j}{k \choose j}{m-1-j \choose t-1}={k-t \choose ...

**5**

votes

**4**answers

244 views

### Selecting subsets with size $\frac{n}{2}$ covering every pair of the elements

Given a set $S$ of $n$ elements. Let $T$ be the set of all subsets of $S$, with size $\frac{n}{2}$ ($n$ is even). We want to select a subset $T'$ of $T$, with the property that for any pair of the ...

**2**

votes

**3**answers

2k views

### An identity involving a product of two binomial coefficients

I'm trying to find a closed formula (in the parameters $q,N$) for the following sum:
$$ \sum_{k=q}^{N} {{k-1}\choose{q-1}} {{k}\choose {q}} $$
Can anybody give me a lead?
Lior

**4**

votes

**1**answer

352 views

### Number of different positions of rooks on chessboard

I know that this topic as been mentioned before, but no accurate answer has been provided.
Suppose we have to place $n$ rooks on $n \times n$ chessboard so that no one attacks another. How to count ...

**5**

votes

**1**answer

190 views

### Intersection of rotating regular polygons

This question has a recreational flavor, but may not be
entirely uninteresting.
Let $P_k$ be a unit-radius regular polygon of $k$ sides,
and $P_n$ a unit-radius regular polygon of $n \ge k$ sides.
...

**1**

vote

**1**answer

159 views

### Discrete summation of Gaussian functions. Decay time problem

I am facing the following problem. I have a function which is defined through a discrete sum of Gaussians
$$F_M(t) = 2\sum\limits_{n=1}^{M}e^{-t^2 \sigma^2 n^2}\times \sum\limits_{k=n}^{M}p_k p_{k-n} +...

**5**

votes

**3**answers

423 views

### Fundamental solution of Discrete Laplace in the plane

We consider a discretization of the Laplace operator on $\mathbb Z^2$, https://en.wikipedia.org/wiki/Discrete_Laplace_operator
Then, it is natural to consider its fundamental solution $u$, i.e. $|u(x)...

**1**

vote

**0**answers

81 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

214 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 ...