**1**

vote

**1**answer

180 views

### Non-regular languages fulfilling the Pumping Lemma

Some non-regular languages don't yield to the Pumping Lemma ($L_1=a^nb^mc^m$ should work). But now consider the set of non-regular languages L only over the alphabet {a}. (Like $L_2=a^{n^2}$ or ...

**3**

votes

**0**answers

76 views

### Number of linearly independent subsets in arbitrary set

Consider $n$-dimensional vector space $\mathbb{F}_p^n$ over finite field $\mathbb{F}_p$ and a function $a: \mathbb{F}_p^n\rightarrow\mathbb{C}$. Let
$$ F(a) = \sum_{\substack{S\subset \mathbb{F}_p^n ...

**7**

votes

**1**answer

276 views

### Unique factorization of posets

Given two finite posets $P$ and $Q$, we can form the direct product poset $P \times Q$ whose elements are pairs $(p,q) \in P \times Q$ with $(p,q) \leq (p',q')$ if $p \leq p'$ and $q \leq q'$. Let us ...

**3**

votes

**1**answer

185 views

### Self-containing trees

Suppose that $r^2-r-1=0$ and that $T$ is the tree with root $1$ such that the children of each node $x$ are $rx$ and $x+1$. Remove all duplicates as they occur, and let $T(r)$ denote the remaining ...

**-3**

votes

**2**answers

154 views

### What is the number of self-inverse permutations on a set of cardinality $N$?

Given a function (aka 'permutation') $f:A \rightarrow A$, where $A$ is a finite set such that $|A| = N$, we call it a self-inverse if $f(f(x)) = x$. The sequence of how many such functions exist for ...

**2**

votes

**0**answers

28 views

### Ordered cross ratios for the uniform matroid

At the moment I am studying a proof by Gel'fand, Rybnikov and Stone (Theorem 4 in the paper "Projective Orientations of Matroids"). To be more precise, I am try ing to describe a new presentation by ...

**1**

vote

**1**answer

71 views

### Reference for a local density theorem for binary vectors

I have the following theorem written on my whiteboard, but have misplaced the reference. I believe the probabilistic method may be involved in the proof. Any pointers appreciated.
Theorem Let ...

**2**

votes

**0**answers

83 views

### Maximum number of $4$-cycles

Suppose we have a balanced bipartite planar maximum degree $k$ graph.
How many such graphs on $2n$ vertices have at most $f(n)$ maximum number of $4$ cycles for a given function $f:\Bbb ...

**1**

vote

**1**answer

171 views

### Applications of topology to discrete dynamical systems?

I'd like to know some of the applications of topology to discrete dynamics. By discrete dynamics I loosely mean studying maps between discrete sets.
I mean cases where adding a topology to the sets ...

**12**

votes

**2**answers

508 views

### Lattice n-gons with ordered side lengths 1,2,3,…,n

Consider the octagon in the Cartesian plane with vertices at (0,0), (1,0), (1,2), (4,2), (4,6), (7,2), (7,8), and (0,8).
Are there other (infinitely many) polygons, such as this, lying entirely in ...

**1**

vote

**0**answers

76 views

### maximal sets of vertices that avoids a clique

I am looking for some known algorithm that finds, for a given graph, all the maximal sets of vertices that avoid a clique of some given size $k$. I'd prefer one written in MATLAB, but other languages ...

**3**

votes

**1**answer

106 views

### chromatic polynomial of G - Join graph

Given a connected graph $G$ with $n$ vertices and given set of $\{m_1,m_2,...,m_n\}$ $n$ integers, we form a new graph $G^{\wedge} $ by considering the complete graph $K_{m_i}$ for each vertex i and ...

**1**

vote

**1**answer

56 views

### linear recurrence inequality of positive terms

This is a follow up on my previous linear recurrence inequality question.
I have some matrices which satisfy a linear recurrence formula of the form
$$
A_{n+1} = \alpha A_{n} + \beta A_{n-1},\qquad ...

**2**

votes

**1**answer

65 views

### linear recurrence inequality

Given two real analytic functions, $g(x)$ and $f(x)$, on an open interval $I\subset \mathbb{R}$, it is obvious that $g(x) \leq f(x)$ does not imply $g_n \leq f_n$ (here $g_n = [x^n] g(x)$ denotes the ...

**1**

vote

**1**answer

70 views

### Counting bounded genus non-isomorphic graphs

What is the number of non-isomorphic $2n$ vertex balanced bipartite graphs of degree at most $d$ and genus $g$?
I am most interested in $d\leq3$ and $g=0$.

**4**

votes

**2**answers

181 views

### Non-Cayley expander graphs

When I search about expander graphs in google I see a lot of articles about expander Cayley graphs. Now my questions are as follows:
Are all expander regular graphs are Cayley, or there is a special ...

**9**

votes

**0**answers

237 views

### Computing the ordinal of a rational language well-partially-ordered by the subword relation

Let $\Sigma$ be a finite set or "alphabet", $\Sigma^*$ the free monoid on $\Sigma$ or set of "words". If $w,w'\in \Sigma^*$, write $w\leq w'$ when $w$ is a "subword" of $w'$, i.e., can be obtained by ...

**4**

votes

**1**answer

111 views

### Nearly Be Bruijn sequences constructed from De Bruijn sequences

Let $w$ be a De Bruijn $01$-sequence of the type $B(2,n)$; i.e., a cyclic $01$-sequence that contains every $n$-digit $01$-sequence exactly once. Let $x$ be a $01$-sequence of length $n$. When and ...

**6**

votes

**2**answers

187 views

### “Diagonalizing” Littlewood-Richardson coefficients

Let's consider the Littlewood-Richardson coefficients $c^{\lambda}_{\mu \nu}$ so that
\begin{equation}
V_\mu \otimes V_\nu = \bigoplus_\lambda V_\lambda^{\oplus c^{\lambda}_{\mu \nu}}
\end{equation}
...

**6**

votes

**0**answers

106 views

### A way to smooth out the log* function?

I have seen here and there discussions about what is the "correct" way of extending the Ackermann function to the reals (the same way the Gamma function extends the factorial function to the reals). ...

**1**

vote

**1**answer

145 views

### Powers of two with coefficients {1,−1}

Given a vector $(n_0, n_1, \dots, n_l)$ where $n_i \in \{-1, 1\}$, $i = \overline{0, l-1}, n_l = 1$ and $l \in \mathbb{N}$.
Prove that for all $a$ such that
$$0 < a \leq 2^0\cdot n_0 + 2^1 \cdot ...

**2**

votes

**2**answers

938 views

### Encoding vectors of size $n$ in matrices which less than $2n$ rows [closed]

I have a set of vectors and each has $n$ nonnegative entries.
Moreover, each entry of a vector has a quality: (1) or (2). It makes $2^n$ different possible patterns.
For example, let's take two ...

**1**

vote

**0**answers

57 views

### Björner-Wachs theorem for posets admitting an EL-labeling

In the survey paper Poset Topology: Tools and Applications by Michelle Wachs, there is the following theorem on p46:
Theorem 3.2.4 (Björner and Wachs [40]). Suppose $P$ is a poset for
which ...

**4**

votes

**2**answers

245 views

### Are all numbers from $1$ to $n!$ the number of perfect matchings of some bipartite graph?

Let $f(G)$ give the number of perfect matchings of a graph $G$.
Consider set $\mathcal N_{2n}=\{0,1,2,\dots,n!-1,n!\}$.
Consider collection of all $2n$ vertex balanced bipartite graph to be ...

**7**

votes

**0**answers

130 views

### More about self-complementary block designs

For what odd integers $n \geq 3$ does there exist a self-complementary $(2n,8n−4,4n−2,n,2n−2)$ balanced incomplete block design?
By "self-complementary" I mean that the complement of each block is a ...

**2**

votes

**0**answers

77 views

### Regularity for a bipartite graph

Let $G$ be a bipartite graph with $2^n$ left vertices and $2^n$ right vertices such that:
1) degree of every vertex is not greater then $2^t$
2) number of all edges is greater than $2^{n +t - O(\log ...

**0**

votes

**1**answer

55 views

### Long term behavior of a certain discrete time dynamical system on graphs

Consider the graph $(V,E)$ with vertex set $V=\{v_1,...,v_n\}$ and edge set $E\subset V\times V$. Further, assume that $\forall v_i\in V, (v_i,v_i)\in E$.
Assume that each vertex has an ...

**1**

vote

**0**answers

44 views

### Largest number of perfect matchings in bounded genus graphs

What is the largest number of perfect matchings a genus $g$ bipartite graph on $n+m$ vertices have?

**2**

votes

**0**answers

149 views

### the root lattice, reflections, and a coxeter element

Question: Is is possible to realise the positive root lattice $\Phi_{\Delta}^{>0}$ (viewed as an abstract poset) of a root system $\Phi_\Delta$ associated to a Dynkin or affine Dynkin diagram ...

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

246 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

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

**2**

votes

**1**answer

114 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

93 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

134 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

88 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

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

**4**

votes

**3**answers

175 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

381 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

36 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

567 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

45 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

69 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

279 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

157 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

170 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

87 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

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