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)

20
votes
2answers
2k views

An unfair marriage lemma

I am looking for a citeable reference to the following generalization of Hall's Marriage Theorem: Given a bipartite graph of boys and girls. In addition to gender difference, they are divided into ...
5
votes
2answers
198 views

Ordered lattice point enumeration

I initially asked this question over at StackOverflow as it has algorithmic flavor to it, but I haven't been getting much traction so I thought I would probe the mathematics community. Setup: Let ...
7
votes
0answers
118 views

Some $q-$analogues of $ \sum\limits_{j = - k}^k {{{( - 1)}^{ j}}}\binom{n}{k-j}\binom{n}{k+j}=\binom{n}{k}.$

Let ${\left( {a;q} \right)_n}=\prod\limits_{j = 0}^{n - 1} {(1-{q^j}a} )$ and let $ {{n}\brack{k}}_q$ denote a $q-$binomial coefficient. I am interested in $q-$analogues of the identity $ ...
1
vote
1answer
84 views

Balls from bin with replacement, distinct elements, concentration inequality

Draw $n$ numbers, denoted by $a_1, a_2, \ldots, a_n$, from set $[n]$, that is, for each $i$, $a_i$ is a uniformly random number from $[n]$. Let $A = \{a_1, a_2, \ldots, a_n\}$. Then $$ ...
6
votes
0answers
92 views

The Maximum Number of Lines Contained in the Point Set of a Finite Projective Plane

Consider a finite projective plane of order $q$. Define $f(m)$ to be the maximum number of lines completely contained in any point set of size $m$, where $1 \leq m \leq q^2+q+1$. I would like to ...
9
votes
2answers
293 views

Determinant of a checkerboard Hankel matrix with Catalan numbers

