**13**

votes

**0**answers

387 views

### Chasing a 1950s thesis from the University of Dhaka on block designs

On behalf of a friend I am searching for a thesis on block designs from the 1950s. The details are below.
Author: Qazi Motahar Husein (Sometimes Husain or Hussein).
Title of the Thesis: Symmetrical ...

**3**

votes

**0**answers

38 views

### Weighted matching and spanning set in $2$-polymatroids

A $2$-polymatroid $P$ is a pair $(S, f)$, where $S$ is a finite set and $f: 2^{S} \rightarrow \mathbb{Z}$ is a function satisfying the following:
$f(\varnothing) = 0$;
$f(X) \leq f(Y)$, for any $X ...

**8**

votes

**3**answers

573 views

### What is the optimal size in the finite axiom of symmetry?

Freiling's axiom of symmetry states that if you assign to each real number $x$ a countable set $A_x\subset\mathbb{R}$, then there should be two reals $x,y$ for which $x\notin A_y$ and $y\notin A_x$.
...

**1**

vote

**0**answers

48 views

### How to count the number of shortest paths in a 2x2 grid? [closed]

Say that we have a 2x2 regular grid or network. We label the nodes 0 to 3 row-wise. Then, for each node, we want to compute the number of shortest paths that pass through them.
I have a Python code ...

**4**

votes

**0**answers

46 views

### Looking for a Collection of Examples and Counter Examples for Assumptions about the Properties of Planar Euclidean TSP Instances?

Where can I find example and counter examples to seemingly plausible assumption about the properties of optimal solutions of planar euclidean TSP instances?
The reason for asking is that the ...

**1**

vote

**0**answers

71 views

### An optimal lower bound related to generators in a boolean interval of finite groups

Let $[H,G]$ be a rank $n$ boolean interval of finite groups (i.e. $[H,G] \simeq B_n$ as lattice).
Let the set $E = \{ g \in G \ | \ \langle H,g \rangle = G \}$
Remark: If $g \in E$ then $Hg \...

**11**

votes

**2**answers

284 views

### Tableaux with limited rows and complementary skew shapes

Given a partition $\mu=(\mu_1,\mu_2...,\mu_d)$, define $\bar\mu=(\mu_1-\mu_d,\mu_1-\mu_{d-1},...,\mu_1-\mu_2,0)$, the complementary shape in the $d\times \mu_1$ rectangle. Then the number of skew ...

**5**

votes

**0**answers

164 views

### A question on symmetric functions

Let $0 \leq m \leq n$ be integers. The group $S_n$ of permutations acts on the ring $\mathbb{Z}[X_1,\dots,X_n]$ by permuting the coordinates, with fixed subring $\mathbb{Z}[\sigma_1,\dots,\sigma_n]$, ...

**12**

votes

**0**answers

173 views

### Reference request: exponential growth rates of subword-closed languages are integers

For a language $L$ over the finite alphabet $\Sigma$, let $L_n$ denote the set of words in $L$ of length $n$. The word $u$ is a subword of $w$ if $u$ can be obtained from $w$ by deleting letters. The ...

**2**

votes

**0**answers

89 views

### Growth of inner products between two random vectors on the sparse hypercube

We define the $s$-sparse hypercube in $\mathbb{R}^d$ as
\begin{align}
\mathbb{H}_s = \bigl \{ {\bf{v}} \in \{ -1, 0 , 1\}^d \colon \| {\bf{v}} \|_0 = s \bigr\},
\end{align}
where $ \| {\bf v} \|_0 $ ...

**12**

votes

**2**answers

209 views

### Permutation search problems with no known $o(n!)$ algorithms

I am looking for problems for whose solution no known subfactorial algorithms are known. I am particularly interested in questions of isomorphism; that is, is there a permutation that converts one ...

**2**

votes

**0**answers

53 views

### What do you call the collection of all sets shattered by $F$?

The proof of Pajor's lemma uses the collection of all sets $S\subseteq X$ shattered by some $F\subseteq 2^X$. Is there a standard term for the former object? I've been privately referring to it as the ...

