# Tagged Questions

**0**

votes

**0**answers

116 views

### Non existence (or existence) of a set that is equidistributed modulo $q$ for every $q$

I have been thinking about some set that is equidistributed modulo $q$,
uniformly in $q$ in some sense. I was starting to think this particular condition, which I describe below, is too strong and ...

**0**

votes

**1**answer

76 views

### Generalized Helly theorem for $t$-intersecting families

Given a family $\mathcal{F}$ of sets over ground set $X$, let $\tau(\mathcal{F})$ be the transversal number (aka blocking number), that is the cardinality of the smallest set of points $E \subseteq X$ ...

**4**

votes

**3**answers

245 views

### Number of binary vectors of a given Hamming weight in a subspace of the Hypercube

Let $n$ be a natural number.
Let $U \subseteq \mathbb{F}_2^n$ be a linear subspace of dimension $k$.
What is the maximum number of vectors in $U$ of Hamming weight $\ell$?
The case I am specifically ...

**1**

vote

**0**answers

68 views

### Inverse of matrix of generalised harmonic numbers

For $s=0,1,\dots$ and $n=1,2,\dots$, denote $r_{n,s}=\sum_{k=1}^n k^s$. It is well-known that $r_{n,s}$ are polynomials in $n$ with leading term $\frac{1}{s+1}n^{s+1}$. Let $R_{n,s}$ be the ...

**4**

votes

**0**answers

91 views

### A question on hyperplanes in partial linear spaces and hypergraphs

A partial linear space (or a linear hypergraph) is a point line geometry $(P,L,I)$ where for every pair of points there is at most one line incident with both of them. A hyperplane in a partial linear ...

**6**

votes

**5**answers

575 views

### What makes a set random?

There are many results in number theory, where the existence
of some $B \subseteq \mathbb{N}$ with certain properties is proved by
a probabilistic argument employing "random sets". One such example
...

**3**

votes

**0**answers

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

**2**

votes

**1**answer

133 views

### Is there a bijection from indecomposable to irreducible set partitions?

A partition of $[n]$ is indecomposable if no subset of its blocks partitions $[k]$ with $k \in [n-1]$. Irreducible set partitions are defined at http://oeis.org/A055105 . Both are counted by ...

**1**

vote

**1**answer

68 views

### planar bipartite cubic graph