My goal is to compute \begin{equation} I = \det \left(\mathbf{I} + \mathbf{A}\right) \end{equation} where $\mathbf{A}$ is a $n \times n$ checkerboard matrix filled with Catalan numbers: $$ \left\{ ...
4
votes
0answers
142 views

What is known about the complexity of this covering problem?

Let $G=(V,E)$ be a graph. A vertex set $X\subseteq V$ is called critical if $X\neq\emptyset$ and no vertex in $V\setminus X$ is adjacent to exactly one vertex in $X$. The problem is to find a vertex ...
15
votes
1answer
888 views

Evaluating a remarkable term for primes p = 5 (mod. 8)

Let $p > 3$ be a prime number, and $\zeta$ be a primitive $p$-th root of unity. I am interested in knowing the exact value of $$w_p = \prod_{a \in (\mathbb F_p^{\times})^2}(1 + \zeta^a) + \prod_{b ...
11
votes
2answers
460 views

“The Two Sheriffs” puzzle -2: threshold for security

I've already asked a question “The Two Sheriffs” puzzle with wrong assumption. Yoav Kallus in his amazing answer using Fano plane showed that the problem has a solution in the case of seven suspects. ...
2
votes
0answers
62 views

Edge-disjoint path-systems in infinite digraphs

Let $ D=(V,A) $ be a directed graph without backward-infinite paths and let $ \{ s_i \}_{i<\lambda},U \subset V $ where $ \lambda $ is some cardinal. Assume that for all $ u\in U $ there is a ...
3
votes
0answers
125 views

A Result of Anders Bjorner: Matchings in countably infinite geometric lattices of finite height

Let $L$ be a countably infinite geometric lattice of finite height $r\ge3$. (A geometric lattice of height $r$ is an atomistic semimodular lattice such that every maximal chain has $r+1$ elements.) ...
28
votes
1answer
1k views

“The Two Sheriffs” puzzle

This puzzle is taken from the book Mathematical puzzles: a connoisseur's collection by P. Winkler. Two sheriffs in neighboring towns are on the track of a killer, in a case involving eight ...
4
votes
2answers
203 views

How many simple cycles can a graph with $n$ vertices and $m$ edges have?

I am mainly interested in the smallest number of simple cycles a graph with $n$ vertices and $m$ edges must have. For example, if $m\le n-1$, this number is $0$, then if $n\le m \le 3(n-1)/2$, it is ...
7
votes
2answers
184 views

Decomposition of a cross-polytope into simplices

Consider the standard embedded $n$-cross polytope $P_n$ with vertices $\pm e_i \in \mathbb R^n$. Let us consider decompositions of this polytope into $2^{n-1}$ simplices, such that these simplices ...
4
votes
1answer
193 views

Young tableau with no i in row i, name that derangement

This question has its genesis in a group assignment: $k$ students are to be given oral exams. Each student will be asked one distinct question from $n$ questions given to them earlier, no two students ...
6
votes
2answers
110 views

Reference request: monochromatic paths in edge-colored complete graphs

Given $k,c \in \mathbb{N}$, let $P(k,c)$ be the minimum $n$ such that no matter how we color the edges of the complete graph $K_n$ with $c$ colors, there is always a monochromatic path of length $k$. ...
3
votes
1answer
150 views

Identify ring of polynomials symmetric under forgetting variables

I came across the following ring $A$, which appears as a Chow ring. I am wondering if it has been studied before; in particular, I am looking for a reference where this object might have been ...
7
votes
1answer
124 views

Is there a Degenerate Dependency Local Lemma?

The Lovasz Local Lemma has several generalizations, with names usually starting with L, such as Lopsided or Lefthanded. Here I ask whether another possible generalization (for which I could not yet ...
2
votes
0answers
52 views

Bounds on number of distinct substrings

I have a table with $r$ rows of length $\ell$, with each cell containing a letter from an alphabet $A$ of length $a$. I'm trying to determine the expected number of distinct strings of length $k$ ...
3
votes
1answer
85 views

congruence for Stirling numbers of the first kind

Suppose we write $s(n,k)$ for the Stirling numbers of the first kind. When $p$ is a prime number, I'm interested in knowing when $s(p^a, k)$ is divisible by $p^a$. So: What is known about ...
1
vote
1answer
122 views

Generating function for $t$-residues of partitions using Heisenberg + $\hat{sl_t}$ representation theory

Recall that for $t\geq2$, a partition is a $t$-core if none of its hooklengths is divisible by $t$. It is known that the $t$-cores are parametrized by ${\mathbb Z}^{t-1}$. More precisely, let ...
25
votes
0answers
621 views

3-colorings of the unit distance graph of $\Bbb R^3$

Let $\Gamma$ be the unit distance graph of $\Bbb R^3$: points $(x,y)$ form an edge if $|x,y|=1$. Let $(A,B,C,D)$ be a unit side rhombus in the plane, with a transcendental diagonal, e.g. $A = ...
3
votes
0answers
203 views

adding a boundary to the finite upper half-plane

Let $\Bbb{F}_q$ be a finite field, let $\delta \in \Bbb{F}_q$ be a non-square, let $\Bbb{F}_{q^2} = \Bbb{F}_q\big( \sqrt{\delta} \big)$ be the corresponding quadratic extension, and let ...
4
votes
2answers
144 views

The Hadwiger number of $L(K_n)$

For $n\in\mathbb{N}$ we consider the set $\{1,\ldots,n\}$ and define the line graph $L(K_n)$ of the complete graph $K_n$ as follows: $V(L(K_n)) = \big\{\{a,b\}: a,b\in \{1,\ldots, n\}, a\neq b ...
4
votes
1answer
125 views

Segments on a family of parallel lines

Let $\{l_i:i\in I\}$ be a family of parallel lines on the plane $\mathbb{R}^2$. Suppose for each $i\in I$ there is a closed segment $s_i\subset l_i$. Moreover, for each triple $i_1,i_2,i_3$ there ...
3
votes
3answers
346 views

When few simple conditions yield a unique intricate structure

If people were asked to do a brainstorming related to the title, everyone would probably come up with dozens of examples. Those could include things as different as the Mandelbrot set, Julia sets ...
3
votes
1answer
142 views

Is the number of vertices bounded for fixed max degree and fixed diameter?

Are there positive integers $\Delta, d$ such that the following statement is true? For every $n\in \mathbb{N}$ there is a graph $G = (V,E)$ such that $|V| = n$, $\Delta(G) \leq \Delta$ ...
7
votes
4answers
347 views

Is there a non-explicit characterization of the Specht modules?

It is a basic fact about the symmetric group $S_n$ that its irreducible representations are indexed by partitions of $n$. My question is, can the association between partitions and irreps be ...
4
votes
0answers
117 views

Pattern avoidance in Young diagrams

There has been lots of studies on pattern-avoiding permutations. There is also some work done on permutations whose permutation matrix fit in a diagram shape, and then do pattern avoidance on this ...
0
votes
1answer
92 views

Edge-disjoint cycles in graphs

Given a graph $G=(V,E)$ and a fixed integer $k$ are there any algorithms known which would find the maximum number of edge-disjoint cycles of length $k$ in $G$? If not is there a proof that this ...
11
votes
0answers
383 views

Transitivity of balanced mass transport in Z

Given two atomic measures $\mu$ and $\nu$ on $\mathbb{Z}$, write $\mu \sim \nu$ iff there exist countable decompositions $\mu = \mu_1 + \mu_2 + \cdots$ and $\nu = \nu_1 + \nu_2 + \cdots$ along with ...
5
votes
1answer
118 views

Time to generate a filled-in sub-checkered board

Take an $m \times n$ checkered board and one-at-a-time add a piece to an empty square. At what point are you guaranteed to have an $s \times t$ sub-board where all of its squares are filled? Here I ...
19
votes
5answers
818 views

Three-halves-free words (analogous to square-free)

A square-free word is a string of symbols (a "word") that avoids the pattern $XX$, where $X$ is any consecutive sequence of symbols in the string. For alphabets of two symbols, the longest square-free ...
3
votes
0answers
109 views

``Occasional'' Laurent phenomenon

This question is motivated by Richard Stanley's A question on the Laurent phenomenon (motivated by his answer to the question what is the probability that a scissor became the champion?). He asked ...
0
votes
0answers
39 views

Is there any analytically expressible choice of disjoint perfect matchings?

Consider being given a $d-$regular $(n,n)$-bipartite graph. We know that its edge set decomposes into $d$ disjoint perfect matchings. I want to know if there is a analytic way to pick such a ...
4
votes
1answer
120 views

Estimating the distribution of minimal hamming distances within a set of strings?

Is their an efficient mathematical way to estimate the distribution of minimal hamming distances for a set of random strings of length 8 over a 4-letter alphabet? E.g. given a set of 100-10,000 ...
2
votes
0answers
51 views

Is the size of maximum matching in vertex transitive 3-uniform hyper-graph on $n$ vertices always $\Omega(n)$?

What is the best known lower bound on the size of the maximum matching in a vertex transitive $3$-uniform hyper-graph?
3
votes
1answer
126 views

convex decompositions of the sphere

Consider a decomposition of the sphere $S^n$ into convex pieces (that is, every cell of the cell decomposition is convex, in particular, is contained in a hemisphere). Consider the $k$-skeleta of ...
8
votes
1answer
308 views

Transitive closure of balanced mass transport in Z (move to close)

Given two atomic measures $\mu$ and $\nu$ on $\mathbb{Z}$, write $\mu \sim \nu$ iff there exist countable decompositions $\mu = \mu_1 + \mu_2 + \cdots$ and $\nu = \nu_1 + \nu_2 + \cdots$ along with ...
3
votes
1answer
67 views

Dense high-degree sub-graphs of dense graphs

Let $G$ be a graph with $n$ vertices and $m$ edges, and let $d=\lfloor\frac{m}{n}\rfloor$ be the rounded-down average-degree. A lemma that is attributed to Erdos says that $G$ has a non-empty induced ...
0
votes
0answers
115 views

How large can a set of nearly equidistant points be?

Suppose that $D$ is a set of points in $\mathbb{R}^{k}$ such that all pairwise distances between them belong to $[1,1+\epsilon]$. It seems that such a set cannot be very large and that its ...
3
votes
0answers
142 views

Is there any good survey on the hook length formula and related topics?

I am recently doing some research related to the hook length formula. The hook formula counts the number of Young tableaux of certain type. I find there are plenty of research already been done and ...
38
votes
1answer
3k views

Mathematicians wearing hats on arbitrary total orders

I've been pondering the following generalisation of a famous problem (the special case where $T = \mathbb{N})$: Question: We have some totally-ordered set $T$ of mathematicians, each wearing a hat ...
3
votes
0answers
61 views

Matroid rank decay

Consider a uniform vector matroid $M(0)=U_{m,n}$ of rank $m$ with $n$ points, $n>m>2$ (you can think of it as a set of $n$ points in general position in vector space $F^m$ for some large field ...
2
votes
0answers
86 views

Applications of small Kakeya sets over finite fields

It was proved by Dvir that a Kakeya set in $\mathbb{F}_q^n$ has size at least $q^n/n!$, a bound which was later improved to $q^n/2^n$. For $n = 2$ and $q$ odd the exact bound is $q(q+1)/2 + (q-1)/2$ ...
5
votes
2answers
201 views

Combinatorial identity and Fuss-Catalan numbers

I would like to show that $$ \lim_{N\to\infty}\frac{1}{N^{np+1}}\frac1{p!}\sum_{j=0}^{p-1}(-1)^j\binom{p-1}{j} \left(\frac{\Gamma(N+p-j)}{\Gamma(N-j)}\right)^{n+1} =\frac1{np+1}\binom{(n+1)p}{p}, $$ ...
6
votes
0answers
259 views

Have topographs been studied before?

This is my first post on MO so I hope this question is suitable. I have quite a few definitions which I will need to state before my questions at the end of this post. Please let me know if anything ...
1
vote
0answers
135 views

Generalization of Little Fermat Theorem for a particular $a$ and perfect shuffles

I'm looking for the smallest $n\in \mathbb{N}$ that solves the following equation: $$2^n=1 \mod m$$ For an odd $m$. I know that Little Fermat Theorem and Euler Totient give me a solution but they ...
1
vote
0answers
196 views

What is the status on questions related to Bhargava's factorial function?

In Manjul Bhargava's The Factorial Function and Generalizations he motivates a new type of factorial $n!_S$ using by generalizing a few theorems like: For $k, l \in \mathbb{Z}$, we have $k! \times ...
1
vote
0answers
79 views

Notions of consistency / heterogeneity in sets of vector values?

The problem Let us consider a row vector u of size $n\in\mathbb{N}$, containing only binary values (0,1): $$u=(u_1 \cdots u_n), n\in\mathbb{N}$$ $$\forall i \in \{1\ldots n\}, u_i \in\{0,1\}$$ I ...