The discrete-mathematics tag has no wiki summary.

**12**

votes

**1**answer

169 views

### Is there an unambiguous CFL whose complement is not context-free?

I'm doing a little bit of research about context-free languages. A question that's popped up is whether or not there exists an unambiguous context-free language whose complement is not a context-free ...

**0**

votes

**1**answer

253 views

### Probability generating function zero implies random variable is infinite

Let $V$ be a random variable supported on the nonnegative integers (including $\infty$) and $f(x) = \mathbf E x^V$ be the probability generating function. In our model $V$ is the number of visits to ...

**6**

votes

**1**answer

252 views

### A variation on Bulgarian solitare

It appears that a variation on Bulgarian solitare has a fixed point regardless
of the starting $n$.
For example, let $n=69$, and consider this partition:
$$
(8,8,7,7,5,5,5,5,5,4,3,3,2,2)
$$
In ...

**0**

votes

**1**answer

78 views

### Probability of k overlapping subsets in N trials

Ok, here is what I am attempting to find an answer to:
I draw M uniformly random subsets of size K from the set of numbers $\Omega=\{1, \dots, N\}$ (where uniformly random means that each unique ...

**0**

votes

**1**answer

236 views

### Indexing combinations with repetition

Let $\Sigma$ be a finite set of symbols with total order. Let $C_k$ be the set of all $k$-multiset (unordered collection of $k$ elements from $S$, with repetition allowed). We can order all the ...

**1**

vote

**0**answers

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

**0**

votes

**4**answers

111 views

### about the structure of components of tensor product if more than one bipartite graph is taken

I was reading about tensor product of graphs. We know that if we take tensor product of n graphs and want this product to be a connected graph then at most one graph should be bipartite. In the book ...

**33**

votes

**6**answers

2k views

### Is it easy to produce hard-to-color graphs?

This question arises from my recent visit to my daughter's second-grade class, where I led some discussion and activities on graph coloring (see Math for seven-year-olds). In one such activity, each ...

**0**

votes

**0**answers

73 views

### Rank function and closure operator for a set system

I would like to trace the concepts "rank function" and "closure operator" back to some structures as primitive as possible.
For a set system $(E,F)$ which is an independence system or a greedoid, I ...

**11**

votes

**1**answer

313 views

### Longest of random worm-like paths in $\mathbb{Z}^2$

Imagine at each lattice point of $\mathbb{Z}^2$ within $[1,3n]^2$,
with coordinates
$\equiv 2 \mod 3$,
we place, with equal probability, one of these six patterns:
The result ...

**1**

vote

**0**answers

34 views

### Find a common expression (parameterized by y = 1/2, 1 and 2) uniting three (rational) polynomials in k [closed]

I am seeking a common "simple" expression (preferably/presumably a sum of products of linear factors, or sum of products of low-degree factors) uniting the three polynomials (parameterized by ...

**1**

vote

**1**answer

127 views

### Calculate the discrete set of points B which are in the convex hull of the set of points A

This problem is likely best described with the following picture:
Given the discrete set of points $A$ (shown in blue), I wish to calculate the discrete set of points that are contained within the ...

**1**

vote

**1**answer

170 views

### A square-squareroot integer race sequence involving primes

I wonder what is the expected behavior of this process?
Let
$f^2_{\mathrm{next}}(n) =$ the next prime after $n^2$.
$g_{\mathrm{sqrt}}(n) = \lfloor \sqrt{n} \rfloor$.
Now iterate as ...

**11**

votes

**0**answers

250 views

### Generating random finite groups

I would like a method to efficiently generate a random finite group of a given order $n$.
If there are $g(n)$ non-isomorphic groups of order $n$,
ideally each group would occur with probability ...

**7**

votes

**1**answer

342 views

### Is this a new formula? $\Delta^d x^n/d! = \sum_k \left[ x \atop k\right]{ k+n \brace x + d}(-1)^{x+k}$

$$\frac{\Delta^d x^n}{d!} = \sum_k \left[ x \atop k\right]{ k+n \brace x + d}(-1)^{x+k}$$
Where $x$, $n$ and $d$ are non-negative integers, $\Delta^d$ is the $d$-th difference with respect to ...

**7**

votes

**2**answers

277 views

### Iteration of a 2D map involving absolute value: phase transition?

I was looking at this map: $f(x,y) \mapsto (|x-y|,x)$, starting from some point
with coordinates $(x,y) \in [0,1]^2$, and iterating:
$(x,y),\, f(x,y), \, f^2(x,y), \,f^3(x,y), \ldots$.
It displays ...

**2**

votes

**1**answer

107 views

### Family of sets with unique subsets

I am given a set $M\subseteq\{1,\dots,n\},\,|M|=m$ and a famliy of $k$-sets ($k<m$) $\mathcal{U}=\{U_1,\dots,U_p\},\,U_{i}\subset M$. For this family, I would like to check one of the following ...

**13**

votes

**1**answer

636 views

### Is every graph the center of some other graph?

The center of a graph $G$ is the set of vertices that minimize the largest
distance to vertices in $G$, e.g., in the graph below, that radius is $4$:
Define the ...

**6**

votes

**0**answers

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

**19**

votes

**1**answer

254 views

### Hidden points in polygons

Let $h(n)$ be the largest number of mutually invisible points that can be located in a
polygon $P$ of $n$ vertices. Two points $x$ and $y$ are mutually invisible if the segment
$xy$ contains a point ...

**2**

votes

**1**answer

96 views

### Subdividing toward a unit distance graph in the plane

I just want to ask, what is the significance of subdividing a graph toward a unit distance graph? I have seen several studies of it but I cannot find what its importance.
I mean, like the study of ...

**3**

votes

**1**answer

103 views

### Obtaining each set (hyperedge) in a set system (hypergraph) as a union of sets in a smaller set sytem

Let $V$ be a set and $E$ a set of subsets of $V$. I'd like to know the proper terminology for the following concept.
Let me call it "generator". A generator is a set $F$ of subsets of $V$ such that ...

**15**

votes

**7**answers

1k views

### Two questions from combinatorics on words

Question 1. Assume that an infinite word $u\in\{0,1\}^{\mathbb Z}$ is not balanced. Is it true that there exists a finite 0-1 word $w$ such that $0w01w1$ or $1w10w0$ is a factor of $u$? Is it true ...

**2**

votes

**2**answers

250 views

### Computing the lexicographic indices of integer partition

If we order all the partitions of a integer in a lexicographic order, how can we compute the position of each partition in this order without having to explicitly list all other partitions that ...

**1**

vote

**1**answer

297 views

### a conjecture about a specific subset of $S_n$

Let $n>3$ be a positive integer.We denote the symmetric group of $n$ elements by $S_n$ and the identity mapping by $id$. For every $f\in S_n$, $f(1,2,\ldots,n)=(a_1,a_2,\ldots,a_n)$, denote $a_n$ ...

**3**

votes

**2**answers

232 views

### Cardinality of intersection of a random subset with a fixed subset

How can I simply prove the following fact:
Let $A := \{1, \dots n \}$ and $B := \{1, \dots, \lfloor \frac{n}{4} \rfloor \}$. Let $d \in (0,1)$ and let $R$ be a randomly choosen (with uniform ...

**3**

votes

**1**answer

261 views

### Sequences with integral variances

This is a companion to my earlier question,
Sequences with integral means.
This new question is, frankly, not as interesting, but it feels necessary to complete
the thought.
Let $V(n)$ be the ...

**20**

votes

**5**answers

639 views

### Sequences with integral means

Let $S(n)$ be the sequence whose first element is $n$, and from then onward,
the next element is the smallest natural number ${\ge}1$ that ensures that the
mean of all the numbers in the sequence is ...

**1**

vote

**1**answer

68 views

### the “compact good array” in a “good $N^+$-cycle”

We use $N^+$ to denote the set of positive integers.For any finite array $A:(a_1,b_1),...,(a_k,b_k)$,where every $(a_i,b_i)\in N^+\times N^+$,we call $A$ is good if for every $i\in ...

**1**

vote

**1**answer

106 views

### Transform $a\mathbf x+\mathbf b$, then make it $k$-sparse, resulting least modification?

Consider vector $\mathbf x = (x_1,x_2,\cdots,x_n)$, $a$ a scalar, $\mathbf b = (b_0,\cdots,b_0)$ and $k < n$.
I want to transform $\mathbf x$ ($\mathbf y = a\mathbf x+\mathbf b$) such that if I ...

**3**

votes

**1**answer

124 views

### Reference for partial Hadamard matrices

Definition. An $m\times n$ matrix is said to be a partial Hadamard matrix (let's say PHM) if its entries are chosen from $\lbrace -1, 1 \rbrace$ such that the dot product of each pair of row vectors ...

**-1**

votes

**1**answer

298 views

### Number of blocks in a t-(v,k,l) design with empty intersection with a given set U [closed]

Question
Given a $t-(v,k,\lambda)$ design $(X,\mathcal{B})$ and a set $U\subset X$ with $|U|=u\leq t$, what is the number of blocks $B\in\mathcal{B}$ such that $B\cap U=\emptyset$?
The answer is: ...

**1**

vote

**3**answers

348 views

### How do quantifiers limit scope?

I'm teaching a discrete math class at the high school level and realize that I'm fuzzier on a topic than I should be.
In their last problem set, I asked my students to translate "There is a triangle ...

**0**

votes

**0**answers

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

**1**

vote

**1**answer

426 views

### Graph Theory and Subgraphs [closed]

Let T = (V , E) be a tree with |V | = n â‰¥ 2. How many distinct paths are there (as sub graphs) in T?
I already have the answer to this question as (n/2). The problem that I'm having is finding ...

**3**

votes

**2**answers

173 views

### Question on weights and minimal degree

Edit: question has been changed from 'lexicographic' (cf. "D K"'s answer below) to 'degree' minimality.
Let $x_1,x_2,x_3$ be indeterminates. Fix an integer $k> 3$. Consider the set $M$ of all ...

**6**

votes

**1**answer

565 views

### Integer solution to special system of linear equations

This problem appear in my research, but I am unable to solve it.
There should be an easy argument, but I have not yet found it.
Informal version
An integer $k\geq 2$ is fixed.
We are given a matrix ...

**1**

vote

**1**answer

160 views

### How to determine the number of a cube within a bigger cube?

Hi all,
I have a cube, sized 39 x 13 x 8. I need to find out how many of them can fit in a cube of 100 x 100 x 100. I need to find the highest number possible.
Do you know of a way to do that ...

**4**

votes

**1**answer

202 views

### Best upper bound on rate for q-ary codes

Among the many upper bounds for families of codes in $\mathbb F _2 ^n$, the best known bound is the one by McEliece, Rodemich, Rumsey and Welch which states that the rate $R(\delta)$ corresponding to ...

**2**

votes

**1**answer

177 views

### On solution of a class of discrete-time Lyapunov equation

Hello members, let's consider the following equation
$$X=F_{1}XF_{1}^{T}+...+F_{p}XF_{p}^{T}+C$$
where $p$ is an positive integer and $C$ is a known positive semidefinite matrix. If we augment ...

**2**

votes

**1**answer

125 views

### On solution of a discrete-time equation

Hello, members.
I have a problem for the following problem
when I derive an optimization algorithm for stochastic singular systems
$$S(k+1)=A(k)S(k)A^{T}(k)+R(k)+F(k)S(k+1)F^{T}(k)$$
where ...

**1**

vote

**1**answer

251 views

### Distance between vertices in a vertex transitive graphs. [closed]

Can anybody help me in finding out the distances between vertices in a vertex transitive graphs. Is there any specific formula to calculate distance between vertices in this graph. Thanks for your ...

**6**

votes

**3**answers

547 views

### References on techniques for solving equations with discontinuous functions such as floor and ceiling?

Here I describe the sort of reference I'm after with a motivating example. I am not seeking solutions to my equations on this forum; I'm quite happy to do that myself. Rather, I'm asking for some good ...

**3**

votes

**0**answers

121 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* ...

**13**

votes

**1**answer

445 views

### Does erosion mix faster than a riffle shuffle?

It is a famous result of Aldous and Diaconis1 that
seven shuffles are necessary and suffice to approximately
randomize 52 cards.2
Here the shuffles are the standard riffle shuffle, where the ...

**12**

votes

**4**answers

1k views

### Has any attempt been made to classify finite groupoids?

I recently stumbled upon the Mathieu groupoid and I found them fascinating.
It appears as a subset of $S_{13}$ which is not closed under multiplication, but it turns out to be a groupoid with 13 ...

**5**

votes

**1**answer

607 views

### Bounding the entropy of a convolution

Say we have a function $f:\mathbb{Z}_2^n \to \mathbb{R}$, such that $\sum _{x\in \mathbb{Z}_2^n} f(x)^2 = 1$ (so we can think of $\{ f(x)^2\} _{x\in \mathbb{Z}_2^n}$ as a distribution). It is natural ...

**6**

votes

**1**answer

517 views

### Calculating a specific joint probability involving sums of binomial distributions

The following might look like a simple problem - but the question has been unanswered for more than a week on math.stackexchange.com, and I have asked quite a few of the Ph.d. students at our ...

**0**

votes

**0**answers

127 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

**1**answer

116 views

### expected size of unbalanced biclique in random bipartite graph

I am discovering random graph and I am trying to prove the following result. This is a follow-up on a previous question of mine
what's an upper bound on the size of the largest biclique in random ...