# Tagged Questions

**0**

votes

**0**answers

71 views

### Error term in formula for products of necklaces

Let us consider the $\lim_{n\to \infty}\prod_{p=1}^n N(p,a)$, where the number of fixed necklaces of length n composed of a types of beads $N(n,a)$ can be calculated via totient function: ...

**0**

votes

**0**answers

16 views

### Single element extensions of subspace arrangement over finite field

Matroids have single element extensions found by Crapo[1] to create ground set size $n+1$ matroids from ground set size $n$ matroids. Do subspace arrangements over a finite field $\mathbb{F}_q$ have ...

**0**

votes

**0**answers

113 views

### Conjecture relating differential equation and sum of a function over partitions

The following is an addition to A function from partitions to natural numbers - is it familiar?; the function $f(\lambda)$ as defined there, when summed over all partitions of n, gives an unexpected ...

**1**

vote

**1**answer

197 views

### An infinite product: combinatorial interpretation

It is an undergraduate exercise to show that the generating function for the sequence of unrestricted integer partitions $p(n)$ is the celebrated infinite product
...

**1**

vote

**0**answers

49 views

### Bases of a matroid such that their complement is an independent set

Let $M$ be some matroid on $[n]$ with set of bases $\mathcal{B}$. I am interested in the subset $\mathcal{B}' \subseteq \mathcal{B}$ of bases $b \in \mathcal{B}$ with the property that $[n] \setminus ...

**7**

votes

**4**answers

268 views

### Extremal examples for a folklore lemma on subgraphs of large minimum degree

It's a well known fact that a graph $G$ of average degree $d$ has a subgraph $G'$ of minimum degree at least $d/2$ and that the constant $1/2$ cannot be improved. The proof I know, which proceeds by ...

**0**

votes

**0**answers

60 views

### Generalized Leibniz rule for higher derivative of multiple factors [closed]

Is there a "nice" general formula that expresses the following (formal) derivative
$$\frac{d^n}{dx^n} \prod_{i=1}^N a_i(x)$$
"in terms of" the higher derivatives $a_{\nu}^{(k)}$ of each $a_{\nu}$?

**4**

votes

**1**answer

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

**1**

vote

**1**answer

118 views

### Degree Sequence Problem on $k$-Partite Graphs

The general Degree Sequence Problem asks for a simple undirected graph (that is a graph without self-loops and with no more than one edge between any pair of nodes) for which it holds that the degrees ...

**8**

votes

**3**answers

266 views

### A strengthening of Frankl's union-closed conjecture?

Frankl's union-closed conjecture states that if $F$ is a finite union-closed family of sets (i.e. a family that is closed under taking unions), then there must be an element that belongs to at least ...

**2**

votes

**1**answer

108 views

### Calculating the probability that all possible length $r$ subwords exists in a string, with or without overlaps allowed

Let $S$ be a length $L$ string, where each character in the string is chosen with uniform random probability over an alphabet with $q$ characters. For example, a binary string would imply $q = 2$, a ...

**1**

vote

**0**answers

87 views

### Combinatorial design for minimization problem over binary strings

Suppose the cost of a binary string $B$ of length $k$ is the number of $1$s that occur before the last $0$. For example, $1110$ has cost 3 while $0111$ has cost 0. Now suppose you can choose $k$ ...

**1**

vote

**0**answers

40 views

### On generating Euler Square of index q, q-1 (where q is any prime power)

Can somebody help me in generating Euler Square of index q, q-1 (where q is any prime power). Also, kidly tell me if there is any code availeble for generating the stated Euler Square. The details of ...

**0**

votes

**0**answers

45 views

### Find minimal set of progressions which intersections, unions or negations covers given set

Given an integer $N$ and a set of integers in $[1; N]$. Find a minimal set of integer arithmetical progressions such as given set can be covered using operations $A \cap B$, $A \cup B$ and $\overline ...

**-1**

votes

**0**answers

42 views

### Feature relationship based class separability [closed]

I am a computer science guy, not a mathematician so kindly excuse me if there is any ridiculous error in my problem description.
I have two clusters $C_1$ and $C_2$ in a feature space spanned by $k$ ...

**-2**

votes

**0**answers

92 views

### Paths on a Rubik's cube [migrated]

Here is the Question i'm trying to solve:
An ant is initially positioned at one corner of the Rubik's cube and wishes to go to the farthest corner of the block from its initial position. Assuming ...

**3**

votes

**0**answers

81 views

### Number cubes with consecutive line sums

This is barely of research interest, but I'd classify it as a curiosity with connections to combinatorics.
The problem is to place integers in an $n \times n \times n$ array so that all $3n^2$ line ...

**2**

votes

**1**answer

83 views

### Hitting sets (aka covers aka transversals) of Steiner triple systems

Does there exist a constant $c$ so that the lines of every Steiner
triple system on $v$ points can be covered by $cv$ points?
That is if $D \in STS(v)$ with point set $T=\{1,2,\ldots,v\}$ then ...

**7**

votes

**1**answer

234 views

