# Tagged Questions

**0**

votes

**0**answers

119 views

### Closed form solution of a complex recurrence relation

I am looking for a closed form expression for $ST(n, k)$ defined as
$$
ST(n, k) = \sum_{s = 0}^{n - k}
{{n - k} \choose s} QT( k + s, k + s - 2, k),
$$
where $QT( n, m, k)$ is defined by the ...

**4**

votes

**0**answers

113 views

### Convex polytopes as “products” of lower dimensional polytopes of the same family

This MO answer on enumerative geometry details the sense in which an associahedron is a product of lower dimensional associahedra, and the comments in this MSE-Q indicate the same is true for ...

**11**

votes

**1**answer

1k views

### Why is this character expression an integer?

Let $\gamma$ be an $n$-dimensional complex representation of a finite group $G$ with character $\chi$ and let $e=c_0, c_1, ..., c_{\ell}$ be a set of conjugacy class representatives for $G$. In the ...

**2**

votes

**1**answer

152 views

### Generating function for numbers divisible by some primes

Consider the first $k$ primes $p_1 = 2, p_2 = 3, \dots, p_k$. Let $A_k$ be the set of numbers that are divisible by at least one $p_i$. We can represent this set as a generating function:
$$G_k(x) = \...

**1**

vote

**0**answers

52 views

### On structure of patterns of subset sums?

There are roughly $2^{nm}$ choices of sets of $m$ distinct integers in $[-2^n,2^n]$ (after fixing ordering). Each set of $m$ integers has $2^m$ subsets.
Suppose we assign $\{0,1\}$ value to each ...

**8**

votes

**1**answer

77 views

### Schur positivity on 2 letter alphabets implies Schur-positivity on n letters?

Suppose we have a symmetric polynomial $P$ in $n$ variables.
We can partition this alphabet into sets with one or two letters, e.g. ${ {x_1}, {x_2, x_3}}.
We can thus see $P$ as an element in $Q[x_1]...

**0**

votes

**1**answer

79 views

### Does general case of following function exist?

