# Tagged Questions

**2**

votes

**1**answer

132 views

### A number array related to colored necklaces and the primes

I stumbled upon entry OEIS-A208535 on the enumeration of certain kinds of colored necklaces and noticed that the integers for the odd prime rows of the table there seem to be given by the Moreau ...

**1**

vote

**1**answer

148 views

### A generalisation of Narayana-like numbers (walks on the 2D lattice)

I apologize in advance if this question has a trivial answer. I am pretty sure this kind of problem was already studied and I am mostly asking for good references.
Given integers $0 < k \le n+1,$ ...

**13**

votes

**2**answers

352 views

### What is the minimal $C_k$, such that every $f\colon \{-1,1\}^n\to \mathbb{R}$ of degree at most $k$ satisfies $\|f\|_2\le C_k\|f\|_1$

Every $f\colon\{-1,1\}^n\to \mathbb{R}$ can be repsenented as a multilinean polynomial of the form $$f(x_1,x_2,\ldots ,x_n)=\sum _{S\subseteq [n]} \hat{f}(S)\prod_{i\in S} x_i $$ The degree of the ...

**1**

vote

**0**answers

100 views

### current status of combinatorial optimization solvers [closed]

What is the current status of the solvers in combinatorial optimization? For example, what is the "usual feasible size" for a traveller sale's man problem, say, how many nodes and edges are "usually ...

**6**

votes

**1**answer

177 views

### Some polytopes in $\mathbb R^n$ whose vertices have coordinates 1, -1 or 0

Let $n$ and $k$ be positive integers with $k\leq n$.
Let $P(n,k)$ be the convex hull in $\mathbb R^n$ of the $2^k {n \choose k}$ vectors whose exactly $k$ coordinates belong to $\{\pm 1\}$ all the ...

**3**

votes

**0**answers

74 views

### Counting Problems where Labeled is Known but Unlabeled is Not

Cayley's formula states that the number of labeled trees on $n$ vertices is $n^{n-2}$. There are many nice proofs of this compact formula.
To contrast, counting unlabeled trees is considerably ...

**4**

votes

**2**answers

135 views

### open question on intersecting rectangles - reference request

In the now-inactive (and very nice) "Tricki" website that describes various proof techniques, there is an article (written I think by Timothy Gowers) that describes the following Ramsey-type problem:
...

**2**

votes

**0**answers

137 views

### Dissection of a polygon into convex polygons

Problem: for a fixed integer $m\geqslant 3$ find all $n$ such that no $n$-gon can be dissected into convex $m$-gons.
I would be very grateful for any information on this problem.
Remark 1. There ...

**5**

votes

**0**answers

69 views

### Bound on the number of lattice points in d-dimensional ball

The following paper states that the number of lattice points in a $d$-dimensional ball of radius $R$ is $V_d R^d + O(R^\alpha)$ where $\alpha = d - 2$ and $V_d$ is the volume of the unit ...

**1**

vote

**1**answer

51 views

### A possible minimal aperiodic set of corner Wang Tile

From one of my previous question Aperiodic set of corner Wang Tile (although it is put on hold), I realize there is a systematic way to construct aperiodic corner type of Wang tile from edge type ...

**1**

vote

**2**answers

232 views

### Embed one Coxeter System into another

What is a good reference that explains all the braid relations and diagrams for Coxeter systems concisely?
In particular, how do I embed $H_3$ inside $D_6$, or $H_4$ inside $E_8$? Any hints?

**0**

votes

**0**answers

46 views

### Calculating the longest Bracelet(s) Common to a Set of Bracelets

I would like to know, if the following problems has been studied before:
let $\{B_1, ..., B_n\}$ be a set of Bracelets with the same set $\{\beta_1, ..., \beta_k\}$ of beads,
what is the ...

**6**

votes

**1**answer

277 views

### About an identity which gives immediate proof of the permanent lemma

Let $A$ be a $n \times n$ matrix over field $F$. Let $a_1, \cdots, a_n$ be the column vectors of $A$. For any subset $S \subseteq [n] = \{1, 2, \cdots, n\}$, let $a_S = \sum_{i \in S} a_i$. Alon's ...

**2**

votes

**0**answers

62 views

### Reference for MacMahon on Overpartitions

In the literature on overpartitions Percy A. MacMahon is usally cited as the genesis of the theory. Often the reference is to his 1916 textbook -- but, having recently checked this out of my school's ...

**5**

votes

**2**answers

173 views

### What is known about tiling a rectangle in an irreducible way by smaller rectangles?

