**2**

votes

**1**answer

226 views

### global sections of structure sheaf on the toric Calabi-Yau

Let P be a lattice polytope and lying in $ N \times {1} \subset N \times \mathbb{R}$. Let $\sigma$ be the cone over this polytope and $X_\sigma$ be the corresponding toric variety, which is an ...

**3**

votes

**1**answer

50 views

### Counting equivalence relations with marked classes

The number of equivalence relations on a set of $n$ elements is the Bell number $B_n$.
If we wish to count the number of equivalence classes on a set of $n$ elements where one of the classes is ...

**20**

votes

**7**answers

1k views

### Computer package for representation theory of the symmetric group

Is there a computer algebra package in which I can compute the following for representations of a specific symmetric group (e.g. $S_7$):
(1) $V \otimes W$
(2) $S_\lambda V$, where $S_\lambda$ is a ...

**6**

votes

**2**answers

215 views

### Principal Order Ideals in the Weak Bruhat Order

Let $\sigma\in S_n$ be a permutation on $n$ elements, and $\mathrm{Inv}(\sigma):=\{(i,j) : 1\leq i<j\leq n\text{ and }\sigma(i)>\sigma(j)\}$ be its set of inversions. In the weak order on ...

**11**

votes

**1**answer

223 views

### No limit shape for random Young diagrams under z-measure?

In their paper Random partitions and the Gamma kernel (Advances in Mathematics 194 (2005) 141–202), Borodin and Olshanski state that:
An important difference between the Plancherel measures and ...

**29**

votes

**4**answers

7k views

### Is the Jaccard distance a distance?

Wikipedia defines the Jaccard distance between sets A and B as $$J_\delta(A,B)=1-\frac{|A\cap B|}{|A\cup B|}.$$ There's also a book claiming that this is a metric. However, I couldn't find any ...

**7**

votes

**5**answers

644 views

### Algorithms for calculating R(5,5) and R(6,6)

Calculating the Ramsey numbers R(5,5) and R(6,6) is a notoriously difficult problem. Indeed Erdős once said:
Suppose aliens invade the earth and threaten to obliterate it in a year's time unless ...

**2**

votes

**1**answer

184 views

### Rank changes with matrix edits

Assume we have rank $r$ real matrix $M\in\{0,1\}^{n\times n}$ (not constrained to symmetric).
Assume $W\in\{0,1\}^{n\times n}$ is rank $1$ real matrix.
Case $1$: $M+W\in\{0,1\}^{n\times n}$.
Could ...

**0**

votes

**1**answer

186 views

### The weighting function for the infinite product of necklaces

Let us consider the limit $\lim_{n\to \infty}\prod_{p=1}^n N(p,a)$ where $N(n,a)$ is the number of fixed necklaces of length $n$ composed of $a$ types of beads.
Let's rewrite the product in a way ...

**4**

votes

**0**answers

53 views

### Prove or disprove a claim about covering a polytope by convex polytopes in a certain way

Here is the claim:
Given a polytope $K$ in a unit ball in $\mathbb{R}^d$, there exists a universal constant $C(d)>0$ depending only on $d$ and a countable collection of convex polytopes ...

**0**

votes

**1**answer

255 views

### Number of Dyck paths with k returns and b peaks

The number of Dyck paths from the origin to $(2n,0)$ which touch the $x$-axis $k+2$ times ($k$ internal touches) is given by
$$\frac{k}{2n-k}{2n-k \choose n}.$$
The number of Dyck paths from the ...

**4**

votes

**0**answers

89 views

### Generalization of Sprague-Grundy Theorem

In my research on Combinatorial Game Theory, I used a certain theorem that is essentially a generalization of the Sprague-Grundy theorem. Because the result hinges too much on the work of others to be ...

**2**

votes

**2**answers

183 views

### binomial/factorial identity mod p

In trying to determine the spectrum of a well-known ergodic transformation, I came up with the following useful (for me) result.
Let $p$ be a prime and $a$ a positive integer. Then for $M$ a positive ...

**0**

votes

**0**answers

36 views

### 3D matching modification

Consider all instances of the $3D$ matching problem where all edges that intersect-intersect in "exactly" one vertex (1-edge intersection).
Consider all instances of the $3D$ matching problem where ...

**14**

votes

**0**answers

268 views

### Need explicit formula for certain “$q$-numbers” involving gcd's

The question is motivated by yet another possible approach to a combinatorial problem formulated previously in "Special" meanders. I'm not giving details of the connection as I believe the ...

**17**

votes

**5**answers

4k views

### The problem of finding the first digit in Graham's number

Motivation
In this BBC video about infinity they mention Graham's number. In the second part, Graham mentions that "maybe no one will ever know what [the first] digit is". This made me think: Could ...

**5**

votes

**2**answers

213 views

### Four Dimensional Rook Domination

Let $\gamma(G)$ denote the domination number of a graph, and $G\,\square\,H$ denote the cartesian product of two graphs. Then $K_8\,\square\, K_8$ is the rook graph, whose vertices are the squares of ...

**2**

