# Tagged Questions

**1**

vote

**0**answers

63 views

### Lower bound the ratio of the combinatorial quantities

Suppose $p < q$, $s = p^{d}$ for some fixed $d \in (0,1)$, let $p$ goes to infinity, define the following quantity,
\begin{aligned}
\quad f(j) = \sum_{i = 0}^{\min(j,s)}{s \choose i}{p-s \choose i}{...

**3**

votes

**2**answers

218 views

### sum over all integer partitions, of the product of the factorials of the terms

I'm looking for something making tractable the sum, over all partitions into k terms of an integer n, of the product of the factorials of all the terms.
Thanks,

**1**

vote

**0**answers

70 views

### connectedness of semi algebraic sets

We know the inequalities $x_ix_j >\theta_{ij}$ or $x_ix_j<\theta_{ij}$ for some $\theta_{ij}$>0, some $i,j\in\{1,\cdots,n\}$, $i\neq j$ defines the easiest semi algebraic set in $R^n_{\geq 0}$, ...

**6**

votes

**1**answer

115 views

### Average minimum number of random k-sparse vectors in GF(2) to span the whole space?

What is the average minimum required number of independent $k$-sparse (having at most $k$ non-zero elements) random vectors belonging to $\mathbb{F}_2^n$ to span the whole space of $\mathbb{F}_2^n$? ...

**3**

votes

**1**answer

107 views

### What is the densest bipartite graph with unique Hamiltonian cycle?

In a prior post regarding perfect matching, it was stated that the densest graph with a unique perfect matching cannot have more than $n^2$ edges, if graph has $2n$ vertices.
Analogously, what is the ...

**5**

votes

**1**answer

136 views

### Upper Bound for the Difference of Even Probability and Odd Probability in Hypergeometric Distribution

Let $X$ be a random variable following the hypergeometric distribution with parameters $N,K,n$, where
\begin{equation}
Pr(X=k) = \frac{\binom{K}{k}\binom{N-K}{n-k}}{\binom{N}{n}}.
\end{equation}
To ...

**3**

votes

**0**answers

180 views

### First to note/document the relation between permutohedra and multiplicative inversion

The relation between the refined face numbers of the permutohedra and the formal series expansion of the reciprocal of a function (exponential generating function, formal Taylor series) is given in ...

**1**

vote

**1**answer

133 views

### Number of eigenvalues of a Cayley graph

Let $G=Z_2^n$ and $S\subset G$. Is there any relation for number of distinct eigenvalues of $\Gamma=Cayley(G,S)$ graph depending on $n$ and $|S|$, or at least diameter of $\Gamma$? If you have any ...

**4**

votes

**1**answer

133 views

### “Small” simplicial complex with torsion trees

I am giving an expository talk soon about Duval-Klivans-Martin's paper Simplicial Matrix Tree Theorems, and I've been struggling to find a good example to do at the board. An important aspect of the ...

**3**

votes

**1**answer

132 views

### Alternative parallel paths

There are $n$ non-intersecting strings (with ends $x_1,\dots, x_n$ and $y_1,\dots, y_n$). An additional string intersects the first $n$ strings somehow. All the intersections are simple (vertices of ...

**7**

votes

**1**answer

285 views

### Choosing two-colorable subgraph in a triangulation

Consider a planar graph $G$ which is a triangulation.
Is it possible to find a two-colorable subgraph $H$ of $G$ which has a common edge with every face of $G$?
It is known that it is not always ...

**1**

vote

**1**answer

187 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

79 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

278 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

189 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

162 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

73 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 $v\in\{...

**2**

votes

**0**answers

85 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 R^+\...

**1**

vote

**1**answer

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

**13**

votes

**2**answers

577 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

79 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

111 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

57 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 n\...

**2**

votes

**1**answer

66 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

104 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

187 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

262 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

112 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

193 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

107 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

149 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

948 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

62 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

251 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

132 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

80 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 $\textit{...

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

150 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

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

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

94 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

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

130 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

184 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

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