**15**

votes

**1**answer

901 views

### Prove that expression is integer

Numerical experiments suggest that
$\binom{2m}{m + k}\cdot\frac{3m - 1 - 2k^2}{2m - 1}$
is integer for all $-m \le k\le +m$. It means that expression evaluation could be implemented very efficiently, ...

**3**

votes

**1**answer

248 views

### Are there enough additive permutations?

I am hoping to learn enough about additive permutations to help with a number theory problem. These permutations also have connections to difference sets, orthomorphisms, transversals, and other ...

**4**

votes

**0**answers

48 views

### Existence of certain graph gadget related to coloring odd hole free graph

Wondering about the existence of graph gadget related to coloring
(or 3-coloring) odd hole free graphs.
Let $G$ be simple $k$-chromatic connected graph with two
vertices $u,v$.
Is it possible $G$ to ...

**2**

votes

**1**answer

83 views

### Set counting problem with a cap on the intersection between the set and a fixed partition

Fix sets $T_1,\ldots T_m$ as a $k$-partition of $[m\cdot k]=\{1,2,\ldots,m\cdot k\}$, so that $|T_i|=k$ and $|T_i\cap T_\ell|=0$.
1) For any $j\le k$, how many sets $C\subset [m\cdot k]$ are there ...

**1**

vote

**0**answers

146 views

### Complexity of reordering a matrix which consists independent sub matrices

Introduction:
Given a matrix A of a $k$ regular graph G. The matrix A can be divided into 4 sub matrices based on adjacency of vertex $x \in G$.
$A_x$ is the symmetric matrix of the graph $(G-x)$, ...

**2**

votes

**0**answers

45 views

### Maximum cardinality general factor of a graph

