Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [discrete-mathematics]

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

0
votes
1answer
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
19answers
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
0answers
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
1answer
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
2answers
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
2answers
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
2answers
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
2answers
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
3answers
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
4answers
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
3answers
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
1answer
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
1answer
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
1answer
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
3answers
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
0answers
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
0answers
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 ...