**1**

vote

**1**answer

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

**0**

votes

**0**answers

40 views

### Probability of differently loaded dice summing to a value

I have a real world problem that boils down to the following:
I'm playing dice. I have $n \approx o(10)$ differently biased die. The probability of the $i^{th}$ die showing $x_i$ is given by ...

**1**

vote

**0**answers

15 views

### TSP: Approximation Ratio of the Double Tree Heuristic after Diagonals have been Removed

In their article "Double-Tree Approximations for the Metric TSP: Is the Best One Good Enough?", Vladimir Deineko and Alexander Tiskin derive a lower bound for the approximation ratio of the ...

**7**

votes

**1**answer

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

**3**

votes

**0**answers

91 views

### Asymptotics and combinatorics

Wright's expansion of
$$
(1-z)^b\exp[A/(1-z)^c], \text{for } A > 0, 0<c<1\tag{1}
$$
is, in the words of the late, great Mark Kac "well known to those that know it well".
(See, for example, ...

**9**

votes

**0**answers

219 views

### What is the best lower bound for 3-sunflowers?

A collection of $t$ sets $A_i$ is called a t-sunflower if $A_i \cap A_j = Z $ for all $i \neq j$ for some fixed $Z$. A well-known conjecture of Erdos and Rado says that in any $k$-uniform family of ...

**2**

votes

**1**answer

68 views

### Characterizing and counting boolean functions with all influences 1/2

Is there a characterization of boolean functions $f:\{-1,1\}^n \longrightarrow \{-1,1\}$,
so that $\mathbf{Inf_i}[f]=\frac{1} {2}$, for all $1\leq i\leq n$? Is it known how many such functions there ...

**4**

votes

**1**answer

214 views

### Existence of a certain subset of natural numbers equidistributed modulo $m$ for every $m$

I was talking to a friend and the following set $S$ came up.
Let $f$ be some real valued function tending to infinity.
Let $S$ be a subset of natural numbers such that $|S \cap [1,N]| = N^{\delta}+ ...

**3**

votes

**0**answers

44 views

### Matching in the Boolean Algebra

We consider the Boolean Algebra of the set $[n]=\{1,\dots,n\}$ and the matching $\psi$ from the $m+1$ subsets of $[n]$ into the $m$ subsets of $[n]$ for $(n+1)/2\leq m+1\leq n$, which is used to show ...

**1**

vote

**0**answers

176 views

### A generalized urn-ball matching problem; Complicated combinatoric/probabilistic limit

I'm looking for a generalization to the urn-ball matching problem. As a reminder of what I've got in mind, here's the simple version:
Randomly assign (with replacement) $N$ balls to $M$ urns. ...

**3**

votes

**1**answer

74 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

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

**-1**

votes

**0**answers

24 views

### departure time/overlap algorithm [on hold]

i'm looking for "departure time/overlap algorithm" or any other idea.
Suppose you have n trains and each one has a performance profile(how much electricity they need at the current time while driving ...

**0**

votes

**0**answers

101 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

31 views

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

Matroids have single element extensions found by Crapo[2] 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

121 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

208 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

51 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

278 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

97 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

122 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

269 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

88 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

41 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

47 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

82 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

84 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

237 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

78 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

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

**3**

votes

**1**answer

143 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

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

**34**

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

230 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

106 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

116 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

84 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

65 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$ ...

**5**

votes

**0**answers

121 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

81 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, ...