### The Simultaneous Conjugacy Problem in the symmetric group $S_N$

We are interested in the following notions in the case $G=S_N$, the symmetric group on
$\{1,\dots,N\}$.
Fix a group $G$ and a number $d$. For $(g_1,\dots,g_d)\in G^d$ and $x\in G$, define
...

**2**

votes

**1**answer

68 views

### Computational complexity of deciding isomorphism of rational polyhedral cones

Let $C,C'$ be rational polyhedral cones in $\mathbb R^n$ both with non-empty interior. Rational means they are generated by vectors with rational entries. One says that $C,C'$ are isomorphic if there ...

**0**

votes

**0**answers

105 views

### Base-signed harmonic series

This question is directly related to this question by Douglas Zare.
The harmonic sequence
$$s = 1 - \frac{1}{2} - \frac{1}{3} + \frac{1}{4} - \frac{1}{5} + \frac{1}{6}+\frac{1}{7}-\frac{1}{8} - ... ...

**4**

votes

**1**answer

288 views

### Application of Combinatorics, Logic and computability theory in physical science: Tiling of Wang Tile with proportionality

The original problem of Domino Tiling and Wang Tile has great theoretical interest on computability theory... However, the great emerging problem on application of Wang Tile in material science and ...

**2**

votes

**1**answer

95 views

### Conjecture of a subset of Wang tile which might be decidable

From the two papers proving the undecidability of Wang tile in 1966 by Berger and in 1971 by RM Robinson, the tiles used in proving undecidability has a general common feature:
The left color and ...

**2**

votes

**1**answer

216 views

### A variant of Kruskal's theorem

For $X$ and $Y$ finite sequences of finite trees, let us say that $X$ is everywhere contained in $Y$ ($X\subseteq_{ec}Y$) iff, for every $y\in Y$, there is some $x\in X$ such that $x$ is a minor of ...

**32**

votes

**6**answers

2k views

### Placing numbers $1,2,\ldots,n^3$ in a cube so that numbers of any two adjacent unit subcube are coprime

This is a question first I asked in SE but since there was no suggestion or solution, I decide to put it here.
Consider an $n\times n \times n$ Cube containing $n^3$ unit cubes. Is it possible to ...

**19**

votes

**0**answers

225 views

### Which region in the plane with a given area has the most domino tilings?

I just finished teaching a class in combinatorics in which I included a fairly easy upper bound on the number of domino tilings of a region in the plane as a function of its area. So this led to ...

**1**

vote

**1**answer

103 views

### Assigning unique binary strings to the squares of a chessboard s.t. inter-string Hamming distances are the same as inter-square Manhattan distances

Consider a chessboard with $(n_1 \times n_2)$ squares, where we would like to assign a unique binary string, of some length $L$, to each square s.t. the Hamming distance between the strings ...

**3**

votes

**2**answers

114 views

### Definition of the Moebius Ladder Graph

I found two different definitions of the Moebius Ladder Graph, whose essential difference is, whether the smallest one shall be $K_4$ or $K_{3,3}$.
according to Wikipedia ...

**2**

votes

**2**answers

111 views

### Which graphs generate a matroidal independence complex?

