**1**

vote

**1**answer

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

**4**

votes

**0**answers

94 views

### Counting vertex-permutations of a finite tree which rip all edges

Given a finite tree $T$ with $n$ vertices labelled $1,\dots,n$, we say that a permutation $\sigma$ of $1,\dots,n$ rips all edges if $\{\sigma(i),\sigma(j)\}$
is never an edge for every edge $\{i,j\}$ ...

**2**

votes

**1**answer

100 views

### Maximal neighbour-full partition of $\{0,1\}^n$

What is the largest complete minor of the $n$-dimensional hypercube? (which we call $k(n)$)
Alternatively, what is the partition of $\{0,1\}^n$ with each set connected and neighboring each other that ...

**1**

vote

**0**answers

97 views

### Evaluation of Macdonald Polynomials at $x_1=x_2=…=x_n = h$

This question is related to my previous question (here).
Let $P_\lambda$(q,t) be the Macdonald polynomials with partition $\lambda$. Let $\Lambda$ denote the ring of symmetric functions over the ...

**3**

votes

**0**answers

91 views

### A “nice” Orthogonal Basis for Translation Invariant Symmetric Polynomials

It is going to be a rather long question, so I will first state it and then try to explain and motivate it.
Take $\Lambda_n $ as the graded ring of symmetric polynomials of a field $F$ in $n$ ...

**37**

votes

**0**answers

2k views

### How to prove this polynomial always has integer values at all integers?

Let $m$ be any positive integer.
$$
P_m(x)=\sum_{i=0}^{m}\sum_{j=0}^{m}{x+j\choose j}{x-1\choose j}{j\choose i}{m\choose i}{i\choose m-j}\frac{3}{(2i-1)(2j+1)(2m-2i-1)}.
$$
Question: $P_m(x)$ always ...

**10**

votes

**2**answers

955 views

### A new generalisation of Fermat's little theorem?