**2**

votes

**0**answers

66 views

### Batched coupon collector with quota

Assume that you draw coupons uniformly at random from a collection of $n$ coupons and you want to collect $m_i$ coupons of type $i$. This is referred to as the coupon collector with quota (http://www....

**3**

votes

**1**answer

72 views

### Density of permutation of syndetic sets of integers

Define the upper uniform density of a set $A\subset\mathbb{Z}$ to be
$$
D^+(A)=\lim_{r\rightarrow\infty}\sup_{a\in\mathbb{R}}\frac{|A\cap[a,a+r)|}{r}
$$
Fix an arbitrary permutation of the integers $\...

**3**

votes

**0**answers

96 views

### Minimization module $p$

Let $p$ be a prime number, let $m$ be a fixed number (for example $2^{20}$), and $i=k^{-1}\cdot (j-t) \pmod{p}$ where $j \leq m$ and $m<k$.
In the general case we have $t=0$, and $k,j$ are ...

**1**

vote

**0**answers

32 views

### computational-expensive signal reconstruct - a combination problem [closed]

My problem is:
I have a time series signal (vibration signal), use BSS algorithm (Blind Source Separation, we can regard it as a black box), separate the source signal into 100 components.
Now I ...

**4**

votes

**1**answer

127 views

### Maximum size of minimal sequence of transpositions whose product is a given permutation

Consider the sequence $S = 1,2,3,\ldots n$ of elements, along with a sequence $T = t_1, t_2, \ldots, t_m$ of transpositions. Each transposition $t_i$ is a tuple $(a_i, b_i) \in [n]^2$. When applying a ...

**0**

votes

**0**answers

34 views

### Minimal subset of an $n$-dimensional grid intersecting every ($n$-dim) arithmetic progression of length $k$

Let $$A=\{1,2,...,l\}^n \subset \mathbb{R}^n$$ for some positive integers $l$ and $n$, and $B \subset A$ be a set such that $|B| \ll l^n$. I am interested in determining how small must $B$ be in ...

**11**

votes

**1**answer

221 views

### Generating function of a sequence is not algebraic

Let we have a sequence $\{a_{n}\}$, such that $\forall n \,\, a_{n}>0$ and $a_{n} \rightarrow\infty, n\rightarrow\infty$. Also let's suppose that we have a subsequence $\{a_{n_{k}}\}$ such that $\...

**1**

vote

**1**answer

76 views

### If the two smallest eigenvalues of the Laplacian matrix of a network are equal to zero, then does it mean that the network is not connected? [closed]

What does it mean if the two smallest eigenvalues of the Laplacian matrix of a graph are equal to zero?

**7**

votes

**1**answer

135 views

### Can the graph removal lemma be proved directly from the triangle removal lemma?

The Triangle Removal Lemma states that any graph with $o(n^3)$ triangles can be made triangle-free by removing only $o(n^2)$ edges. More generally, the Graph Removal Lemma states that for any graph $...

**4**

votes

**1**answer

157 views

### What is the minimum number of independent sets for a graph with fixed numbers of vertices and edges?

Fix integers $V$ and $E_{\text{max}}$, and consider graphs $G$ with $V$ vertices and at most $E_{\text{max}}$ edges. What is the best lower bound that one can give on the number of distinct ...

**0**

votes

**1**answer

131 views

### Stable marriages for infinite bipartite graphs

Short and informal version: Does the stable marriage problem have a solution if there are $\kappa$ men and $\kappa$ women for any cardinal $\kappa \geq \aleph_0$?
Long and formal version: Let $\kappa$...

**-2**

votes

**1**answer

61 views

### Splitting the vertices of undirected graphs into 2 sparse sets

(A version of this question for undirected graphs.)
Let $G=(V,E)$ be a finite, simple, undirected graph. For $v\in V$ set
$$
N(v) := \{x\in V: \{x,v\}\in E\}.
$$
Is it possible to find a ...

**1**

vote

**1**answer

121 views

### Counting faces on multipermutahedra/multipermutohedra

A multipermutahedron is the convex hull of all permutations of a list of numbers. For example, $\Pi(0,1,2)$ generates a regular hexagon, and $\Pi(0,1,1,2)$ generates a cuboctahedron.
In general, ...

**2**

votes

**2**answers

99 views

### Minimal number of blocks in a $(n,n/2,\lambda)$ block design

A $(n,n/2,\lambda)$ block-design is a family $A_1,...,A_K$ of subsets of $[n]$ such that $|A_i|=n/2$ and for every $1 \leq i < j \leq n$ it holds that
$\#\{1 \leq k \leq K : i,j \in A_k \} = \...

**5**

votes

**2**answers

168 views

### How to construct particular De Bruijn sequences

For $n \ge 2$, there is at least one binary DeBruijn sequence beginning with $n$ zeros followed by $n$ ones. Is there a straightforward way to construct such a sequence for each $n \ge 2$? Examples:
...

**7**

votes

**3**answers

299 views

### A simplified Art Gallery Problem in a matrix

Let's take a $m \times n$ matrix as an area with $m \times n$ blocks (likes a 2D-version of the world in Minecraft). We have to put some lamps in this matrix to illuminate the whole matrix. Here is ...

**5**

votes

**0**answers

73 views

### Probabilistic distribution of sandpile model type

Let $G=(V,E)$ be a connected graph. Assume that $m\leqslant |V|$ hedgehogs sit in the vertices of $G$. If there are $r\geqslant 2$ hedgehogs in the same vertex $v\in V$, one of them goes to a randomly ...

**1**

vote

**0**answers

42 views

### How to estimate the size of balanced biclique in random bipartite graph?

We have a random bipartite graph $G=(V,U,E)$ and $|V|=|U|=n$, in which any vertex pair $<v,u>$ ($v\in V$,$u\in U$) exists an edge with probability $p$. A balanced bipartite complete graph is a ...

**0**

votes

**2**answers

163 views

### Reference : Partition of integer

In algebraic number theory we come across following formula:
$n= e_1f_1+\cdots+e_rf_r$
where all $e_i$ and $f_i$ are positive integers. I am sure writing a positive integer n as above must be ...

**1**

vote

**1**answer

117 views

### Building the string on $\{0,1\}$ alphabet with $\Omega(n^{2})$ different substrings [closed]

As we know the number of different substrings has the upper bound $O(n^{2})$.
Consider the strings on $\{0,1\}$ alphabet. Can I build a string with $\Omega(n^{2})$ different substrings?
Actually I ...

**6**

votes

**1**answer

368 views

### Frankl's conjecture and Oeis sequence A188163

For every natural number $c \geq 2$, let $f(c)$ denote the least natural number $f$ with the following property : every union-closed family of sets with at least $f$ members has $c$ members whose ...

**3**

votes

**0**answers

51 views

### Bounding the number of information sets in a linear binary code

A pretty well-known theorem regarding linear $(n,k,d)$ codes is that every $n-d+1$ coordinate positions contain an information set, but not all $n-d$ coordinate positions do. This is equivalent to a ...

**2**

votes

**1**answer

103 views

### Intransitive finite irreducible linear groups whose orbits are all large

I am interested in intransitive irreducible linear subgroups $G\subseteq\mathrm{GL}_n(\mathbb{F}_p)$ acting on $V-\{0\}=\mathbb{F}_p^n-\{0\}$ in the natural way, such that all of the orbits are very ...

**6**

votes

**1**answer

141 views

### Existence of a particular kind of polygonal subdivisions of surfaces

Let $\Sigma$ be a closed, compact, connected, oriented smooth $2$-manifold (in other words, a sphere or a torus with $g$ handles). We may draw smooth arcs on the surface in such a way that they cut it ...

**1**

vote

**0**answers

92 views

### Recursively defined numbers vs geometric series

Let $a,b\in{\mathbb Z}^{\ge0}$ and $h\in{\mathbb R}(d_1,d_2)$ be such that
$$a\ge b, \quad h(d_1,d_2)>0~~\forall\,d_1,d_2\in{\mathbb Z}^+, \quad \lim_{d_1,d_2\longrightarrow\infty}\frac{h(d_1,d_2)}{...

**5**

votes

**2**answers

144 views

### Minimum length of a convex lattice polygon containing k lattice points?

Let $f(k)$ denote the minimum length of a convex lattice polygon containing exactly $k$ lattice points (including lattice points on the boundary).
It is not too hard to show that $k = \frac{1}{4\pi} ...

**8**

votes

**1**answer

289 views

### How long does the slow inefficient algorithm for computing the product in classical Laver tables take?

Let $(A_{n},*)$ denote the $n$-th classical Laver table. Let
$X_{n}$ be the set of all finite sequences of elements from $A_{n}$.
Define a function $E_{n}:X_{n}\rightarrow X_{n}$ by letting
$E_{n}((...

**4**

votes

**2**answers

207 views

### Algorithms for finding graph isomorphisms

I was wondering if anybody knows where I can find some information about the current (practical) algorithms for finding graph isomorphisms. I've joined the bandwagon and wrote my own which I would ...

**2**

votes

**0**answers

102 views

### Asymptotic analysis of generating functions

Let $a_d\!\in\!{\mathbb R}^+$ with $d\!\in\!{\mathbb Z^+}$ be a sequence such that
$$\limsup \sqrt[d]{a_d}=1\,.$$
Define
$$F(z)=\sum_{d=1}^{\infty}a_d\,{\text{e}}^{d z}\,.$$
Suppose $F(z)$ admits an ...

**3**

votes

**0**answers

184 views

### A different equivalence relation on partizan combinatorial games

The following definitions are fairly standard, but reworded in a way that will be more appropriate for my question (so what follows is fairly long, but should be easy to read for the experts and might ...

**3**

votes

**1**answer

84 views

### Tournament whose large subtournaments contain no automorphism

For sufficiently large $n$, it is known that most tournaments of size $n$ contains no nontrivial automorphism, though I forgot the reference.
For sufficiently large $n$, does there always exist a ...

**4**

votes

**1**answer

125 views

### Representing a graph's vertices as linear combinations of paths

I have a (directed graded) graph $G=(V,E)$ with two distinguished subsets of $V$: sources and destinations. I am to show that the set of indicator functions of paths starting in a source and ending in ...

**5**

votes

**1**answer

193 views

### Construction of a graph

To construct a specific kind of undirected graph $G=(V,E)$, which $|V|=n>2$. For convenience, label the vertices with $v_1,v_2,\dots ,v_n\in V$, and $(v_i,v_j)\in E$ means there is a edge between ...

**4**

votes

**0**answers

129 views

### Confusion with proof of Pieri's Formula

In Manivel's Symmetric Functions, Schubert Polynomials, and Degeneracy Loci, I am confused with some parts of his proof of Pieri's Formula. It is given as Pieri's Formula $3.2.8$ (p. $109$):
If $\...

**3**

votes

**1**answer

212 views

### Periodic strings

I wish to ask a problem in periodic strings, it might be well-known but I am a beginner in this subject, so I am very glad if someones can show me. My problem is that can we add some string to the end ...

**4**

votes

**1**answer

218 views

### Eliminating a variable from a two-variable linear recurrence

In attempting to enumerate a combinatorial class of objects, I've come to a bivariate recurrence:
$$
a_{n,k} = 2a_{n,k-1} + (k+1)a_{n-1,k+1} - ka_{n-1,k} - a_{n,k-2} + a_{n-1,k-1}.
$$
Together with ...

**7**

votes

**2**answers

154 views

### Self-complementary block designs

For what $n$ does there exist a self-complementary
$(2n,4n-2,2n-1,n,n-1)$ balanced incomplete block design?
(All I know is that a self-complementary design with these parameters does exist for all $...

**3**

votes

**1**answer

96 views

### Menger's Theorem for planar triangulations

I was reading the paper "Planar separators" by Alon, Seymour and Thomas (available on the first author's webpage). They consider a planar triangulation, that is, a maximally planar graph $G$ drawn in ...