# Tagged Questions

**1**

vote

**0**answers

59 views

### bounded degree graph colouring.

I was wondering if anyone could provide references on the following:
Is determining the chromatic number of a bounded degree graph APX-complete?
2.I've seen the result that states it is NP-hard ...

**3**

votes

**0**answers

73 views

### Hypergraph edge colouring

I'm interested in knowing if finding the edge-chromatic number of a $k$-uniform $k$-partite hypergraph is NP-hard for $k\geq 3$ Could anyone provide a reference for the result? By edge-chromatic ...

**4**

votes

**1**answer

83 views

### Choice number of embedded graphs

For given $g$, consider the family of graphs which may be embedded to the compact orientable surface of genus $g$. For this family, consider maximal clique $\alpha(g)$, maximal chromatic number $\chi(...

**2**

votes

**1**answer

264 views

### upper bound on derivatives of a function defined on an arc

This is a simple question I asked in math.SE last month but unfortunately no one gives any comment. So I decided to try some luck here.
You can skip examples below and read from "General setting" at ...

**5**

votes

**1**answer

207 views

### Can we cover a set by a particular family of sets?

Let $A_1,A_2,\ldots,A_m,B_1,B_2,\ldots, B_m$ be (not necessarily distinct) subsets of $[n]=\{1,2,\ldots,n\}$. Suppose that each $i\in [n]$ appears in at least $k$ of these $2m$ sets.
I want to ...

**1**

vote

**1**answer

89 views

### Weighted counting of circular codes

Given a circular code $X$ (for example: $X=\{ w,b \}$) with generating function $u(z)=\sum\limits_{k=0}^{\infty}{u_k z^k}$ (in this example : $u(z)=2z$), the generating function $p(z)=\sum\limits_{k=0}...

**3**

votes

**1**answer

179 views

### A spectral graph theory problem

Let $S$ be a zero-free subset of the group ${\bf Z}_2^n$ and $\Gamma={\rm Cay}({\bf Z}_2^n,S)$ be a bipartite Cayley graph. For some choices of $S$, the graph $\Gamma$ has $4$ distinct eigenvalues, ...

**2**

votes

**0**answers

59 views

### Terminology and technique for repeated pairwise removal of elements of posets: “Collapsibility” of a “face poset”

Let $P$ be a poset, or partially ordered set. Let $\le$ denote the reflexive order on $P$, and $<$ the corresponding irreflexive order. Let the phrase "a maximal pair" in $P$ refer to an
ordered ...

**4**

votes

**1**answer

66 views

### Separate a special poset by function

Assume $A = \prod_{i=1}^n\{0,1\}$, i.e. element $(a_1,\cdots,a_n)=a\in A$ is n-tuples like $(1,0,1,\cdots)$.
There is an obvious partial order on the $A$: say $a < b$ for $a,b\in A$ if and only ...

**2**

votes

**0**answers

74 views

### Relating face polytopes of permutohedra to integer partitions

The OEIS entries A019538, A049019, and A133314, relate a refinement of the face polynomials of the permutohedra (A049019) to partition polynomials (A133314) defined by multiplicative inversion of an ...

**6**

votes

**1**answer

124 views

### Union-closed family generated by n 2-sets

I asked this question on Stackexchange, but I got no answer, so I ask it here.
Let us define a $2$-set as a set with exactly $2$ elements. For a natural number $n$, let $l(n)$ denote the least ...

**1**

vote

**0**answers

65 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

225 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

71 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

154 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

113 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

140 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

183 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

135 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

138 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

165 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

287 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

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

**4**

votes

**0**answers

81 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

282 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

191 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

169 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

74 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

199 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

585 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

80 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

114 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

59 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

70 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

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

**10**

votes

**0**answers

278 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

199 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

951 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

63 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

253 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

134 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

58 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

47 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?