# Questions tagged [discrete-mathematics]

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

170 questions
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 ...
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 ...
109 views

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)}$, ...
99 views

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 ...
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 ...
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 ...
204 views

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 ...
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 ...
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 ...
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 ...
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 ...
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,...
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 ...
31 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 ...