# Tagged Questions

**3**

votes

**0**answers

63 views

### Fraction of graphs with bound on number of perfect matchings

Asymptotically what is the fraction of balanced bipartite graph on $2n$ vertices with at most $cn^{\beta}$ edges having at most $n^\alpha$ perfect matchings for any fixed $c,\alpha>0$ and fixed $\...

**5**

votes

**1**answer

247 views

### When does there exist a convex polyhedron with given edge lengths?

Let $n$ be a positive integer, and let $n = \ell_1 + \dots + \ell_k$ be
a partition of $n$. Then there exists a convex polygon with side lengths
$\ell_1, \dots, \ell_k$ if and only if all of the $\...

**3**

votes

**1**answer

170 views

### Is there a characterization of CI-groups of order less than 100?

We know some benefit criterion in articles such as:
C. H. Li, On isomorphisms of finite Cayley graphs-a survey, Discrete Math., 256 (2002) 301-334.
C. H. Li, Z. P. Lu, P. P....

**2**

votes

**1**answer

115 views

### Bases of the special form

Let $R = \mathrm{GF}(q)$, $S = \mathrm{GF}(q^n), \ n\geq 2$ be extension of $R$, $h$ be a primitive element of $S$. I want to count or estimate the number $N$ of bases of the following form.
Let $$\...

**4**

votes

**0**answers

97 views

### Examples of combinatorial bijections found by considering functors

Let us assume that I have two sets of combinatorial objects, $A$ and $B$,
and I am looking for a bijection (in particular a map) $\psi:A \to B$ between these sets, usually required to preserve some ...

**5**

votes

**2**answers

135 views

### Are the Gessel sequence integers composite for all $n\ge 3$?

The Gessel sequence is known for Ira Gessel's Lattice Path Conjecture of $2001$, which has been proved by Kauers, Koutschan and Zeilberger in $2009$ with the aid of a computer. Later there were found ...

**3**

votes

**1**answer

89 views

### A modified bipartite assignment problem

Consider the following optimization problem. I have $n$ advisors and $dn$ students. I want to assign each student an advisor so that each advisor has exactly $d$ students. Each advisor/student pair ...

**5**

votes

**2**answers

132 views

### Finite graph colorings without symmetries

Let $G$ be a connected finite simple graph with vertex set $V$, $F$ a finite set and let $\Delta(G)$ denote the degree of $G$, i.e. $\Delta(G)= \max_{v\in V} \deg(v)$. We say that a coloring $\phi\...

**4**

votes

**3**answers

185 views

### Relation between diametral path and regularity of a graph

Let $G(V,E)$ be a graph. A path whose length is equal to the diameter of a graph is called a diametral path. In a cycle graph every vertex has $2$ diametral paths. Now I need to prove that this:
...

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

39 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

579 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

49 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

47 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

72 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

287 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

165 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

174 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

90 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

212 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

67 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

75 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

97 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

36 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

78 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

146 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

163 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

132 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

63 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

126 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

102 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

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

**8**

votes

**3**answers

302 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

74 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

166 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

120 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

372 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

54 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

143 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

145 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

291 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

211 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

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