Suppose we have the following: $m_1 m_2 m_3$
Where $m_1$, $m_2$, $m_3$ are constants $> 0$
I'm looking for a function $f$ such that:
$m_1 m_2 m_3 = 1.0 + f(m_1,m_2,m_3) + f(m_2,m_1,m_3) + f(m_3,...

**2**

votes

**0**answers

64 views

### Which matroids have not unique unimodular representation?

Matroid $M$ is represented by real vectors, and we know that any base of $M$ generates the same lattice (this is called unimodular representation, I guess.) If we change the sign of any vector, we ...

**2**

votes

**1**answer

245 views

### Number of subsets that sum to $0$

Suppose you choose $n$ distinct random numbers from a contiguous subset of cardinality $f({\beta, n})$ with at least $f({\alpha_+, n})$ positive and at least $f({\alpha_-, n})$ negative values from a ...

**7**

votes

**2**answers

207 views

### Graphs with prescribed numbers of k-cliques

Let $(a_1,a_2,\dots, a_n)$ be a sequence of non-negative integers.
Q. When does there exists a simple graph $G$ such that its number of $k$-cliques is $a_k$ (that is $G$ has $a_1$ vertices, $a_2$ ...

**2**

votes

**1**answer

90 views

### How many distinct sets of n collinear points are there in an evenly-spaced two-dimensional grid of m x m points?

I'm seeking the definition of some function $f(n,m)$ which evaluates to the number of distinct sets of $n$ collinear points which are selected from an evenly-spaced two-dimensional grid of $m \times m$...

**2**

votes

**1**answer

133 views

### How many lines of exactly n points can be placed in a discrete, square grid of size m x m?

Per the title, I'm seeking the definition of a function $f(n, m)$ which evaluates to the number of lines made from exactly $n$ points which can be placed on a two-dimensional discrete, square grid of ...

**5**

votes

**2**answers

136 views

### Multiplication in universal enveloping algebra in terms of PBW isomorphism

Let $\mathfrak g$ be a Lie algebra. Consider the multiplication map $m:\mathfrak g\otimes U(\mathfrak g)\to U(\mathfrak g)$ and $i:S(\mathfrak g)\to U(\mathfrak g)$ -- Poincare-Birkhoff-Witt ...

**2**

votes

**0**answers

115 views

### Nonvanishing of the dual Euler totient on boolean intervals of finite groups

The rank $n$ boolean lattice $B_n$, is the subset lattice of $\{1,2, \dotsm n \}$.
Let $[H,G]$ be a boolean interval of finite groups. Its Euler totient is defined by $$\varphi(H,G):=\sum_{K \in ...

**3**

votes

**0**answers

60 views

### How many unimodular lattices does it take to fill a cube with high probability?

Consider $C_a$ in $\Bbb Z^n$ a cube of height $a$ at origin in positive coordinates with one corner at origin.
Consider the set $M_c$ of all unimodular matrices in $\Bbb Z^{n\times n}$ with each ...

**0**

votes

**0**answers

76 views

### Derandomizing AP existence in $A\subseteq \{1,\ldots,N\}$ for $\delta(A) \geq 1/k$

In the answer to the mathoverflow question here, it was established that if we let $p$ be the probability of including point $v$ in $A\subseteq \{1,\ldots,N\}$ and this is done independently for all ...

**1**

vote

**0**answers

114 views

### A probability question related to combinatoric problem

I am trying to solve a combinatoric problem. The problem is the following:
There are A,B,C three types of people. There are totally N people arriving sequentially and make a choice between two boxes X ...

**0**

votes

**0**answers

24 views

### is any closed form relation that can state the error probability of code versus its variable and check node degree distributions?

In Low Density parity check code design, when bit (or frame) error probability of code is the objective of the design, we need a closed form relation between error probably (or even an approximate or ...

**1**

vote

**1**answer

107 views

### Convexity of truncated expectation

Let $k, n$ be two positive integers with $k \leq n$, and let $P = \{ (x_1, \dots, x_n) \in [0, 1]^n : \sum_i x_i = k \}$.
Given $x = (x_1, x_2, \dots, x_n) \in P$, let $X_i$ be the random variable ...

**1**

vote

**1**answer

91 views

### Intersection of members in a separating union-closed family of sets

Tony Huynh gave a nice answer to a question I asked here :
Number of members of a separating union-closed family whose universe has given cardinality
The answer shows in fact that if $\mathcal{F}$ ...

**0**

votes

**0**answers

161 views

### Warren's Theorem

At the end of page 12 in this document Noga Alon mentions Warren's Theorem on sign patterns: tau.ac.il/~nogaa/PDFS/tools1.pdf
Does anyone know of an intuitive explanation of the proof of it ? Also, ...

**1**

vote

**3**answers

214 views

### Existence of special graph

Let $G$ be a $n$-vertices graph and $\lambda_1$ is the largest eigenvalue of this graph. If $\lambda_1$ is an integer value, we can easily find the $\lambda_1$- regular graph with $n$ vertices. Now, ...

**5**

votes

**1**answer

269 views

### Vector with many non-zero coordinates

Given finite field $\mathbb{F}_q$, positive integers $n$ and $k<n$. Given $k$-dimensional subspace $X$ of $\mathbb{F}_q^n$, for which $m=m(q,k,n)$ may we find for sure a vector in $X$ with at least ...

**2**

votes

**0**answers

63 views

### Number of $(2n-1)$-edge-colorings of the complete graph $K_{2n}$

I just started reading about graph theory and have a question (which might be trivial). How many $(2n-1)$ edge colorings of $K_{2n}$ are there?
A vaguer question: can I write $K_{4n}= K_4 + K_4 +.......

**2**

votes

**1**answer

106 views

### Number of members of a separating union-closed family whose universe has given cardinality

If I'm not wrong, it is easy to prove the following statement :
If $n$ is a natural number $\leq 4$, if $\mathcal{F}$ is a union-closed family of nonempty sets, if the universe of $\mathcal{F}$ (i.e. ...

**1**

vote

**1**answer

47 views

### How to generate a Latin square $M'$ in the same main class as $M \in \mathrm{LS}(9)$ which agrees with $L$ in the most cells?

I'm brainstorming an idea for storing a compressed list of main class representatives of Latin squares of order $9$. One way to compress the list would be to store one Latin square $L_1$, and for $i \...

**1**

vote

**0**answers

69 views

### Missing count in number of perfect matchings

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 $\...

**3**

votes

**1**answer

82 views

### Does the Chen-Chvátal Conjecture on metric spaces hold for maximal lines?

A conjecture by Chen and Chvátal asks for the minimum number of induced "lines" in a metric space, in the same spirit as the De Bruijn–Erdős theorem.
Though the statement of this problem on Douglas ...

**3**

votes

**0**answers

39 views

### Does the rank (=height) of a well partial order bound its type (=length, =stature)?

Terminology and context
(This should all be standard, but is recalled because terminology sometimes varies, and also to put the question into perspective.)
A partially ordered set is called well-...

**6**

votes

**1**answer

214 views

### Is the exponent $2$ sharp in the Balog-Szemerédi-Gowers Theorem?

The Balog-Szemerédi-Gowers theorem can be stated in the following form: let $A,B$ be subsets of $\mathbb{Z}/n\mathbb{Z}$ (say) with equal cardinality, such that
$$
\|1_A*1_B\|_2 \ge K^{-1} \|1_A\|_1 \|...

**0**

votes

**1**answer

75 views

### Choosing directed subgraph in a triangulation

Consider triangulation $T.$
Is it always possible to choose such a subgraph $H$ of $T$ that has a common edge with every face of $T$ and can be directed in such way that indegrees of all vertices of ...

**12**

votes

**1**answer

480 views

### A combinatorial identity involving harmonic numbers

The harmonic numbers are given by $$H_n=\sum_{k=1}^n\frac{1}{k}.$$
Numerical calculation suggests
$$
\sum_{k=1}^{n}(-1)^k{n\choose k}{n+k\choose k}\sum_{i=1}^{k}\frac{1}{n+i}=(-1)^nH_n.
$$
I can not ...

**1**

vote

**0**answers

147 views

### A conjecture about orbits in a recursive function motivated by Kolakoski's sequence

We first introduce several functions motivated by Kolakoski's sequence. The conjecture itself can be stated independently of Kolakoski's sequence. You can skip straight to the formulation of the ...

**15**

votes

**1**answer

336 views

### Combinatorics problem about sum of natural numbers

Following combinatorics problem is claimed to be an open problem in "The Princeton Companion to Mathematics" (pp. 6)
Let $a_1,a_2,a_3,...$ be a sequence of positive integers, and suppose that each ...

**2**

votes

**2**answers

124 views

### Probability of no $k$ 1's in arithmetic progression in binary sequence of length $n$

It is well known [it's on Wolfram Mathworld, for example] that the probability of no runs of $k$ consecutive $1$'s will occur in a $\{0,1\}$-valued sequence of length $n$ is exactly equal to $$\frac{F^...

**5**

votes

**1**answer

250 views

### Combinatorics: set partitions of a poset

Let $\pi_n$ be the poset of all set partitions of $\{1,...,n\}$ ordered by refinement, $\sigma = \{B_1,...,B_k\}$ be a set partition with blocks $B_i$, and $\max(B_i)$ be the maximum value in the ...

**2**

votes

**1**answer

144 views

### Can we deduce that a finite topology $T$ satisfies Frankl's union-closed set conjecture?

Let $X$ be a finite set and $T$ be a topology on $X$. Then $T$ is both union-closed and intersection-closed. Can we deduce that $T$ satisfies Frankl's union-closed set conjecture?
(We know that a ...

**1**

vote

**0**answers

40 views

### Separation on discrete set

Consider the set $L = \prod_{i=1}^n\{1,0\}$, i.e. L consists of the element of n-tuples whose entries are 0 or 1. Also we can regard $L$ as a subset of $R^n$.
Define linear functions $f(x)= a_1x_1+ \...

**4**

votes

**1**answer

96 views

### Probability of existence of a base in the span of sparse vectors in GF(2)

For $i=1,2,\dots,l$, let $\mathbf{v}_i =(v_{i1},v_{i2},\dots,v_{in}) \in \mathbb{F}_2^n$ be a sparse vector in GF(2) such that all $v_{ij}$'s are independent for all $1 \le i \le l, 1 \le j \le n$ and ...

**2**

votes

**1**answer

160 views

### The class of $(-1,0,1)$-matrix with all row sums and column sums equalling to $0$

Let $n$ be an even positive integer and $W_n$ be the class of all $n\times n$ matrices with entries from the set $\{-1,0,1\}$ satisfying all row sums and column sums are equal to $0$.
For any $M\in ...

**4**

votes

**2**answers

130 views

### Neighbourhood of a word and Levenshtein distance

The Levenshtein distance or Edit distance $$ lev(U,V) $$ between two strings $U$ and $V$ over a finite alphabet $\Sigma$ of size $ \left| \Sigma \right| = \sigma ,$ is the minimal number of insertions,...

**3**

votes

**2**answers

144 views

### Characterizing graphs whose Incidence Matrix has the all ones vector in its row span

Suppose we have a simple connected graph $G=(V,E)$. Then let $A$ be its $|E|\times |V|$ incidence matrix. Here I am considering the unoriented incidence matrix. I want to known when the row span of $A$...

**2**

votes

**0**answers

70 views

### Given a vector of positive integers, count the number of combinations which have a sum that produces a different value

I have a list (vector) of positive integer numbers, including repetitions. For example,
$L = [1, 1, 4, 1, 3]$;
I want to calculate the number of different sums obtained by using the elements of $L$, ...

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

261 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, ...