**1**

vote

**0**answers

66 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

89 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

89 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

63 views

### Alternative parallel paths

Parallel strings which connect points $x_1,\dots, x_n$ with points $y_1,\dots, y_n$, are sewn with an additional string. The union of these $n+1$ strings is considered a framed graph (we remember ...

**7**

votes

**1**answer

240 views

### Choosing two-colorable subgraph in a triangulation

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

**1**

vote

**1**answer

157 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

65 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

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

**2**

votes

**1**answer

140 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

149 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

24 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

70 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

67 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

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

**9**

votes

**2**answers

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

**0**

votes

**0**answers

65 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

93 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

51 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

63 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

54 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

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

**8**

votes

**0**answers

157 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

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

**5**

votes

**2**answers

174 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

100 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

137 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

750 views

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

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

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

**3**

votes

**1**answer

90 views

### Number of perfect matchings of bipartite graphs

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

127 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

75 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

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

**0**

votes

**0**answers

41 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

144 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

59 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

242 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

162 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

111 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

92 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

133 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

86 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

119 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

**0**answers

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

**14**

votes

**0**answers

375 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

34 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

548 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

44 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

44 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

68 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

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