Given two naturals $s<t$. Is there always a square (or at least a bigger rectangle) that can be tiled with $s\times t$ rectangles in an irreducible way (i.e. any grid line splitting it cuts at ...

**2**

votes

**1**answer

174 views

### A parametrization of subsets

Suppose $I\subseteq\{1,\dots,n\}$, and let $\{1,\dots,n\}\setminus I=\{j_1,\dots,j_m\}$ be an enumeration of the complement of $I$ with $j_r<j_{r+1}$ for each $r\in\{1,\dots,m-1\}$. To $I$ I can ...

**1**

vote

**0**answers

32 views

### Generalizing Concepts of Planar Euclidean Geometry to Symmetric TSP-Instances

To me it seems possible, to successfully look at symmetric TSP instances from a geometry-point of view.
Examples are:
the diagonals of the convex hull of a set of points in the euclidean plane; ...

**9**

votes

**4**answers

808 views

### Ordinary Generating Function for Bell Numbers

In the OEIS entry for Bell numbers, there appears a generating function
$$\sum_{k=0}^\infty B_k t^k = \sum_{r=0}^\infty \prod_{i=1}^r \frac{t}{1-it}$$
However, I could not locate any proof of ...

**0**

votes

**0**answers

83 views

### Transversal theory in ergodic theory

I was taking a glance at the original paper by Donald Ornstein, Bernoulli Shifts with the Same Entropy are Isomorphic, and I came across The Marriage Problem and a paper with the same name by P. ...

**1**

vote

**1**answer

93 views

### maximal chain in (strong) Bruhat order satisfying constraint

Consider the (strong) Bruhat order, $\leq_B$, on the symmetric group $S_n$. Suppose there are permutations $\pi,\sigma∈S_n$ such that $\pi\geq_B \sigma$. Suppose further that they satisfy the ...

**18**

votes

**3**answers

619 views

### Number of primitive $n$th roots with positive versus negative real parts

Does anyone know a reference to the following results, which I can prove, but I suspect may be known. Let $R(n)$ denote the number of primitive $n$th roots of unity with positive real part, and $L(n)$ ...

**1**

vote

**0**answers

72 views

### Empty node in cactus construction

Is there a necessary condition for not having empty node in the construction of the cactus of the minimum cuts of a graph?
In particular is there a necessary condition for not having empty k-junction ...

**3**

votes

**2**answers

145 views

### Asymptotics of the number of elements in the intersection of two growing sets

Let $[n]:=\{1,\dots,n\}$ and $0\leq p_n\leq n$. Fix any subset $A_n$ of $[n]$ with $p_n$ elements. The number of subsets $B$ of $[n]$ with $p_n$ elements that are disjoint from $A$ is ...

**2**

votes

**1**answer

93 views

### Estimate for the travelling salesman problem for balls inside a grid

This question is probably easy but I only have "tedious case checking" proof strategy in sight, and I'm sure there should be a reference lying around...
The question concerns the TSP problem (with ...

**5**

votes

**1**answer

408 views

### A generalized Burnside's lemma

Let $G$ be a finite group acting on a set $X$, and let $S\subseteq G$ be a union of conjugacy classes. Then I believe I can prove:
$$ \sum_{[x]\in X/G} \frac{|G_x \cap S|}{|G_x|} = \sum_{g\in S} ...

**1**

vote

**1**answer

157 views

### Name search for special Linear Integer Program

I am looking for a name for the following question in literature!
(and if you know it, then it would be great)
I couldn't find it and due to wide audience here, presumably you know more. Thank you
...

**2**

votes

**0**answers

52 views

### Generalized separating systems

We call a set system $\mathcal{A}$ of subsets of the $n$ element universe $U$ a separating system if for any pair of elements $x,y \in U$ there is at least one set $A \in \mathcal{A}$ such that either ...

**3**

votes

**3**answers

289 views

### Time-inhomogeneous Markov Chains

I'm trying to find out what is known about time-inhomogeneous ergodic Markov Chains where the transition matrix can vary over time. All textbooks and lecture notes I could find initially introduce ...

**2**

votes

**3**answers

740 views

### An established proof in Wang Tile which I doubt

When I was reading the paper:
Wang, Hao. "Notes on a class of tiling problems." Fundamenta Mathematicae 82.4 (1975): 295-305.
from http://matwbn.icm.edu.pl/ksiazki/fm/fm82/fm82119.pdf
I could not ...

**1**

vote

**1**answer

107 views

### Formula for the Ordinal Number of k-Sets of Positive Integers

Background of my question is, that I would like to store flags indicating the relation between a pairs of non-adjacent edges of a graph (that relation could for example be, whether the edges cross, ...

**3**

votes

**0**answers

78 views

### Orthogonal basis for the multilinear polynomials with zero “trace”

We say that a multilinear polynomial $P(x_1,\ldots,x_n)$ in $n$ commuting variables over $\mathbb{R}$ has zero trace if
$$ \frac{d}{dt} P(t,\ldots,t) = 0. $$
Equivalently,
$$ \left(\sum_{i=1}^n ...

**3**

votes

**1**answer

155 views

### Proof of existence of recursively inaccessible and Mahlo ordinals

As in title - I'm looking for a proof of the existence of a countable recursively inaccessible or recursively Mahlo ordinals, especially the first one. When looking for it in all the papers I stumbled ...

**7**

votes

**1**answer

164 views

### What is the Essential Reason that allows a PTAS for the EUCLIDEAN TSP?

Questions:
Is there some understanding of the reason, why the euclidean TSP allows a PTAS, whereas the metric TSP in general does not and, is the PTAS stable under sufficiently small perturbation ...

**4**

votes

**1**answer

195 views

### Extremal graph theory for directed graphs

In extremal graph theory, there are results such as
$$t(C_4,G)\geq t(K_2,G)^4,$$
where $G$ is an undirected graph, $C_4$ is a cycle graph on 4 nodes, $K_2$ is a complete graph of $2$ nodes, and ...

**3**

votes

**1**answer

99 views

### Reference for Frobenius’s proof of Schur’s finite version of the Rogers - Ramanujan identities

In his paper “Ein Beitrag zur additiven Zahlentheorie und zur Theorie der Kettenbrüche” I. Schur has stated that Frobenius has communicated to him a simple direct proof of his finite version of the ...

**4**

votes

**1**answer

148 views

### Generalized permutahedron and random polytopes

The Birkhoff polytope $B_n$ is defined as the convex hull of the set of permutation matrices, which gives us the set of doubly stochastic matrices. A concept which is intimately related is that of the ...

**5**

votes

**1**answer

116 views

### References to proofs of a theorem by Van Kampen-Flores

Theorem (Van Kampen-Flores 1930s) From any 7 points in four-dimensional space one can choose two disjoint triples such that the triangles with vertices at the triples intersect each other.
This ...

**1**

vote

**0**answers

158 views

### An extrasensory perception strategy :-)

I asked this question at MSE some months ago
but I received only partial answers, so I put it here. The following sounds nice for me and I spent a good time during the investigation. But I am a ...

**4**

votes

**0**answers

66 views

### Reference for statement that almost every $n$-element partial order has trivial automorphism group

I'm looking for a reference for the statement that almost every partial order on $n$ elements has trivial automorphism group. I've been told that this is a folklore result. Does anyone know of a ...

**5**

votes

**0**answers

71 views

### Classifying two-faces of four-polytopes

Motivation: This question is related to my study of hyperbolic Coxeter polytopes. In general, if one put some restrictions on the type of their dihedral angles (say, all dihedral angles are equal to ...

**5**

votes

**1**answer

343 views

### Flow of an integer

I've stumbled across this family of flow networks, and posted the sequence of maximal flows to OEIS: A238729. I can't find any reference to it either. Has anyone seen it?
Here is the description:
...

**16**

votes

**3**answers

2k views

### Silly me & Van der Waerden conjecture

So I walked into this very innocent-looking combinatorics problem,
and quite soon I ended up with the problem to prove that any doubly stochastic $n \times n$ matrix has a non-zero permanent.
Now ...

**4**

votes

**1**answer

194 views

### Is Van der Waerden's function elementary

Van der Waerden's function was proved to have elementary upper bound on growth rate.
Is the Van der Waerden's function itself elementary in the sense of Kalmar?

**3**

votes

**3**answers

355 views

### Estimating a sum involving binomial coefficients [refined]

Having some work done, here is a refined version of my initial question.
For integer $m>0$ and $0\le q\le m$, consider the sum
$$ S(m,q) = \sum_{i=0}^{m-q} \binom{m}{i} \binom{m-i}{q}^2. $$
I ...

**6**

votes

**1**answer

160 views

### What is/are the best bound/s on the sum of squares of degrees in a graph?

Let $G$ be a graph with degrees $d_{1},\ldots,d_{n}$. I am interested in upper bounds on
$$
\sum_{i=1}^{n}{d_{i}^{2}}.
$$
An example is de Caen's bound:
$$
\sum_{i=1}^{n}{d_{i}^{2}} \leq ...

**6**

votes

**0**answers

112 views

### What is the mobius function for the set of simplicial complexes on n vertices?

Consider the set of simplicial complexes on $n$ vertices, with partial ordering by containment. What is the Mobius function for this poset?
Are other combinatorial facts known about it (e.g. the ...

**1**

vote

**1**answer

204 views

### Is this Graph parameter known?

Let $\lambda(G)$ denote the edge-connectivity of $G$.
Consider the following parameter:
$\rho(G) = \max_{X \subset V(G)} \min(\lambda(G[X]), \lambda(G[V(G) - X]))$
Has this parameter been studied? ...

**8**

votes

**2**answers

649 views

### How to find counterfeit coins by weighing

In one variant of the classic counterfeit coins problem you are given a bag of $n$ numbered but otherwise identical looking coins and a scale and your job is to find which coins are counterfeit. ...

**6**

votes

**1**answer

101 views

### Maximizing ratio volume/diameter^n by an affinity

Suppose we have a convex compact body $D\subset \mathbb R^n$. We can try to apply affine transformation keeping the volume and decreasing the diameter of $D$.
It is clear that there is a constant ...

**1**

vote

**0**answers

42 views

### complexity of in-dominating set

Is the decision problem In-Dominating Set NP-complete for digraphs of regular out-degree (greater than (n-2)/4, in particular)? I'm mainly looking for the reference.
Thanks for any answer!