Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.

learn more… | top users | synonyms (1)

2
votes
1answer
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
1answer
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
7answers
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
2answers
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
1answer
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
4answers
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
5answers
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
2answers
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
0answers
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
0answers
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
5answers
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
2answers
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
2answers
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
2answers
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
1answer
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
1answer
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
3answers
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
3answers
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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 ...