**0**

votes

**1**answer

49 views

### The cost function in the Weighted Bipartite Matching Problem (a.k.a the Assignment Problem)

In the definition of this problem, the weight/cost function generally takes value in $\mathbb{Z}$ (or sometimes $\mathbb{Q}$).
This is what I observed from some books (e.g. "Combinatorial ...

**3**

votes

**1**answer

72 views

### Probabilistic many-to-one matching

Let $p<1$ be a constant. Consider two sets $A,B$ with $n$ and $nf(n)$ vertices, respectively, where $f(n)$ is an integer. For each pair $(a,b)\in A\times B$, the edge between $a$ and $b$ appears ...

**2**

votes

**2**answers

108 views

### Matching with probabilistic edges

Let $p<1$ be a constant. Consider two sets $A,B$, each with $n$ vertices. For each pair $(a,b)\in A\times B$, the edge between $a$ and $b$ appears with probability $p$, independently of the ...

**1**

vote

**0**answers

95 views

### Lower bound on the value $\textbf{1}^Tx$ such as $Ax\geq b$

The problem may be formulated as follows:
We are given a set of $m$ positive numbers $\{b_1,...,b_m\}$ and a set of $n$ positive numbers $\{v_1,...,v_n\}$. We have $v_j\leq K$, $j=1,...,n$, for a ...

**4**

votes

**4**answers

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

**3**

votes

**1**answer

127 views

### Volume of the convex hull of the set of all graphic sequences of a given length

Consider the set of all graphic sequences with $n$ elements as a subset of $\mathbb{R}^{n}$, namely let
$$D(n)=\{(d_{1},\dots,d_{n})\in\mathbb{Z}_{+}^{n}:d_{1}\geq\dots\geq d_{n},\ ...

**7**

votes

**1**answer

261 views

### Linear relations among permutation matrices

Given a permutation $\sigma\in S_n$, let $P_\sigma$ denote the corresponding $n\times n$ permutation matrix. It is easy to see that for $n=3$, there is only one linear relation up to scaling given by ...

**1**

vote

**1**answer

88 views

### Eulerian graphs with prescribed number of edges

Under what conditions there exists an $n$-vertex eulerian graph with $m$ edges for $1\leq m\leq\frac{n(n-1)}{2}$?

**8**

votes

**1**answer

156 views

### Expansion in strongly regular graphs

Have you seen the following statement proven anywhere?
Let $G$ be a strongly regular graph with parameters $(n,k,\lambda,\mu)$ with $\lambda,\mu>0$. Then there is no set $A$ of at least $n/4$ ...

**8**

votes

**0**answers

151 views

### Partition regularity in the squares

A linear equation $c_1x_1 + \cdots + c_sx_s = 0$ is partition regular if for every partition of the natural numbers into colour classes $A_1, \ldots, A_r$, there is a solution to the equation in which ...

**11**

votes

**1**answer

266 views

### Travelling salesman: can the furthest-neighbour algorithm beat the nearest-neighbour?

This is a problem that has bugged me for quite some time, and I have not been able to find any documentation about it online. It is well known that the NN algorithm can yield the worst possible route ...

**9**

votes

**3**answers

250 views

### Labeling edges of an icosahedron with sum constraints

The question is inspired by this previous MO question. There it was shown that it's possible to label the edges of a cube by the numbers $\{1,2,\ldots,6,8,9, \ldots, 13\}$ in such a way that:
Three ...

**3**

votes

**1**answer

359 views

### Game on a string

I am interested if one can design an efficient (polynomial) algorithm telling whether the first player has a winning strategy for a game described below.
The board is a string consisting of only ...

**6**

votes

**0**answers

94 views

### Inequality among domino tilings of large triomino shapes

Inspired by this question, which asks for what shape maximizes the number of domino tilings, I want to ask the following seemingly simpler question, which I have been thinking about for a while:
...

**15**

votes

**5**answers

566 views

### The smallest disk containing all sides of an $n$-gon

Start with a regular $n$-gon of side 1 and consider its sides as open segments that can be moved around in the plane, allowing only translations. Two segments may not intersect.
What is the ...

**15**

votes

**2**answers

548 views

### A conjecture about $\lfloor n!\cdot q/e\rfloor-\,!n\cdot q$

I was thinking about this question asked at Math.SE, when I came up with the following conjecture.
For every $q\in\mathbb Q$ consider a sequence $s_n^{(q)}$ (terms within the sequence are indexed by ...

**3**

votes

**1**answer

95 views

### Vertex-connectivity of connected, vertex-transitive graphs without $K_4$ is maximum possible

A graph is said to have optimal vertex connectivity if its vertex connectivity equals its minimum degree. According to this arXiv preprint, it was shown by Mader in (Arch. Math., 1970) and (Math. ...

**0**

votes

**1**answer

105 views

### An asymptotic intersection problem

Given a set of $n\in\Bbb N$ integers $\mathcal S$ and $\mathsf s,\mathsf t\in\big(0,1\big)$, suppose we choose two sets:
$$\mathcal S_{\mathsf{1}}\subseteq\mathcal S$$
$$\mathcal ...

**0**

votes

**0**answers

34 views

### Is the laplacian spectral radius of a directed grpah a non-decreasing function?

Given a directed graph G and its respective laplacian matrix $L = D-A$ where $A$ is the adjacency matrix ($A_{ij}=1$ if there is a link from $j$ to $i$ and $A_{ij}=0$ otherwise) and D is the diagonal ...

**4**

votes

**2**answers

292 views

### Can you simplify (or approximate) $\sum_{n=0}^{N-1}\begin{pmatrix}N-1\\n\end{pmatrix}\frac{(-1)^n}{n+1} e^{-\frac{n}{2(n+1)}\lambda}$?

Let $\begin{pmatrix}x\\y\end{pmatrix}$ be the binomial coefficient. I am trying to get a better understanding of the sum
\begin{equation}
...

**2**

votes

**3**answers

199 views

### Making integer multisets graphic

Let $M=(X,f)$ be a multiset, where $X$ is the underlying set of elements and $f:X\rightarrow\mathbb{N}$ is the multiplicity function. For every $k\in\mathbb{N}$ put $k\cdot M:=(X,k\cdot f)$. It is ...

**7**

votes

**1**answer

90 views

### When is the diagonal of a rational bivariate power series again rational

Given a rational bivariate power series $F(x,y)=\sum{a_{n,m}x^ny^m}$, the diagonal function $G(t):=\sum{a_{n,n}t^n}$ is known to be algebraic, although not rational in general. I was wondering if ...

**16**

votes

**0**answers

248 views

### Zero curves of Tutte Polynomials?

There is an extensive theory of the real and complex roots of the chromatic polynomial of a graph, a substantial fraction of this being due to the connections between the chromatic polynomial and a ...

**8**

votes

**1**answer

300 views

### Removing singularities in generating functions

This is a problem about the practicalities of removing singularities in multivariable complex functions.
In trying to derive the generating function (in two variables) for a certain problem in ...

**1**

vote

**2**answers

66 views

### Position likelihood in a 2D graph [closed]

I am looking for general principles or specific answers to this generic example.
Assume a 2d grid with no boundaries and a roving dot (ant/drunk guy/particle) that is initially located at some ...

**4**

votes

**0**answers

66 views

### A relaxation of proper coloring

I am wondering if the following relaxation of proper coloring appears somewhere. I have tried some searching and have found a few relaxations of proper coloring, but none the coincides with what I ...

**6**

votes

**2**answers

253 views

### extremal bipartite graph

I'm facing the following question:
Given a bipartite graph $G = (L \cup R, E)$.
Let $n = |L|$, $m = |R|$, and a parameter $k \in \mathbb{N}$, $n > m > k$.
What is a minimal possible number ...

**6**

votes

**1**answer

222 views

### Subsets of [1..N] with no three-term arithmetic progressions and no large gaps

Let S be a subset of [1..N] containing no three-term arithmetic progression, and let h(S) be the size of the largest gap between two consecutive elements of S. By Roth's theorem, h(S) has to grow ...

**4**

votes

**1**answer

86 views

### Is there a nice form for the Frobenius characteristic of a border shape character?

Let $\chi^V$ be the character of a border strip Specht module, i.e. a Specht
module for a skew tableau that contains no $2 \times 2$ square. I know that
the Frobenius characteristic of $\chi^V$ is ...

**2**

votes

**0**answers

117 views

### On sets of coprime numbers

We know that from prime number theorem that the number of primes below $n$ and above $\frac n2$ (denoted by $\pi_{n,\frac n2}$ is approximately $$\pi_{n,\frac n2}\approx\frac{n}{2\ln n}.$$
Denote by ...

**2**

votes

**3**answers

269 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

**7**

votes

**2**answers

206 views

### A Different 2-factor in a graph

We know that a k-factor of G is a k-regular spanning subgraph of G. And if G is 4-regular (or 2k-regular), it can be partitioned into 2 (k) edge-disjoint 2-factors (Petersen 1891).
My question is in ...

**-1**

votes

**2**answers

71 views

### Is there a formula that determines the size of the leafage of a graph's spanning tree? [closed]

In general terms, all the spanning trees of a graph G have the same number of leaves.
Is there any formula that allows us to know the number of leaves in terms of |V| and |E| for any spanning tree of ...

**1**

vote

**1**answer

96 views

### Strongly connected graph and the eigenvalues of the laplacian matrix

Given a directed graph $G$, consider that $G$ is strongly connected iff every vertex $i$ in $G$ has inner degree $k_i\geq 1$. Reformulation of this definition: $G$ is strongly connected iff for any ...

**0**

votes

**1**answer

65 views

### An asymptotic set containment problem [closed]

Given a set of $n\in\Bbb N$ integers $\mathcal S$, suppose we choose two sets:
$$\mathcal S_{\mathsf{small}}\subseteq\mathcal S$$
$$\mathcal S_{\mathsf{big}}\subseteq\mathcal S$$ with cardinalities
...

**4**

votes

**1**answer

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

**7**

votes

**2**answers

230 views

### Distribution of $\max_{n \ge 0} S_n$, random walk

Say we have a random walk that is a nearest neighbor random walk on the integers where at each step the probability of moving one step to the right is $p$ and the probability of moving one step to the ...

**0**

votes

**2**answers

95 views

### Infinite k-connected planar graphs

By planar I mean there is no $K_{3,3}$ minor of $K_5$ minor. Also, I am only considering the $\mathbb{R}^2$ surface, not a torus not any other surfaces.
I know that to construct such graph, For $k ...

**4**

votes

**1**answer

195 views

### Combinatorial description of a 120-cell

I'd like a combinatorial description of the 1-skeleton of the 120-cell (roughly) along the lines of the following description of the 1-skeleton of a dodecahedron.
(View all elements of product sets ...

**19**

votes

**1**answer

580 views

### Covering of a surface of a cube $n\times n \times n$ by pieces of paper $1\times 6$

When I was too young one of my problems was in the list of problems of All-Russian Olympiad. The problem is the following:
Problem. We have a surface of a cube $n\times n \times n$ such that each ...

**4**

votes

**1**answer

80 views

### Weights on cyclic orderings

Are there standard or known weights/metrics on cyclic orders?
Cyclic orderings are different ways of listing elements from a finite set, where you call two lists the same if they differ only by a ...

**2**

votes

**1**answer

127 views

### Does this version of Hadwiger's conjecture hold for graphs with infinite chromatic number?

Let $G = (V,E)$ be a finite, simple, undirected graph. Hadwiger's conjecture states that
(Hadw): $K_{\chi(G)}$ is a minor of $G$.
It turns out that for finite graphs, (Hadw) is equivalent to the ...

**4**

votes

**1**answer

115 views

### Existence of an infinite word with a predetermined asymptotic for the word complexity

Let $w$ be an infinite binary word, for example: $$1010100001 0010011000 0001001110 0101011011 \dots$$
Let $N_w(k)$ be the set of distinct subwords of $w$ of length $k$, and $n_w(k)$ the cardinal of ...

**1**

vote

**1**answer

49 views

### Summation of multinominal coefficients with extra bounds on summation indices

My question is related to the sum
\begin{equation}
S(n,N) = \sum_{k_1+k_2+...+k_N=n}\frac{n!}{(k_1!)\cdot(k_2!)\cdot...\cdot(k_N!)} = N^n,
\end{equation}
which is comes from the multinomial ...

**2**

votes

**0**answers

51 views

### The numbers of edge colorings and partitions into vertex covers

Let $G = \langle X \cup Y, E\rangle$ be a $d$-regular bipartite graph such that $|U|=|V|=n$, and assume that $d$ divides $n$. Let $F(G)$ denote the number of proper edge colorings of $G$ using $d$ ...

**3**

votes

**1**answer

75 views

### Number and asymptotic for cyclic sequences

Cyclic sequence is equivalence class of cyclic shift action.
If $a = (a_1, ... , a_i)_c$ is cyclic sequence then $(a_1, a_2, \ldots a_{i-1}, a_i)_c = (a_2, a_3, \ldots, a_i, a_1)_c = \ldots = (a_i, ...

**0**

votes

**1**answer

116 views

### For a set of positive integers, is this inequality always true?

The input consists of a set of positive integers $\{b_1,...,b_2\}$ such that $$\sum_{i=1}^nb_i=CK,$$ with $C$ and $K$ two positive integers.
The question is the following, is there $k\in\{1,...,n\}$ ...

**4**

votes

**1**answer

118 views

### Asymptotic for binomial sums

Let $S(n, t) = \sum_{k = 0}^n {n \choose k} ^t$.
The task is to find asymptotic behavior of $S(n,5)$, $n \to \infty$.
Asymptotic for $S(n,0)$ and $S(n,1)$ is very simple.
For $S(n,2)$ we can use ...

**5**

votes

**1**answer

74 views

### Reference for restriction formula in terms of double Schubert polynomials

Everyone (that is, everyone who cares) knows that double Schubert polynomials represent Schubert classes in equivariant cohomology in type $A$. We also know that we can restrict Schubert classes to ...

**4**

votes

**1**answer

182 views

### Summation of an infinite q-series

When calculating a Partition function, I encounter the following summation
$$\sum_{n=0}^{\infty} x^n q^{n^2}.$$
I know that the sum $\sum_{n=-\infty}^{\infty} x^n q^{n^2}$ is a Theta function, but I ...