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)

1
vote
1answer
113 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
588 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
196 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 ...
3
votes
2answers
138 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
115 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
340 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 ...
2
votes
1answer
133 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$ ...
6
votes
4answers
317 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
113 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
68 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
372 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
113 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
793 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
105 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
38 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
114 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
47 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
124 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
302 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
64 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
105 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
137 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 ...
37
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
59 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
78 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
175 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}, $$ ...
5
votes
0answers
252 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
130 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
180 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
74 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 ...
1
vote
1answer
100 views

Dense symmetric unitary integer matrix?

Can someone give me a nontrivial example of a symmetric unitary integer matrix? I'm looking for something as dense as possible (i.e., not too many 0's); 5 <= size <= 8 would be ideal.
7
votes
0answers
133 views

Combinatorics of palindromic decompositions

This is sort of a companion to my question Number of trivializations of a trivial word in the free group (which in turn is motivated by my earlier question here). It turns out that that question may ...
16
votes
7answers
2k views

Are there any Algebraic Geometry Theorems that were proved using Combinatorics?

I'm collaborating with some algebraic geometers in a paper, and when writing the introduction I mentioned the interaction of Combinatorics and Algebraic Geometry, and gave some examples like the ...
-2
votes
1answer
110 views

About structure of the set of perfect matchings of $K_{n,n}$

Are there any special properties known about the set of perfect matchings of $K_{n,n}$? Like any global structure of this set? Some natural way to partition it? Like is there some algebraic structure ...
6
votes
0answers
231 views

Mass Transportation Through Wonderful Roller

There is a wonderful roller that transports mass from A to B and there is a pile of sand with weight $W$ in point A and we want to transport it to B. Wonderfulness of roller comes from this property ...
1
vote
1answer
139 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$, ...
3
votes
1answer
70 views

Is the union of strongly base-orderable matroids strongly base-orderable?

A matroid is said to be strongly base-orderable if for any two bases $B_1,B_2$ there is a bijection $f:B_1 \to B_2$ such that for any $S\subseteq B_1$ set $(B_1 \setminus S) \cup f(S)$ is also a base. ...
5
votes
0answers
97 views

For which sidelengths are there polyominos composed of three squares that tile the plane?

Given three naturals $a<b<c$. We consider polyominos, connected or not, which are composed of three squares of sides $a,b,c$. How can one characterize all triples $a,b,c$ for which such a ...
-1
votes
1answer
118 views

How compute combinatorial expression [closed]

How compute $\sum_{j=1}^k \binom{x}{j}\binom{k-1}{j-1}\alpha^j, \quad x, \alpha\in\mathbb{R}$
2
votes
1answer
139 views

How to choose a random proper coloring

I am studying proper colorings of complete bipartite graphs and I'd like to be able to pick a random proper coloring and the compute some things about it. Recall that a proper coloring of a complete ...
2
votes
1answer
66 views

Are there non-isomorphic graphs with rationally orthogonal similar adjacency matrices?

Let $A_G,A_H$ be the adjacency matrices of two non-isomorphic graphs. Let $P$ be orthogonal matrix with rational entries. Is it possible $A_G = P^{-1}A_H P$? Paper gives algorithm for ...
10
votes
1answer
347 views

Number of trivializations of a trivial word in the free group

Let $M$ be the free monoid on $2n$ generators $x_1,X_1,...,x_n,X_n$ and consider the set $T$ of all those elements of $M$ which map to 1 of the free group on $x_1,...,x_n$ under the homomorphism $\pi$ ...
0
votes
0answers
41 views

addition chains for products of relatively prime factors

Suppose I have a set $F$ consisting of relatively prime factors (e.g. $\{ 5, 7, 9, 13, 17 \}$) and the set $P = \{\prod_{f \neq f_i}f \} $ consisting of the products of N-1 factors in $F$ (e.g. ...
5
votes
2answers
316 views

When are the adjacency matrices of non-isomorphic graphs similar?

From Wikipedia. In linear algebra, two n-by-n matrices A and B are called similar if $$ B = P^{-1} A P$$ for some invertible n-by-n matrix $P$. If $P$ is a permutation matrix, $A$ and $B$ are ...
13
votes
1answer
466 views

Enumeration of $0-1$ matrices with determinant $1$

Has the number $f(n)$ of $n \times n$, $0{-}1$ matrices whose determinant is $+1$ been enumerated? E.g., for $n{=}2$, there are $f(2)=3$ such matrices: $$ \left( \begin{array}{cc} 1 & 0 \\ 0 ...
14
votes
2answers
366 views

Can every tromino (including those with gaps) tile the plane?

I've generalized trominos to include "gaps", i.e. they are formed by removing all but $3$ squares from an $n$-omino where $n$ is finite. The generalized trominos pictured above can tile the plane ...
9
votes
0answers
117 views

Why must commuting maps (of an interval) without common fixed points have at least 11 fixed points for the composition?

I've been looking at the examples of commuting functions on a closed interval which have no common fixed points. These were discovered in 1967 by William M Boyce and J Philip Huneke. Earlier work by ...
1
vote
1answer
165 views

Creating a Latin rectangle from a projective plane

Given a projective plane I'd like to form a latin rectangle from the lines. In particular, I'd like to take each line from the plane, order the elements in some way, and stick them into the matrix as ...
0
votes
2answers
215 views

Generalized expression for balls and bins problem

$n$ number of balls are thrown randomly to $m$ number of bins, standing in a row. The balls are labeled as $1,2,3,....n$ and bins are also labeled as $1,2,3,...,m$. The probability of $i_{th}$ ball ...
1
vote
0answers
122 views

Surjective marriages

Let $M, W\neq \emptyset$ be sets and $K\subseteq M\times W$. We say that $(M, W, K)$ has a marriage if there is an injective function $f:M\to W$ such that $f\subseteq K$. If $(M,W, K)$ has a ...