votes

**2**answers

163 views

### Simultaneous lcms

Suppose that we have some finite number of $k$-tuples then we define the lcm of two of these tuples to be the tuple of lcms of the co-ordinates. E.g. $[(9, 10), (5, 18)] = ([9, 5], [10, 18]) = (45, ...

**3**

votes

**1**answer

66 views

### $P_3$-factors for 3-regular, 3-connected cubic graphs

Suppose that $G=(V,E)$ is a simple graph.
We know if $G$ is 3-regular, 3-connected and $|V|=4k$ for some $k\in \mathbb{N}$, then $G$ has a $P_4$-factor.
Question. Let $G=(V,E)$ be 3-regular, ...

**5**

votes

**1**answer

435 views

### Bipartite Graphs arising from two k-partitions of a given Graph

Let $G$ be an $n$-chromatic connected graph. Let $(V_1, V_2, \cdots, V_n)$ and $(U_1, U_2, \cdots, U_n)$ be two partitions of $V(G)$ corresponding to proper n-colorings of $G$.
Consider the bipartite ...

**0**

votes

**1**answer

335 views

### When is a power of an indeterminate in an ideal with 2 generators?

If I have an ideal ${\frak a} \colon= (f(X,S), g(X,S))$ of height $2$ in ${\Bbb C}[X, S]$, is it easy to know what power of $S$ is contained in $\frak a$? For example, what is the minimal number $m$? ...

**4**

votes

**1**answer

400 views

### A Zero-Multiplicity Problem Related to Foulkes' Conjecture

I'm a combinatorialist that is interested in estimating multiplicities of irreps of $1^{S_{kn}}_{S_k \wr S_n}$ (the action of symmetric group on uniform partitions). I'm aware of the difficulty (or ...

**-4**

votes

**0**answers

54 views

### Cayley graph of dihedral group is isomorphic to which kind of graphs? [on hold]

Let D_{2n}= be dihedral group of order 2n. Also let D_{2n}= in which 1\ notin S=S^{-1}.
In this case Cay(D_{2n}, S) is isomorphic to which kind of graphs? This is my conjecture that this graph is ...

**7**

votes

**2**answers

259 views

### When is a sequence the sum of two Beatty sequences?

In other words, given a sequence $(s_n)$, how can we tell if there exist irrationals $u>1$ and $v>1$ such that
$$s_n = \lfloor un\rfloor + \lfloor vn\rfloor$$
for every positive integer $n$?
...

**8**

votes

**1**answer

478 views

### Does $(\mathbb{Z}/n\mathbb{Z})^2$ ever admit a difference set when $n$ is odd?

A difference set of a group $G$ is a subset $D\subseteq G$ with the property that there exists an integer $\lambda>0$ such that for every non-identity member $g$ of $G$, there exist exactly ...

**1**

vote

**1**answer

130 views

### Counting matrices of special types

How many symmetric and non-symmetric $n\times n$ matrices with $0/1$ entries are there such that every row is distinct and every column is distinct? (I am looking for a proof as well).
If only every ...

**8**

votes

**3**answers

378 views

### Disjoint Maximum Independent Sets in $alpha$-critical graphs

Let $G$ be an undirected, simple graph, and let $\alpha(G)$ denote the independence number of $G$, i.e., the size of a maximum independent set (stable set) in $G$. A graph is $\alpha$-critical if for ...

**3**

votes

**1**answer

144 views

### higher dimensional analogue of EGZ theorem

The EGZ theorem states that any multiset of $2n-1$ integers has a subset of size $n$ the sum of whose elements is a multiple of $n$.
Kemnitz-Reiher theorem is a 2-dimensional analogue of EGZ. Here is ...

**3**

votes

**1**answer

168 views

### Largest symmetric matrix given rank

Let $\mathscr{M}[n,d]$ be collection of $n\times n$ symmetric matrices with real entries from $\{0,1\}$ such that every row/column is distinct with sum of every row/column being $d$.
What is minimum ...

**10**

votes

**1**answer

545 views

### A circulant coin weighing problem

We are given $n$ coins, some of which are "real" and weigh $1$ and some of which are "fake" and weigh $0$. We have one "spring scale" which can weigh any subset of the coins. A classic question asks ...

**2**

votes

**1**answer

41 views

### Vanishing Restricted Isometric Constant

In compressed sensing, we are interested in the restricted isometry property. Suppose the design matrix is $n$ by $p$, consisting of $np$ iid $\mathcal{N}(0, 1/n)$ entries. Assume both $n$ and $p$ are ...

**-6**

votes

**0**answers

77 views

### A Paradox by a Variant of Von Neumann's coin toss [closed]

All biased coins are fair.
If I have a biased coin whose probability of heads is $p$, and keeps tossing it, and only stops when the number of heads equals tails, then each sequence I get has a ...

**11**

votes

**1**answer

174 views

### Complexity of planar scissor congruence

Two (not necessarily convex) poygons of equal area are scissor-congruent, i.e. both can be cut along a finite number of straight lines or segments into isometric pieces.
What can be said about the ...

**9**

votes

**0**answers

94 views

### Is there a nice formula for the “non-crossing substitution” of linear combinatorial species?

Background
A linear species is a functor
$$F : \mathrm{Lin} \to \mathrm{FinSet},$$
where $\mathrm{Lin}$ is the category of totally ordered sets and bijections and $\mathrm{FinSet}$ is the category ...

**8**

votes

**3**answers

632 views

### Why does the bitxor function appear in Nim?

I am conducting research in Combinatorial Game Theory (CGT). Although I have done a considerable amount of reading, I do not completely understand why the bit-xor function also known as the nim-sum ...

**4**

votes

**0**answers

125 views

### inequality in a shape of inclusion exclusion formula

I have two inequalities to show, both of which describe some probabilities. First I know how to handle, and it follows from applying arithmetic-harmonic mean inequality:
consider 9 numbers ...

**21**

votes

**1**answer

1k views

### Red-blue alternating paths

Suppose we have two simple graphs on the same vertex set. We will call one of them red, the other blue. Suppose that for $i=1,..,k$ we have $deg (v_i)\ge i$ in both graphs, where ...

**2**

votes

**1**answer

125 views

### Expected value (probability) maximization with binomial distribution

I need to solve an optimization problem that involves an expected value like
$$F(n,x) = \sum_{k=0}^n \binom{n}{k} p^k(1 - p)^{n - k} f(k,x).$$
Here $f(k,x)$ is actually a probability coming from a ...

**5**

votes

**0**answers

118 views

### Extrapolation between longest increasing and longest alternating subsequences

The question
When should we expect Tracy-Widom?
motivated me to post the following question, in which I have been
interested for a while. Let $f(n)$ be a function from the positive
integers to ...

**4**

votes

**1**answer

322 views

### The number of monotone full binary trees

Let $\rho$ be an equivalence relation on a semigroup $S$. A subsemigroup $S'$ of $S$ is called a $\rho$-cross-section of $S$, provided that $S'$ contains exactly one representative from each ...

**4**

votes

**0**answers

115 views

### Unique Nash equilibrium games

Multicast network design game is a special case of a general network design game (http://www.cs.cornell.edu/home/kleinber/focs04-game.pdf) in which there is a target vertex $t$ and $n$ rational ...

**1**

vote

**1**answer

155 views

### Existence of functions on finite sets with specific propertise

Let $\Omega$ be an universal set and $|\Omega|=N$, denote $\mathcal{F}$ to be the family of all subsets $\subset \Omega$ with cardinal $n$. We now define a function $f:\mathcal{F}\rightarrow \Omega$, ...

**4**

votes

**1**answer

181 views

### Large bicliques in r-partite graphs containing no independent sets having one vertex from each class

Let $G$ be a multipartite graph on $r$ classes, each containing $k$ vertices, such that there is no independent set which contains at least one vertex from each class. I believe such graphs contain a ...

**5**

votes

**1**answer

129 views

### partition of a convex set into squares

Let $P$ denote the perimeter function. It's not hard to prove that for any rectangle $R$ in $\mathbb{R}^2$, $R$ can be partitioned into a countable collection of squares $\{Q_k\}_{k=1}^{\infty}$ such ...

**12**

votes

**1**answer

169 views

### Asymptotics of coefficients of implicitely defined generating function

I have two integer sequences $\{a_n\}_{n=0}^\infty$ and $\{b_n\}_{n=0}^\infty$. Explicit formulas for the $a_n$ are known and their asymptotic growth is fully understood. My wish is to also understand ...

**1**

vote

**0**answers

99 views

### Fundamental theorems of invariant theory, twisted by a representation

Let $V$ be a finite dimensional complex vector space and let $G = \mathrm{GL}(V)$. The first and second fundamental theorems of invariant theory for $V$ give generators and relations for the algebra
...

**7**

votes

**1**answer

514 views

### Simplest form for sum of Binomial Expressions

How difficult is the problem of reducing the number of terms in a sum of binomial expressions? Formally:
Given $a_1, a_2, a_3, … a_n$, and $b_1, b_2, b_3, ... , b_n$, where $a_i, b_i \in \mathbb{Z}$, ...

**0**

votes

**0**answers

57 views

### Minimum rank of certain matrices

Let $\mathscr{M}[n]$ be collection of $n\times n$ matrices with real entries from $\{0,1\}$ such that every row is distinct and every column is distinct.
What is minimum real rank of matrices in ...

**0**

votes

**0**answers

38 views

### On subset of items in ordered list would like to calculate cardinality of set of orderings grouped by kendall tau distance

Let's say I have an ordered list of length $n$ which I will denote $12\ldots n$. There are $n!$ ways to rearrange the items in this list. Take a subset of the items in the list $B\subset ...

**3**

votes

**1**answer

141 views

### Products of relative prime numbers with least sum

Let $P(n)$ be the set of subsets $P$ of $\mathbb{N}$ with the properties
All elements of $P$ are relative prime to each other.
The product of all $k \in P$ is greater or equal to $n$.
Now let ...