Do NOT use this tag; instead you might use co.combinatorics or various more specific tags.

**4**

votes

**3**answers

175 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:
...

**2**

votes

**1**answer

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

**0**

votes

**0**answers

36 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

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

**2**

votes

**0**answers

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

**15**

votes

**2**answers

774 views

### A set of integers whose factorial can be written as a product of two factorials

I am trying to collect informations concerning the set
$$\mathcal{A}=\left\{n\in\mathbb{N} \mid (\exists k,l\in\{2,3,\dots,n-2\})(n!=k!l!)\right\}.$$
It seems not much is known about the set ...

**4**

votes

**1**answer

65 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

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

**1**

vote

**0**answers

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

**2**

votes

**0**answers

87 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

53 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

220 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

114 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

45 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

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

**40**

votes

**1**answer

2k views

### Why is the Frankl conjecture hard?

This is a naive question that could justifiably be quickly closed.
Nevertheless:
Q. Why is
Péter Frankl's
conjecture so difficult?
If any two sets in some family of sets have a union that also ...

**7**

votes

**1**answer

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

**3**

votes

**0**answers

110 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

69 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

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

**1**

vote

**0**answers

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

**7**

votes

**1**answer

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

**11**

votes

**2**answers

655 views

### What is the probability that two random permutations have the same order?

I am interested in the orders of random permutations. Since the law of the logarithm of the order of a permutation converges to a normal law (for instance Erdös-Turan Statistical group theory III), ...

**2**

votes

**1**answer

86 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

**0**answers

26 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

**1**answer

115 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 & \\
& ...

**5**

votes

**3**answers

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

**13**

votes

**7**answers

2k views

### Special arithmetic progressions involving perfect squares

Prove that there are infinitely many positive integers $a$, $b$, $c$ that are consecutive terms of an arithmetic progression and also satisfy the condition that $ab+1$, $bc+1$, $ca+1$ are all perfect ...

**1**

vote

**0**answers

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

**7**

votes

**1**answer

250 views

### Recursive sequence of binomial random variables

Fix $p>0$ and define a recursive sequence of random variables with $X_1 =1$ and
$$X_{k+1} = X_k + \text{Bin}(X_k,p).$$
Thus, $\mathbf E [ X_k ] = (1+p)^k$.
I would like a left tail bound. Perhaps, ...

**11**

votes

**7**answers

714 views

### Finite-space dynamical systems

This question is quite open-ended, but I will formulate several sub-questions that I'll try to make precise. It is about finite-state dynamical system: start with a finite set $X$, with say $n$ ...

**2**

votes

**2**answers

350 views

### Minimally intersecting subsets of fixed size

The question I have, is how to generate the following collection of subsets:
Given a set $S$ of size $n$. I want to find a sequence of $k$ subsets of fixed size $m$, $0<m<n$, such that at each ...

**2**

votes

**1**answer

146 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

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

**4**

votes

**1**answer

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

**2**

votes

**3**answers

350 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

**5**

votes

**1**answer

160 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

90 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} ...

**0**

votes

**0**answers

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

**6**

votes

**1**answer

655 views

### Prime labelling of graphs

A prime labeling of a graph is an injective function $f: V(G) \to \{1, 2, ..., |V(G)|\}$
such that for every pair of adjacent vertices $u$ and $v$, $\text{gcd}(f(u), f(v)) = 1$ (labels of any two ...

**2**

votes

**1**answer

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

**3**

votes

**0**answers

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

**0**

votes

**0**answers

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

**6**

votes

**1**answer

94 views

### Above/below directed graph on cells of arrangement of lines

This question concerns the structure of a directed graph
built on the cells of an arrangement of lines.
My basic question is whether this graph has been
studied before, perhaps in another guise. I ...

**1**

vote

**0**answers

42 views

### Finding optimal set of permutations [closed]

I have the following data set of a human population. The data set captures households and relationships of the persons living in those households. My problem is how to group the individuals into ...

**3**

votes

**0**answers

66 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

**3**answers

140 views

### Simplifying a Taylor polynomial that involves Stirling numbers of the second kind

I am currently trying to evaluate a complicated function $f$ at a point $x+a$ using a high order Taylor polynomial about the point $a$. The polynomial has the standard form:
$$\sum_{n=1}^k ...

**8**

votes

**2**answers

201 views

### Repeats of all binary strings of length k

The question seems like it should be known, but I was not able to find it anywhere.
How many binary strings of length $n$ are required so that for every $k$ positions in these strings, all $2^k$ ...

**10**

votes

**1**answer

250 views

### Finding combinatorial models / statistics

In many cases in combinatorics and especially algebraic combinatorics with some representation theory, the main problem is about finding the correct statistic on a mathematical object.
For example, ...

**7**

votes

**1**answer

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