Given a graph $G=(V,E)$ and a set of integers $B(v)$ associated to each vertex, a general factor of $G$ is a set of edges $F\subseteq E$ such that the degree of each vertex $v\in V$ in the graph $(V, ...

**0**

votes

**0**answers

42 views

### Enumeration of simple graphs with given degree distribution/sequence [duplicate]

Is there any exact formula for asymptotic/exact enumeration of simple graphs with given degree sequence? I just found some results about it, but the formula is hold on for some conditions, for example ...

**1**

vote

**0**answers

109 views

### What are constructions for induced $C_5$-free graphs?

During a recent workshop, the question came up whether there are some constructions for graphs that are induced $C_5$-free, but they contain "everything else," so we don't want to forbid $C_5$'s, ...

**0**

votes

**2**answers

340 views

### Worst case difference in rank by column-row swapping

Given a matrix $m\in\{-1,+1\}^{n\times n}$. Consider $m^\sigma$ to be collection of all matrices obtained from $m$ by permuting rows and columns.
Consider $\mathscr{M}[m^\sigma]$ to be collection of ...

**6**

votes

**1**answer

104 views

### Counting equivalence relations with marked classes

The number of equivalence relations on a set of $n$ elements is the Bell number $B_n$.
If we wish to count the number of equivalence classes on a set of $n$ elements where one of the classes is ...

**4**

votes

**0**answers

88 views

### Prove or disprove a claim about covering a polytope by convex polytopes in a certain way

Here is the claim:
Given a polytope $K$ in a unit ball in $\mathbb{R}^d$, there exists a universal constant $C(d)>0$ depending only on $d$ and a countable collection of convex polytopes ...

**10**

votes

**6**answers

965 views

### Algorithms for calculating R(5,5) and R(6,6)

Calculating the Ramsey numbers R(5,5) and R(6,6) is a notoriously difficult problem. Indeed Erdős once said:
Suppose aliens invade the earth and threaten to obliterate it in a year's time unless ...

**2**

votes

**2**answers

217 views

### binomial/factorial identity mod p

In trying to determine the spectrum of a well-known ergodic transformation, I came up with the following useful (for me) result.
Let $p$ be a prime and $a$ a positive integer. Then for $M$ a positive ...

**3**

votes

**1**answer

86 views

### $P_3$-factors for 3-regular, 3-connected cubic graphs

Suppose that $G=(V,E)$ is a simple graph.
We know if $G$ is 3-regular, 3-connected and $|V|=4k$ for some $k\in \mathbb{N}$, then $G$ has a $P_4$-factor.
Question. Let $G=(V,E)$ be 3-regular, ...

**2**

votes

**2**answers

181 views

### Simultaneous lcms

Suppose that we have some finite number of $k$-tuples then we define the lcm of two of these tuples to be the tuple of lcms of the co-ordinates. E.g. $[(9, 10), (5, 18)] = ([9, 5], [10, 18]) = (45, ...

**16**

votes

**0**answers

295 views

### Need explicit formula for certain “$q$-numbers” involving gcd's

The question is motivated by yet another possible approach to a combinatorial problem formulated previously in "Special" meanders. I'm not giving details of the connection as I believe the ...

**7**

votes

**2**answers

276 views

### When is a sequence the sum of two Beatty sequences?

In other words, given a sequence $(s_n)$, how can we tell if there exist irrationals $u>1$ and $v>1$ such that
$$s_n = \lfloor un\rfloor + \lfloor vn\rfloor$$
for every positive integer $n$?
...

**1**

vote

**1**answer

182 views

### Counting matrices of special types

How many symmetric and non-symmetric $n\times n$ matrices with $0/1$ entries are there such that every row is distinct and every column is distinct? (I am looking for a proof as well).
If only every ...

**5**

votes

**2**answers

258 views

### Four Dimensional Rook Domination

Let $\gamma(G)$ denote the domination number of a graph, and $G\,\square\,H$ denote the cartesian product of two graphs. Then $K_8\,\square\, K_8$ is the rook graph, whose vertices are the squares of ...

**3**

votes

**1**answer

185 views

### Largest symmetric matrix given rank

Let $\mathscr{M}[n,d]$ be collection of $n\times n$ symmetric matrices with real entries from $\{0,1\}$ such that every row/column is distinct with sum of every row/column being $d$.
What is minimum ...

**2**

votes

**1**answer

48 views

### Vanishing Restricted Isometric Constant

In compressed sensing, we are interested in the restricted isometry property. Suppose the design matrix is $n$ by $p$, consisting of $np$ iid $\mathcal{N}(0, 1/n)$ entries. Assume both $n$ and $p$ are ...

**3**

votes

**1**answer

156 views

### higher dimensional analogue of EGZ theorem

The EGZ theorem states that any multiset of $2n-1$ integers has a subset of size $n$ the sum of whose elements is a multiple of $n$.
Kemnitz-Reiher theorem is a 2-dimensional analogue of EGZ. Here is ...

**9**

votes

**0**answers

110 views

### Is there a nice formula for the “non-crossing substitution” of linear combinatorial species?

Background
A linear species is a functor
$$F : \mathrm{Lin} \to \mathrm{FinSet},$$
where $\mathrm{Lin}$ is the category of totally ordered sets and bijections and $\mathrm{FinSet}$ is the category ...

**4**

votes

**0**answers

143 views

### inequality in a shape of inclusion exclusion formula

I have two inequalities to show, both of which describe some probabilities. First I know how to handle, and it follows from applying arithmetic-harmonic mean inequality:
consider 9 numbers ...

**5**

votes

**0**answers

134 views

### Extrapolation between longest increasing and longest alternating subsequences

The question
When should we expect Tracy-Widom?
motivated me to post the following question, in which I have been
interested for a while. Let $f(n)$ be a function from the positive
integers to ...

**4**

votes

**0**answers

103 views

### Generalization of Sprague-Grundy Theorem

In my research on Combinatorial Game Theory, I used a certain theorem that is essentially a generalization of the Sprague-Grundy theorem. Because the result hinges too much on the work of others to be ...

**8**

votes

**3**answers

667 views

### Why does the bitxor function appear in Nim?

I am conducting research in Combinatorial Game Theory (CGT). Although I have done a considerable amount of reading, I do not completely understand why the bit-xor function also known as the nim-sum ...

**0**

votes

**0**answers

60 views

### Minimum rank of certain matrices

Let $\mathscr{M}[n]$ be collection of $n\times n$ matrices with real entries from $\{0,1\}$ such that every row is distinct and every column is distinct.
What is minimum real rank of matrices in ...

**5**

votes

**1**answer

143 views

### partition of a convex set into squares

Let $P$ denote the perimeter function. It's not hard to prove that for any rectangle $R$ in $\mathbb{R}^2$, $R$ can be partitioned into a countable collection of squares $\{Q_k\}_{k=1}^{\infty}$ such ...

**2**

votes

**1**answer

187 views

### Expected value (probability) maximization with binomial distribution

I need to solve an optimization problem that involves an expected value like
$$F(n,x) = \sum_{k=0}^n \binom{n}{k} p^k(1 - p)^{n - k} f(k,x).$$
Here $f(k,x)$ is actually a probability coming from a ...

**0**

votes

**0**answers

68 views

### Classic question on integer partitions (with distinct summands)

I guess that the following was solved sometime in the 18th century, but could not find a reference to it. I am interested in approximations to the following integer partition problem:
Denote $R(N,L)$ ...

**3**

votes

**1**answer

149 views

### Products of relative prime numbers with least sum

Let $P(n)$ be the set of subsets $P$ of $\mathbb{N}$ with the properties
All elements of $P$ are relative prime to each other.
The product of all $k \in P$ is greater or equal to $n$.
Now let ...

**10**

votes

**0**answers

244 views

### Reference request: a combinatoric result [closed]

When I tried to construct a counterexample in my research, I encountered the following result, which should be true.
Let $m=m(n)$ be a function that grows faster than $\sqrt n$, so $m(n) = ...

**0**

votes

**0**answers

87 views

### A sum on a minimums conjecture

Prove or disprove:
$$m(n,k,s)=\sum_{a_1=1}^n \sum_{a_2=1}^n \cdots \sum_{a_k=1}^n \min(a_1, a_2,\cdots, a_k)^s =$$
$$ \sum _{i=0}^{k-1} \frac{(-1)^i}{i!} F(n,i+s) \sum _{j=0}^{k-1} \frac{\partial ...

**2**

votes

**1**answer

102 views

### Probability of Hamming weight

Given $s,t\in(0,1)$, $c>1$, $n\in\Bbb N$, pick ${n^t}$ random vectors $\{v_i\}_{i=1}^{{n^t}}$ such that each $v_i\in\{x\in\{0,1\}^{2^n}:|x|_{hamming}={2^{n-n^s}}\}$.
Denote $v_j\cap v_j$ to be ...

**4**

votes

**1**answer

127 views

### Motzkin polynomials and enumeration of chord diagrams

On page 12 of the paper Enumeration of chord diagrams on many intervals and their non-orientable analogs" by Alexeev, Andersen, Penner, and Zograf is a list of polynomials which are a refinement of ...

**5**

votes

**0**answers

181 views

### Unique Nash equilibrium games

Multicast network design game is a special case of a general network design game (http://www.cs.cornell.edu/home/kleinber/focs04-game.pdf) in which there is a target vertex $t$ and $n$ rational ...

**2**

votes

**0**answers

59 views

### Vanishing of finite difference operators by composition under a cyclic condition

Consider $n$ finite difference operators $D_1, \ldots, D_n$
acting on real-valued functions $f_1 (y), \ldots , f_n (y)$
of a variable $y$, with the following properties:
(i) $D_i f_i (y) = 0$ for ...

**12**

votes

**2**answers

307 views

### Asymptotics of coefficients of implicitely defined generating function

I have two integer sequences $\{a_n\}_{n=0}^\infty$ and $\{b_n\}_{n=0}^\infty$. Explicit formulas for the $a_n$ are known and their asymptotic growth is fully understood. My wish is to also understand ...

**10**

votes

**0**answers

317 views

### Combinatorial results by Poincaré duality

For the n-dimensional Torus, the k-th homology group (with integer coefficients) is isomorphic to the direct sum of $n \choose k$ copies of $\mathbb{Z}$.
Poincaré duality thus gives us a somewhat ...

**6**

votes

**2**answers

397 views

### Embedding of planar graphs

I've recently come across the following lemma.
Lemma (Valiant): A planar graph $G$ with maximum degree $4$ can be embedded in the plane using $O(|V|)$ area in such a way that its vertices are at ...

**2**

votes

**0**answers

38 views

### Catalogs/numbers/constructions of non-isomorphic conference matrices

I am interested in complete catalogs of non-isomorphic conference matrices, similar to those of Hadamard matrices. Do such catalogs exist? If yes, then where could they be found, and what is an ...

**0**

votes

**1**answer

52 views

### Extracting path information for a directed acyclic graph

For a research problem I am tackling, I have a directed acyclic graph $G(V,E)$. With every node in $V$, I have a variable $y$ associated. Now, given two nodes $i$ and $j$, I would like to have the sum ...

**0**

votes

**0**answers

55 views

### Linear intersection number of a product of graphs

A linear hypergraph is a pair $\pi=(X, L)$ where $X\neq \emptyset$ is a set and $L\subseteq {\cal P}(X)$ has the following properties:
for $e\in L$ we have $|e|\geq 2$;
if $e_1\neq e_2 \in L$ then ...

**2**

votes

**1**answer

138 views

### Number of lines of symmetry of a set of lattice points

Given some finite $S\subseteq\mathbb R^2$, it is clearly possible for $S$ to have arbitrarily many lines of symmetry. However, it is not very clear if the same is necessarily true for subsets of ...

**3**

votes

**0**answers

100 views

### “Standard” notation for symmetric functions?

Here is what I encountered in the paper "The Optimal Lattice Quantizer in Three dimensions" by Barnes and Sloane.
Here is the setup:
Let $\Lambda$ be a lattice in $\mathbb{R}^3$. Around each ...

**1**

vote

**1**answer

129 views

### Selecting columns of a set of boolean matrices with constraint on the ones in each row

I've come up with the following question in my research: Let $S$ be a finite set of $n \times n$ matrices with elements 0 or 1. denote $n_i$ as the total number of 1's in the $i$th row of all matrices ...

**8**

votes

**1**answer

203 views

### Cheeger Numbers for 3-regular Graphs

A student wanted a challenging Graph Theory programming project and I had
him try to determine the maximum value of the Cheeger number (isoperimetric number) among all 3-regular graphs of order $n$, ...

**3**

votes

**2**answers

313 views

### Geometry, Number Theory and Graph Theory of n-gon, permutation and graph labeling?

Given $n$ and $t$ lengths $ l_i, 1\leq l_1<l_2<\cdots<l_t\leq n-1$, of directed diagonals within an $n$-gon such that $l_1+\cdots+l_t\neq 0 \pmod n)$. Does it exist a directed path within ...

**4**

votes

**1**answer

78 views

### How to realize any non-crossing matching as $\mathrm{Re}[p(z)]=0$

Asymptotically any polynomial is $p(z) = z^n + O(z^{n-1})$. Therefore $\mathrm{Re}[p(z)]= r^n \cos(2\pi i \theta)$ which vanishes at $\theta = \frac{(k+ \frac{1}{2})\pi}{n}$. Those $2n$ line ...