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
0answers
25 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 ...
9
votes
2answers
492 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
61 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
163 views

Mass Transportation Through Wonderful Roller

There is a wonderful ruller 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 ruller comes from this property ...
0
votes
1answer
50 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$, ...
2
votes
1answer
37 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
82 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
105 views

How compute combinatorial expression [on hold]

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
119 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 ...
-3
votes
0answers
56 views

Permutations with fixd points [on hold]

I am trying to write a java program that counts permutations of a string, I would like to check my results by hand, but I can remember (or find) the formula to count the number of permutations, and ...
2
votes
1answer
59 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 ...
6
votes
1answer
227 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
38 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
205 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
401 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 ...
0
votes
0answers
47 views

Probability of picking exactly $k$ number of same color balls from $n$ number of urns with nonuniform ball counts [migrated]

There are $n$ urns labeled as $1,2,3,....,n$. Each urn contains balls of $m$ different colors labeled as $1,2,3,...,m$. The number of $j_{th}$ color ball in the $i_{th}$ urn is denoted as $N_{ij}$. If ...
14
votes
2answers
336 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 ...
8
votes
0answers
100 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
112 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
189 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
117 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 ...
0
votes
0answers
35 views

Lattice isotopy type of uniform hyperplane arrangements

I am working on a problem related to the isotopy type of a certain class of hyperplane arrangements in $\mathbb{C}^{d}.$ For more references, compare Randell's work "Lattice-isotopic arrangements are ...
10
votes
1answer
502 views

Associativity of Kontsevich's star product up to second order

In Deformation quantization of Poisson manifolds, Kontsevich gives the quantization formula $$f \star g = \sum_{n=0}^\infty \hbar^n \sum_{\Gamma \in G_n} w_\Gamma B_{\Gamma,\alpha}(f,g).$$ He gives ...
0
votes
0answers
16 views

Sorting circles sizes with points in integers lattice [migrated]

I wrote a program to find all the circles with at least three points located at the integers grid. I started with smallest boxes (width >= height) calculating the radius of a circle with points ...
2
votes
2answers
118 views

How to calculate one Cauchy type determinant

