Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.

learn more… | top users | synonyms (1)

1
vote
1answer
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
1answer
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
2answers
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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
2answers
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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
2answers
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
2answers
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
1answer
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
1answer
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
0answers
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
1answer
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
3answers
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
0answers
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
1answer
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
2answers
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
0answers
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
1answer
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 ...