I would like to share a personal result, which I interpret as a "generalisation of Fermat's little theorem". I know that there exist already several generalisations (e.g. Euler's) but I would like to ...

**3**

votes

**0**answers

131 views

### Algebraic integers with conjugates of fixed norm

Let $n$ be a positive integer and let $Q_n^d$ be the set of algebraic integers $\zeta$ which live in a degree $d$ extension of the rationals and such that any Galois-conjugate $\zeta^\sigma$ of ...

**2**

votes

**1**answer

92 views

### sub-variety of (P^1)^4

Let $S$ be the sub-algebra generated by the set $\{x_1x_2y_3y_4, x_1x_3y_2y_4, x_1x_4y_2y_3, x_2x_3y_1y_4, x_2x_4y_1y_3, x_3x_4y_1y_2\}$ of homogeneous polynomials of degree $4$. I need to study the ...

**4**

votes

**0**answers

211 views

### Every integer, and every positive integer?

Construct $A_k = (a_1, …, a_k)$ and $D_k = (d_1, …, d_k)$ inductively from $a_1 = d_1 = 0$, starting with $k = 1$, as follows: let $h$ be the least integer $>-a_k$ such that $h \not\in D_k$ and ...

**2**

votes

**1**answer

106 views

### Representation numbers of numerical semigroups

I've been playing around with numerical semigroups lately. I'm pretty new to this stuff, so I apologize in advance if my notation is non-standard. Fix positive integers $x_1,\dots,x_r$ with ...

**-1**

votes

**1**answer

135 views

### Number of Nice Matrices

Let's call a nice matrix a square matrix of size $n$ with elements from $\{1,...,n\}$ such that every row and every column contains all the number $1,...,n$,
What is the number of nice matrices ?
a ...

**5**

votes

**1**answer

130 views

### How are the infinity norm of Fourier transforms of sign vectors distributed?

This is a follow up to an earlier resolved question. Define the $n$-dimensional discrete Fourier transform via the matrix
$$
D_{s,t} := \omega^{st},
$$
where $\omega=\exp(-2\pi i/n)$. Notice that $D$ ...

**4**

votes

**1**answer

94 views

### Is it true that any $3$-uniform hypergraph that is not $k$-colorable must have $\Omega(k^3)$ edges?

What is the best lower bound in terms of $k$ on the number of edges in a $3$-uniform hypergraph that is not $k$-colorable?
Thanks in advance.

**2**

votes

**1**answer

96 views

### Is there a systematic relation between the generating functions for the rows vs that for columns of infinite sized Carleman-matrices?

(I've asked this in MSE but nobody had an idea since dec 14...)
(Roughly related, but generalizing, of this earlier MSE question)
Background: ...

**3**

votes

**1**answer

150 views

### Partitioning a binary tree into vertex-disjoint subtrees

Say we have a labeled, binary unrooted tree $T$, i.e. each node has either 1 or 3 neighbors.
Denote by $L(T)$ the set of leaves (degree-one nodes) of $T$.
For some $L \subseteq L(T)$, denote by ...

**4**

votes

**0**answers

153 views

### Evaluate a multiple integral

I want to compute this integral and I would appreciate any help: $N\geq 1$ is fixed.
$$I_N=\int_{0\le r_n\le r_{n-1}\le\cdots\le r_1} e^{-(r_1^2+\cdots+r_n^2)} \prod_{i<j} \sinh(r_i-r_j) ...

**1**

vote

**0**answers

74 views

### permutations sampling by probability matrix [closed]

I am looking for effective and reliable algorithm which is able to generate random samples of permutations by square doubly stochastic probability matrix $P$ (n x n) distribution ($\sum_{i}p_{i,j} = ...

**2**

votes

**1**answer

154 views

### Sum Of n numbers taken $k$ at a time, where numbers are of form $r\choose k$

I have an array of numbers lets call it $p$ , where $p[r]={k+r-1\choose k-1}$
I want to find the sum of all the elements of $p$ taken $n$ at a time .
$0\le r\le k$
For instance, for $k=3$ ,$n=2$ , ...

**4**

votes

**1**answer

229 views

### Euler-like identity for partition function

Following is the wonderful Euler's partition identity:
$$\prod_{i=1}^\infty (1 - x^i) = 1 + \sum_{k=1}^\infty (-1)^k \left (x^{(3k^2-k)/2} + x^{(3k^2+k)/2} \right )$$
I'm wondering if there is ...

**3**

votes

**0**answers

122 views

### Combinatorial result needed in machine learning? [closed]

Say $\sigma_1, \sigma_2, \dots, \sigma_m$ are i.i.d distributed $\pm1$ variables. How do i show that for any choice of $S_1, S_2, \dots, S_d$ subsets of $\{1, 2, \dots, m\}$, the expectation of the ...

**5**

votes

**1**answer

230 views

### Chromatic number of graph defined on the set of permutations

For $n\in\mathbb{N}$ let $S_n$ denote the set of permutations on the set $\{1,\ldots,n\}$. Set $$E_n = \big\{\{\pi_1, \pi_2\}: \pi_1,\pi_2\in S_n \land \exists k_1 < k_2 <\ldots <k_r\leq n: ...

**1**

vote

**0**answers

93 views

### First to note the relation between Stasheff polytopes (associahedra) and compositional inversion?

In my answer to MO-Q: Enumerative geometry and nonlinear waves, I outline the relation between the refined face polynomials of the Stasheff polytopes (associahedra) and the partition polynomials for ...

**3**

votes

**0**answers

50 views

### The Class of Strong Resolving Graphs of Hamiltonian Outerplanar Graphs

I'll start with a couple important definitions. I'm not sure how well-known any of them are.
Firstly, if $G$ is a graph, and $u, v \in V(G)$, say that $u$ is maximally distant from $v$, denoted $u\ ...

**7**

votes

**0**answers

204 views

### Theorems proved using combinatorial nullstellensatz that have no other known proof

Alon's (or Alon and Tarsi's?) combinatorial nullstellensatz is a powerful algebraic tool with many applications in combinatorics and number theory. See this, this, this and this mathoverflow question. ...

**4**

votes

**2**answers

144 views

### Can we find 3 disjoint directed Hamiltonian cycles in the cube?

Let $D$ be the digraph on $2^d$ vertices with $d2^d$ edges that we obtain by directing each edge of the $d$-dimensional hypercube in both directions.
Can we partition the edges of $D$ into $d$ ...

**0**

votes

**0**answers

89 views

### When does the normalized graph Laplacian have eigenvalue 1?

Let $G= (V,E)$ be a finite, undirected and unweighted graph with $V = \{v_1,\ldots, v_n\}$. Denote by $d_i$ the degree of $v_i$, i.e. the number of vertices that are adjacent to $v_i$. Let $A$ be the ...

**2**

votes

**1**answer

201 views

### Does the minor graph of graphs on $\mathbb{N}$ have an uncountable independent set?

By a graph I mean a pair $G = (V, E)$ where $V$ is a set and $E \subseteq \mathcal{P}_2(V) := \{\{a,b\}: a\neq b \in V\}$. We write $V(G) := V$.
If $S, T$ are disjoint subsets of $V(G)$ we say that ...

**1**

vote

**0**answers

56 views

### Proper edge colorings with no bi-colored 5-paths

Consider you want to properly edge color a graph such that it has no bi-colored cycle. Denote by $\alpha'(G)$ the least number of colors required to color the edges of $G$ in such a way.
It is well ...

**14**

votes

**0**answers

421 views

### Probability of many overlapping zero inner products on a circle

[Question edited and changed a little on June 14 2015]
Consider an $n$-dimensional vector $v$ with $v_i \in \{-1,1\}$. Now consider an $n$-dimensional vector $w$ with $w_i \in \{-1,0,1\}$. The ...

**13**

votes

**1**answer

585 views

### A circulant coin weighing problem

We are given $n$ coins, some of which are "real" and weigh $1$ and some of which are "fake" and weigh $0$. We have one "spring scale" which can weigh any subset of the coins. A classic question asks ...

**4**

votes

**1**answer

116 views

### Infinite graphs with “similar” Hom-sets

Let $G,H$ be infinite simple undirected graphs with the property that for any graph $X$ we have $|\text{Hom}(X,G)| = |\text{Hom}(X,H)|$. Does this imply that $G$ is isomorphic to a subgraph of $H$, ...

**4**

votes

**0**answers

87 views

### Sparsifiers for 3-term arithmetic progressions

Let $G$ be a finite abelian group of odd order, let $D\subseteq G$, and $\epsilon \in (0,1)$.
For $S\subseteq G$ define
$$
\Lambda(S) = \frac{1}{|S||G|} \sum_{s\in S}\sum_{g\in G} ...

**7**

votes

**1**answer

190 views

### Iterated sumset inequalities in cancellative semigroups

This question is motivated by the following well-known theorems:
Thm (Plünnecke): If $A$ is a finite nonempty subset of an abelian group, then for every $n$ we have $|A^n| \le ...

**0**

votes

**1**answer

156 views

### Moment maps and flat degenerations of toric varieties

We have a flat family of projective varieties with a torus $T$ action, over $\mathbb{A}^1$.
How do the moment map images of the fibers change when we pass from the generic fiber to the special fiber ...

**1**

vote

**1**answer

194 views

### Ask the name of a combinatorial theorem

It is a classical theorem. For given integer $n \ge 1$, among ${n\choose{n/2}} = 2^{(1-o(1)n)}$ strings in the cube $\{0, 1\}^n$ with weights $n/2$, i.e., $n/2$ indices are 1, there are at least ...

**9**

votes

**2**answers

364 views

### Sumsets and dilates: does $|A+\lambda A|<|A+A|$ ever hold?

The following problem is somehow hidden in this recently asked question, but I believe that it deserves to be asked explicitly.
Is it true that for any finite set $A$ of real numbers, and any real ...

**9**

votes

**1**answer

232 views

### One identity in Lie algebras

Let $L$ be a (non-restricted) Lie algebra over a field of prime characteristic $p,$ $UL$ be its universal enveloping algebra and $a_1,\dots, a_p \in L$ (the number of elements is equal to the ...

**7**

votes

**1**answer

118 views

### Does the Tutte polynomial of iterated cone graphs detect isomorphism?

Let $T_G(x,y)$ denote the Tutte polynomial of a graph. Of course we may have $T_G(x,y) = T_H(x,y)$ for $G$ and $H$ non-isomorphic graphs.
Now let $c(G)$ denote the cone graph of $G$, i.e., the graph ...

**0**

votes

**0**answers

59 views

### Finding a “special” non singular submatrix

Given a square integer matrix $A \in M_n(Z)$ and two subsets $I, J \subset \{ 1, \ldots, n\}$, we define $A_{I,J}$ as the sub-matrix of $A$ containing the rows (resp. columns) whose index is in $I$ ...

**1**

vote

**1**answer

62 views

### Graph classes which are not perfect but the stability number = clique cover numer?

I have a result for graphs whose stability number=clique cover number, which naturally includes the perfect graphs, but I'm curious about if there are other known and well-definable graph classes ...

**8**

votes

**3**answers

743 views

### Catalan numbers as sums of squares of numbers in the rows of the Catalan triangle - is there a combinatorial explanation?

This question arose from an answer to my recent question How many traces are there on Temperley-Lieb, Fuss-Catalan, Iwahori-Hecke, Birman-Wenzl-Murakami-Kauffman, ... algebras?
What I need from that ...

**0**

votes

**0**answers

111 views

### Does the equality of product of integers modulo prime p holds in a given interval?

For any given prime $p$, does there exist $a_1,a_2,\dots,a_k,$ (not necessarily distinct) $b_1,b_2,\dots,b_m$ (not necessarily distinct) and $y_1$, $y_2$ such that
...

**6**

votes

**1**answer

262 views

### Combinatorial formula for the number of different words

I originally posted this question here:
http://math.stackexchange.com/questions/1296199/combinatorial-formula-for-the-number-of-different-words :
I am interested in the asymptotic behaviour of the ...

**11**

votes

**2**answers

315 views

### The most number of points that realize only $k$ distinct distances

For $k \ge 1$, let $f_d(k)$ be the largest possible number of points $p_i$
in $\mathbb{R}^d$ that determine at most $k$ distinct (Euclidean) distances,
$\|p_i-p_j\|$.
Example. For points in the plane ...

**2**

votes

**0**answers

57 views

### Euclidean minimum spanning trees intersecting each unit square

The recent question "Euclidean Minimum Spanning Trees Restricted to One Vertex Per Grid Cell" can be restated in terms of "minimum spanning trees intersecting each (closed) lattice square of an ...

**-2**

votes

**1**answer

75 views

### How does deletion-contraction affect chromatic number? Can it increase chromatic number? [closed]

Question: In graph theory, contracting an edge or deleting an edge are basic operations in many topics such as graph minors or Wagner's theorem on planar graphs. And I'm interested in how these ...