As we know, a Cauchy determinant of size n admits the following explicit formula: $$\det \left(\frac{1}{x _i+y _j}\right) _{1\le i,j \le n}=\frac{\prod _{1\le i < j\le n} (x _j-x _i)(y _j-y ...
11
votes
0answers
288 views

Does Langton's ant cover every n by 6 gridded torus?

This post follows this other post about times cover by Langton's ant of $n$ by $n$ gridded torus. For $n$ by $n$ gridded torus, I've checked for $n \le 1000$ that the ant covers all. This fact needs ...
7
votes
0answers
139 views

What's the analogue of a Young symmetrizer in the Brauer algebra?

According to Schur--Weyl duality, the centralizer of $\mathrm{GL}(V)$ acting diagonally on $V^{\otimes N}$ is the group algebra of the symmetric group $\mathbb S_N$. An equivalent formulation is the ...
1
vote
0answers
110 views

Kripke frames as classes of partitions

Here's something I've been playing with off and on for a bit; I'm curious if anyone has seen it before. For this question, a Kripke frame $K$ is a finite reflexive directed graph. (Reflexivity isn't ...
5
votes
1answer
150 views

The Maximal $\ell_2$ norm of a signed sum of vectors

Suppose we have $n$ vectors in $\mathbb{R}^n.$ Consider the signed sum of these vectors: $$U(s_1,\ldots,s_n)=s_1 v_1+s_2 v_2 + \ldots + s_n v_n$$ where $s_j$'s can only take values of $+1$ or $-1.$ I ...
0
votes
0answers
14 views

Urn Ball Game - $m$ urns $n$ players Expected number of rounds the game to be played to get all the players selected [migrated]

This is an urn-ball game. There is a coordinator and there are $m$ urns and $n$ players. Each player has got one ball each. The game happens in rounds. In a specific round the users throw balls at ...
1
vote
1answer
132 views

How many finite subsets in $\mathbb{Z}^d$ have a given sum of squares?

Let $|\cdot|$ denote the usual norm in $\mathbb{Z}^d$. Given a finite subset $S \subset \mathbb{Z}^d$, let $\varphi(S) = \sum_{z \in S}|z|^2$. Given $m \in \mathbb{N}$, what is the size of ...
3
votes
0answers
78 views

Looking for a natural definition of certain polynomials associated with skew Young diagrams

Consider a connected skew Young diagram in the English notation and then rotate it counterclockwise by $\pi/4$. This rotation can be avoided by simply replacing "rows" by "diagonals" in the below, but ...
0
votes
0answers
107 views

Generating function for reciprocals of Stirling numbers?

Is there an (ordinary or exponential) generating function for the reciprocals $\frac{1}{s(n,k)}$ of the Stirling numbers of the first kind? Also, is there some general way to find generating ...
3
votes
0answers
58 views

Which (polytopal) fans/polytopes are secondary?

Let $P$ be a (d-1)-dimensional polytope with $n$ vertices that sits in an affine hyperplane in $\mathbb{R}^d$. The secondary fan of $P$ is a polytopal fan in $\mathbb{R}^n$ with $d$-dimensional ...
0
votes
0answers
80 views

Adjacency graph of a polyomino

Given a polyomino, the "adjacency graph" has one vertex for each tile and an edge connecting tiles which are adjacent (diagonal doesn't count). Is anything known about which graphs can be the ...
18
votes
0answers
407 views

Time for Langton's ant to cover a “square” torus

Langton's ant is a cellular automaton running as follows: Squares on a plane are colored variously either black or white. We arbitrarily identify one square as the "ant". The ant can travel ...
16
votes
0answers
223 views

Deforming a basis of a polynomial ring

The ring $Symm$ of symmetric functions in infinitely many variables is well-known to be a polynomial ring in the elementary symmetric functions, and has a $\mathbb Z$-basis of Schur functions ...
9
votes
5answers
608 views

Combinatorial\Probabilistic Proof of Stirling's Approximation

Stirling's approximation is the following well-known asymptotic result: $$n! \approx \left(\frac{n}{e}\right)^n \sqrt{2 \pi n}$$ This result has several analytical proofs, for example via Laplace's ...
14
votes
1answer
583 views

In how many steps a random walk visits all the elements of a finite group, with a probability 1/2?

This question is a variation of the return to the origin problem. Let $G$ be the finite group $\mathbb{Z}/n \times \mathbb{Z}/n$ and let the random transformation $T: G \to G$ such that $T(a,b) = ...
7
votes
1answer
207 views

Yet another Erdős–Szekeres game

Given $n$. Two players in turn write different real numbers $x_1,x_2,x_3,\dots$ The player after whose turn there is a monotone subsequence of length $n$ loses. I guess that the question 'who wins' ...
8
votes
1answer
463 views

Erdős-Szekeres game

Given $n$. Two players in turn mark points on the plane. No three may be collinear, no $n$ may form a convex $n$-gon. The player who does not have legal move loses. Who has a winning strategy?
9
votes
1answer
326 views

Continuous functions and 2-bushy trees

The following problem was asked by Joe Miller in the fall of 2010 at a bar in Madison. A subtree $T \subseteq 4^{< \omega}$ is $2$-bushy if for some node $\sigma \in T$, every node above $\sigma$ ...
0
votes
1answer
81 views

A particular argument in the review on expanders by Hoory-Linial-Wigderson

I am thinking about the third bullet point on page 455 here, http://www.ams.org/journals/bull/2006-43-04/S0273-0979-06-01126-8/ Can someone explain what is the argument there which seems to conclude ...
4
votes
1answer
430 views

How to prove this identity on double summation series?

I suspect the following identity is valid, but I can not prove it. I just calculate it numerically. ...
1
vote
1answer
140 views

Asymptotic of a certain double sum involving binomial coefficients

Consider sums of the form $S(n)=\sum^{n}_{m=0}\sum^{m}_{k=1}2^{2k+m+1}{n-m+k+1 \choose 2k+2}{m \choose k}$ I am interested in the asymptotics of $S(n)$ as $n\to \infty$. More precisely I would ...
6
votes
1answer
137 views

Probability of a graph procedure

We are going to build $K_n$ one edge at a time. Begin with the empty graph on $n$ vertices. Take a random permutation of the edges of $K_n$ and, one at a time, place the edges onto the graph (so, ...
3
votes
0answers
93 views

Hypercube edge-coloring problem

Question: Is there a pairing (a fixed point free involution) of the vertices of the $n$-dimensional cube graph, and a $2$-coloring of its edges such that the number of color changes needed to get from ...
5
votes
1answer
280 views

Infinite sequence avoiding a countable set of words

As an application in group theory, I would need an infinite sequence over a finite alphabet, that avoids a sequence of words $w_i$, where the length of $w_i$ is such that $l(w_i) > 10^8 ...
3
votes
3answers
317 views

Aperiodic graphs

The concepts of being non-periodic and aperiodic for tilings have obvious versions for connected graphs with a countable set of vertices and a finite number of edges meeting at each vertex. A graph ...
6
votes
0answers
119 views

Asymptotics of the multipartition function

Recall that the multipartition function $p_k(n)$ counts the number of $k$-tuples of partitions $\lambda^1,\ldots,\lambda^k$ of numbers $a_1,\ldots,a_k$ with $a_1+\cdots+a_k=n$. It has a generating ...