Suppose we have a cubic planar bipartite graph with no double edges. I am looking for a statement about the minimal distance between the square faces (shortest path from a vertex on the first square ...

**1**

vote

**1**answer

147 views

### Question about the theory of combinatorial species

The definition of a (combinatorial) species $F$ emphasizes that any bijection $\phi\, :\, A \to B$ between support sets $A$ and $B$ must induce a bijection between $F[A]$ and $F[B]$ (the ...

**16**

votes

**2**answers

343 views

### Shortest supersequence of all permutations of $n$ elements

Given an alphabet with $n$ characters, what is the shortest sequence that contains all $n!$ permutations as subsequences?
A subsequence can be obtained from a sequence by deleting any characters, ...

**2**

votes

**0**answers

301 views

### The twisted kiss of the curvaceous cubic and the staid tetrahedron (references)

(Migrated from MSE)
While investigating some operators, I came across some relations between the twisted cubic curve and the tetrahedron that link together some notions in differential geometry, ...

**1**

vote

**0**answers

111 views

### Relationship betwen eigenvectors

Suppose that we have two matrices A and B. Matrix B is taken from A with one row and one column deleted. On the other hand A is n*n matrix and B is (n-1)*(n-1) matrix and is created by deleting last ...

**5**

votes

**0**answers

174 views

### Is it always optimal to evenly split search space in Rényi-Ulam game?

Suppose that we want to find one of finitely many elements (called pivot) by asking binary questions (one after the other) of which for at most $e$ we might get an incorrect answer and our goal is to ...

**7**

votes

**1**answer

137 views

### Distribution of entries of a doubly-sorted random matrix

Take an $n \times n$ random matrix whose entries are i.i.d. with uniform distribution in $[0,1]$. Look at the sums of the elements of each row and then permute the rows so that these sums form an ...

**10**

votes

**1**answer

277 views

### Explicit algorithm for composing permutations in factorial notation

Given two permutations p1 and p2 in factorial notation, is there an algorithm which computes their composition directly, i.e. without translating to a different notation (like Cauchy's 2-line ...

**1**

vote

**0**answers

118 views

### How to prove this identity? (Perhaps related to partition) [closed]

How to prove this identity?
$ \sum_{n\ge 0} \frac{x^{n^2}}{(1-x)(1-x^2)\cdots(1-x^n)}= \frac{1}{\prod_{k \ge 0}(1-x^{5k+1})(1-x^{5k+4})}$
I will appreciate it a lot if a solution using method ...

**3**

votes

**0**answers

119 views

### characterization of all periodic tiling of a simple set of Wang Tile

Consider a set of Wang Tile such that all the edges are either 1 or 0.... there are 16 elements in such a set.
Now, I wish to characterize all the periodic tilings of this set (better if they are ...

**10**

votes

**1**answer

466 views

### Where can I find Gonthier's Coq code proving the four color theorem?

In a 2008 article in the Notices, Georges Gonthier announced a computer-checked proof of the four color theorem using Coq:
Gonthier, Georges. Formal proof—the four-color theorem.
Notices Amer. ...

**13**

votes

**1**answer

283 views

### partition of infinite word onto permitted words

Consider words over binary alphabet $\{0,1\}$. Let $M$ be a set of finite words such that $M$ contains at least $c\cdot 2^n$ words of length $n$ for all large enough $n$ (for a constant $c$, ...

**3**

votes

**0**answers

85 views

### Sets of polynomials with restricted set of products

Let $F = \{f_1, ..., f_n\}$ be a set of distinct monic polynomials (and thus also $f_i^2$ are distinct). Let $F' = \{f_i f_j: i \neq j\}$ be the set of pairwise products of all distinct elements from ...

**5**

votes

**1**answer

248 views

### Grassmann-Plücker relations for permanents

Let $K$ be a field, $1 \leq d \leq n$ integers and $V$ an $n$-dimensional vector space. The Grassmann-Plücker relations are quadratic forms on $\wedge^d V$ whose zero set is exactly the set of ...

**4**

votes

**2**answers

311 views

### A question about pairs of lines in 3D projective space

Consider a 3-dimensional projective space $X$.
Let $m$ be the smallest number so that there are $m$ pairs of lines
$ \ell_1,\ell'_1$, $ \ell_2,\ell_2'$, ... , $\ell_m, \ell'_m$ in $X$:
a) For ...

**3**

votes

**1**answer

115 views

### Cayley graph which is isomorphic to the line graph of a complete graph

From the literature, we know that the line graph of a complete graph $L(K_{q})$ is a Cayley graph if and only if $q \equiv 3$( mod 4) is a prime power. Now, if $q \equiv 3$( mod 4) is a prime power, ...

**2**

votes

**1**answer

144 views

### relationship between corner tile and edge tile of wang tile

It is clear that any corner type of Wang Tile could be converted to edge type of Wang Tile by defining the edge color according to the corner color.
However, could we convert edge type of Wang Tile ...

**0**

votes

**0**answers

182 views

### A sum of binomial coefficients

Let
$$
a_{i,j} = \binom{i+j}{i}\binom{2n-(i+j)}{n-i}.
$$
I want to (asymptotically in $n$) compute
$$
\sum_{i=0}^{n}\sum_{j=0}^{n} a_{i,j}^2.
$$
Is there an easy way to do this? Are there generating ...

**7**

votes

**1**answer

443 views

### Number of walks

How many walks (asymptotically) of length $2n$ with up or right steps from $(0,0)$ to $(n,n)$ are there such that the walk is always between the lines $y=x+k$ and $y=x-k$?

**2**

votes

**1**answer

133 views

### Maximal number of antichains of a connected poset

Assume we have a connected poset $P$ of $n$ elements, I am searching to know what is the maximal number of antichains such a poset can have?
$2^n$ is obviously an upper bound, and my feeling is that ...

**7**

votes

**0**answers

102 views

### Ordering subsets of the cyclic group to give distinct partial sums

Suppose that you are given a set $S$ of $k$ nonzero elements from $\mathbb{Z}_n$. Is it always possible to order the elements of $S$, say $a_1,a_2,\dots,a_k$ in such a way that the partial sums ...

**0**

votes

**0**answers

115 views

### Maximal “Spot It!” card count

This question was triggered by the game Spot It!.
The game consists of cards, each having $k$ different symbols from an alphabet of $n>k$ symbols, with the property that any 2 cards have at least ...

**8**

votes

**3**answers

514 views

### Changing combination lock [closed]

Suppose you have a combination lock (n digits, m symbols) that is unlocked by one specific n-digit key sequence. However, trying a wrong key changes it according to an fixed but unknown function: new ...

**2**

votes

**1**answer

252 views

### Bound for a combinatorial sum

I was playing around with a problem and I obtained a certain
combinatorial sum. I was wondering if there was a way to simplify or bound it.
I have a real valued function $f$, which satisfies $|f(x)| ...

**3**

votes

**0**answers

101 views

### Triangulations of special polyhedra

Let $A_1,A_2,A_3 \in \mathbb{N}^3$ be three points in space all lying in some plane $x+y+z=d$ where $d$ is a positive integer. If $\{e_1,e_2,e_3\}$ is the standard basis in $\mathbb{R}^3$, we can ...

**0**

votes

**1**answer

83 views

### Collecting terms of a linear expression with nested sums and combinatorics in coefficients

I need to collect the $\Pr(\cdot)$ terms of the following expression:
$\sum_{m=3}^{n}\frac{g_{m}\left( \cdot \right) }{\left( \sqrt{\theta \left(
1-\theta \right) }\right) ^{m}}\left[ ...

**4**

votes

**2**answers

343 views

### Can we sometimes define the parity of a set?

Suppose that ${n\choose k}, {n-1\choose k-1}, \ldots, {n-k+1\choose 1}$ are all even. (This happens for example if $k=2^\alpha-1$ and $n=2k$.) In this case, can we select ${n\choose k}/2$ sets of size ...

**5**

votes

**1**answer

345 views

### Are semigroups with finite-to-one right multiplication “moving”?

A semigroup $S$ is moving if $S$ is infinite, and for all finite
$F\subseteq S$ and infinite $A\subseteq S$, there are $a_{1},\dots,a_{k}\in A$ such that,
for all but finitely many $s\in S$,
$$
...

**3**

votes

**0**answers

55 views

### Maximal $k$-chordal subgraph

Recall that a graph is called $k$-chordal if any cycle $C$ of length $> k$ contains a chord, i.e. an edge joining to non-consecutive vertices in $C$. Let $f(n, k)$ be the minimal number of edges ...

**2**

votes

**1**answer

127 views

### Looking for a canonical (matroid polytope) subdivision of the hypersimplex

A matroid polytope is the convex hull of the indicator vectors of the bases of a matroid, and a matroid polytope subdivision (MPS) is a polyhedral subdivision of a matroid polytope whose cells are ...

**3**

votes

**1**answer

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

**1**

vote

**0**answers

37 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

163 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

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

**13**

votes

**0**answers

531 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 there is a constant $C_t$ such ...

**5**

votes

**5**answers

260 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

277 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

**1**answer

110 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

**1**answer

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

**4**

votes

**1**answer

182 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

98 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**

vote

**0**answers

212 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: ...