The independence complex $I(G)$ of a graph $G=(V,E)$ has as point set the vertex set $V$ and as simplices the independent sets of $G$.
Now, if $G$ is a well-covered graph (where all maximal ...

**0**

votes

**0**answers

39 views

### Almost symmetric route in digraphs

Let $D=(V,E)$ be a digraph. A route of length $k$ in $D$ is a pair $L=(S,\sigma)$, where $S=(s_1,s_2,\dots,s_{k+1})$ is a sequence of $k+1$ elements of $V$, and ...

**14**

votes

**1**answer

1k views

### What have simplicial complexes ever done for graph theory?

(I am asking in a somewhat tongue-in-cheek fashion, of course, but nevertheless...)
Are there examples of results in "classical" [*] graph theory that have
been achieved by using simplicial ...

**1**

vote

**0**answers

83 views

### Arctic Circle Theorems and the Wave Equation

I've seen the following remark in a number of papers but don't know what to make of it. In this paper by Cohn, Elkies and Propp, it is mentioned that the normalized average Height function ...

**17**

votes

**3**answers

2k views

### Where in mathematics do these polynomials appear?

Does anyone recognize the following sequence of polynomials?
$f_0(x) = x-1$
$f_1(x) = x^2-x$
$f_2(x) = x^4-2x^2+x$
$f_3(x) = x^8-3x^4+3x^2-x$
$f_4(x) = x^{16}-4x^8+6x^4-4x^2+x$
$\vdots$
The ...

**2**

votes

**1**answer

64 views

### Point-Hyperplane incidence in finite projective spaces

Let $P$ be a finite projective space of order $q$ and dimension $d$. I am interested in finding the least $k$ such that for any set $S$ of $k$ points of $P$, and for any set $S'$ of $k$ hyperplanes of ...

**1**

vote

**1**answer

97 views

### The edge chromatic number and pefectness of inflation of cubic graph

The inflation of graph $G$ is a graph $I(G)$
which is obtained by replacing each vertex $x$ by a complete graph
$K_{\deg(x)}$ and joining each edge to a different vertex of $K_{\deg(x)}$.
Let $G$ ...

**3**

votes

**0**answers

110 views

### Is Euler-characteristic of a simplicial complex on $n$ vertices and $f$ facets at most $n^{O(\log f)}$?

(Definition: Facet = Maximal Face)
This question is a continuation of the previous one that I had asked a couple of years ago: Is Euler characteristic of a simplicial complex upper bounded by a ...

**2**

votes

**1**answer

79 views

### On a conjecture by Hibi regarding h-vectors

For integral polytopes, it is conjectured (T. Hibi), that if the $h^*$-vector is symmetric, then it is also unimodal (increasing, then non-decreasing).
A non-integral polytope do not, in general, ...

**4**

votes

**1**answer

163 views

### Do graphs with large number of paths contain large chain minor?

Definition: A "$k$-chain" is a multi-graph obtained from a path of length $k$ by duplicating every edge.
Note that the number of paths between two endpoints of a $k$-chain is $2^k.$
Question: Let ...

**4**

votes

**2**answers

150 views

### Joint probability distribution as functions

Suppose $X$ and $Y$ are correlated random variables in a finite set ${\mathcal A}$, and let $f, g$ be functions that map elements from ${\mathcal A}$ to ${\mathcal B}$ for some finite set ${\mathcal ...

**2**

votes

**2**answers

755 views

### Number of 1 in binary representation of n

Let $1(n)$ be the number of digits $1$ in binary representation of number $n$.
For example, $13=1101_2$ so $1(13)=3\\$
Is there explicit form of $\,\,\sum{1(i)x^i} $?
I checked OEIS and didn't find ...

**1**

vote

**0**answers

99 views

### Knight's metric: ellipse and parabola

Knight's metric is a metric on $\mathbb{Z}^2$ as the minimum number of moves a chess knight would take to travel from $x$ to $y\in\mathbb{Z}^2$. What does a parabola (or an ellipse) became with this ...

**3**

votes

**0**answers

102 views

### What is the combinatorial data classifying non-normal affine toric varieties?

Recall that a toric variety is a variety $V$ containing an open dense algebraic torus. Here an algebraic torus means a finite product of copies of the multiplicative group of the ground field (which I ...

**2**

votes

**0**answers

121 views

### Number of kxk matrices whose rows and columns are permutations

Let $\sigma_1,\ldots, \sigma_k$ be permutations of $\{1,2,\ldots,k\}$. I want to determine the number of $k$-tuples $(\sigma_1,\ldots, \sigma_k)$ of permutations such that, for each $1\leq j\leq k$, ...

**0**

votes

**0**answers

82 views

### Database of non-isomorphic trees

As there are several free prime number databases, is there something similar for non-isomorphic trees?

**8**

votes

**1**answer

389 views

### Is there an interesting species whose generating function gives the zigzag numbers?

Let's say a species is a functor
$$F: \mathrm{FinSet}_0 \to \mathrm{FinSet}_0$$
from the groupoid of finite sets and bijections to itself. Let $F(n)$ be its value on your favorite $n$-element ...

**0**

votes

**0**answers

53 views

### Partitions contained in staircase shape

Let $\lambda_n=\{n-1,n-2,\dots,1\}$ be a partition of staircase shape. Let $f(n,k)=\#\{|\mu|=k|\mu\leq\lambda_n\}$ and $g(n,(i,j))=\#\{\mu|(i,j)\notin \mu,~\mu\leq \lambda_n\}$, where $(i,j)$ denotes ...

**6**

votes

**1**answer

188 views

### maximum size of intersecting set families

Suppose $n$ is a big number and $k\geq 2$. How many sets $S_1,\dots,S_m\subset [n]$ can we find such that
(1) $|S_i| = k$ for all $i$,
(2) $|S_i\cap S_j| \leq 1$ for all $i\ne j$.
What's the maximum ...

**1**

vote

**0**answers

50 views

### Point sets with tangents through every point

Let $D=(P,L)$ be either a $(v,k,\lambda)$-design or a near-linear space (or, more generally, any incidence structure with "points" and sets of points which are called "blocks" or "lines") and let $S ...

**5**

votes

**1**answer

149 views

### The number of partitions between two fixed partitions

Given two partitions M and N, with $M_i \leq N_i$ for all $1\leq i\leq \max\{l(M),l(N)\}$. Is there a formula for the generating function: $$\sum_{\lambda: M_i\leq \lambda_i\leq N_i} ...

**-1**

votes

**1**answer

235 views

### Does anyone recognize this generating function [closed]

$a_1=1, a_2=1, a_3=3, a_4=15, a_5=105$
Reccurence formula is
$a_{k+1}=\sum\limits_{\lambda_1+\lambda_2+\ldots+\lambda_s=k,\ \lambda_i\geq1} a_{\lambda_1}a_{\lambda_2}...a_{\lambda_s}{k \choose ...