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)

5
votes
0answers
196 views

Partitions of $\mathbb{F}_2^n$ related to perfect $1$-error correcting binary codes

Edit. After a computer search found an example for $n=8$, I've rephrased my original question as a conjecture. This question is motivated by the existence of perfect $1$-error correcting binary codes,...
3
votes
1answer
205 views

Maximal Coset representative for the Weyl group of a Parabolic

Let $G=SL_n$ and let $P_i$ be a maximal parabolic corresponding to a simple root say $\alpha_i$. Let $W_{P_i}$ be the Weyl group of $P_i$. Is there an efficient way to compute the longest coset ...
10
votes
1answer
287 views

Question on a paper by Benjamini/Kozma/Wormald about a “well known fact”

In "The mixing time of the giant component of a random graph" by the aforementioned authors, in the last proof on page 19 it says something along the lines of "It is well known and easy to verify ...
8
votes
1answer
329 views

Computational complexity of computing simplicial homology

Is there any literature regarding the fastest known algorithm to compute the homology groups of a simplicial complex (on n vertices)? What about computing the fundamental group? The context is to tell ...
1
vote
0answers
78 views

Does the Ruzsa-Szemeredi Theorem also capture graphs decomposable into *nearly* induced matchings?

The well-known Ruzsa-Szemeredi Theorem states that a graph whose edges can be partitioned into $n$ induced matchings has at most $\frac{n^2}{RS(n)}$ edges, for some slow-growing function $RS(n)$. Now,...
1
vote
1answer
76 views

Hyperplane generic to a given arrangement

At the moment, I am reading the paper "on the connectivity of the realization spaces of line arrangements" of Nazir and Yoshinaga. I would like to extend their Lemma 3.2 to higher dimension. However, ...
5
votes
2answers
172 views

A follow up question to: Number of walks on integer lattice with self-edge at zero

Let $a(n)$ be the number of lattice paths in ${\mathbb{Z}^2}$ of length $n$ which start at the origin $(0,0)$ and end up at $(n,0)$ and have only up-steps $U:(i,j) \to (i + 1,j + 1)$, down-steps $D:(...
3
votes
2answers
220 views

Combinatorial interpretation for coefficients of reciprocal of power series

I've seen a number of combinatorial interpretations for the coefficients of the compositional inverse (aka reversion) of a power series. Is there a known combinatorial interpretation for the ...
0
votes
0answers
372 views

Number Theory and d-Self-Contained Numbers

Given any natural number $N = a_{n}a_{n-1}\ldots a_{1}$, let us associate to it the set $S_{N} = \bigcup_{j=1}^{n}\{(a_{j},j)\}$. We're going to define a d-self-contained number as any natural number ...
1
vote
1answer
118 views

estimating binomial coefficients

There is a beautiful paper on the arXiv by Andrew Suk containing an asymptotic result about the Erdös-Szekeres convex polygon problem. I am struggling with one of the estimates he makes on page 4. He ...
2
votes
1answer
79 views

An inequality on partitions into distinct bounded parts

Let $P(n,m)$ denote the set of all positive integer partitions of $n$ into parts that are pairwise distinct and bounded by $m$. Let $p(n,m) = |P(n,m)|$. After some numerical experiments it appears $...
0
votes
1answer
90 views

Exact formula for computing n-step transition probability of random walks with self-transitions

Consider a semi-infinite random walks $X_n$, $n=0,1,2,\ldots$, whose state space is a set of consecutive integers and whose one-step transition probabilities are $P_{ij}=\mathrm{Pr}\{X_{n+1}=j|X_n=i\}$...
2
votes
0answers
203 views

On the size of residue class

Let $n \in \mathbb{N}$ be a odd number. Let $S \subseteq \{1,3,5,7,...,n-2,n\}$ and $|S|$ is even number. Let $R_i^k=\{a \mid a \in S \text{ } \&\text{ } a\equiv i \text{ }(mod \text{ } k)\}$ ...
4
votes
1answer
213 views

Number of walks on integer lattice with self-edge at zero

Consider the graph with vertices $V=\mathbb Z$ and edges $$E=\{(n,n+1):n\in\mathbb Z\}\cup\{(0,0)\},$$ that is, the usual integer lattice with a self-edge at zero. For some fixed parameters $a,b,n\in\...
1
vote
0answers
97 views

A two variable recurrence relation with conditionals

I have arrived at the combinatorial problem of enumerating certain types of ballot paths. This has led to analyzing the sequence defined by the following recurrence $$ f(n,m) = \begin{cases} f(n, \...
0
votes
2answers
46 views

Make multiple batches of maximum size, different sized objects

I am a software developer with a rather simple problem. I don't really know how to express it in mathematical terms - I'll just try to write it down: I have multiple different files... let's say 20 ...
8
votes
3answers
577 views

Is there a 2-connected k-regular graph without Hamiltonian path?

In this paper (Construction 2.6 p860) the authors have built examples of connected $k$-regular graph without Hamiltonian path, but with a cut-vertex (i.e. it is not $2$-connected). Question: Is ...
2
votes
0answers
182 views

Card Game Feasibility

We play the following card game: We are given a deck with $M$ cards in different colors $c\in\left\{ 1,\dots,C\right\}$. There are $D$ cards from each color, so $M=CD$. We wish to place a subset of ...
1
vote
1answer
376 views

Doing graph theory after a thesis in pure mathematics [closed]

I've just went through the 1st year of my PhD in France, it is related to Floer Homology. I didn't know what it was really about at that time, I chosed this subject because I thought it would combine ...
4
votes
2answers
287 views

Create a graph with a specified number of spanning trees

I read that one of the current challenging problems in mathematics is constructing a minimal graph with a specified number of spanning trees (say, $k$). However, is there a quick way to create some ...
8
votes
0answers
261 views

What is intuition behind sets with more sums than differences?

There exist finite sets $A$ in, say, $\mathbb{Z}$, such that $|A+A|>|A-A|$. The minimal such set contains 8 elements and consists of, say, 0, 2, 3, 4, 7, 11, 12, 14. How should I find such an ...
4
votes
1answer
266 views

A variant of bin-and-ball problem

We have $n$ balls, each belonging to a group (e.g, color). There are $g$ groups ($g$ may be large but $g=o(n)$). We sequentially put the balls into $m$ bins in the following way: for each ball, we ...
4
votes
1answer
197 views

Collecting stones in n buckets

There are $n$ stones distributed in $n$ buckets (initially one stone in each bucket). At each step the content of each bucket is put in a random bucket, chosen independently out of a set of $n$ new ...
4
votes
1answer
154 views

Sum of Young symmetrisers of a given shape

Preliminaries and notation: Let $n\in \mathbb{Z}_{>0}$ and $\lambda=(\lambda_1,\lambda_2,\dots,\lambda_s)\vdash n$ be a partition. Given a Young diagram of shape $\lambda$, we can associate it ...
1
vote
0answers
32 views

Possible configurations of NR red balls and NB blue balls on a circle of L sites with D doubly occupied sites and B bonds (occupied nearest neighbors) [closed]

I am a physicist working on metal-insulator transition in crystalline materials due to Coulomb interaction between their electrons (with both spins up and down) depending whether they occupy the same ...
4
votes
0answers
175 views

Enumerating a class of polynomials

How many equivalence classes of $\Bbb F_2[x,y]$ polynomials with $x$ degree $n_x$ and $y$ degree $n_y$ are there such that each $y^i$ coefficient (polynomial in $\Bbb Z[x]$) is distinct and $x^i$ ...
1
vote
1answer
201 views

Simplify a equation

I have a problem simplifying the summation here: $$ \sum_{x=0}^{n}\sum_{y=0}^{x} {n\choose{x}} {x\choose{y}} y!(x-y)! $$ The last three terms can be simplified to x!, so the current summation ...
2
votes
0answers
71 views

Effective “almost enumeration” of monotone boolean functions

Denote by $\mathcal{M}(n)$ the set of all monotone functions $\{0,1\}^n \to \{0,1\}$. Can $\mathcal{M}(n)$ be represented as $\mathcal{M}(n) = \{ f(t) | t\in \{0,1\}^k \}$ such that: 1) $k = \log |\...
10
votes
1answer
214 views

Looking for a good terminology for permutations having no substring

What is the good name for permutations of [1,...,n+1] having no substring [k,k+1] http://oeis.org/A000255 ?
1
vote
0answers
150 views

How is the Penrose tiling decapod count of 62 calculated?

From Martin Gardner's 'From Penrose Tiles to Trapdoor Ciphers' From page 14, Chapter 1; https://www.maa.org/sites/default/files/pdf/pubs/focus/Gardner_PenroseTilings1-1977.pdf "Any spoke of the ...
2
votes
1answer
85 views

Transformation inverting distances between two sets of diameter 1

Let $S_1, S_2 \subseteq \mathbb{R}^2$ be two finite disjoint sets of points in the plane with $\texttt{diam}(S_1) \leq 1$ and $\texttt{diam}(S_1) \leq 1$. Does there always exist a transformation $f: ...
10
votes
0answers
116 views

Asymptotics of subgraph densities in graphons

In Pittel (1989)'s solution to a problem of Knuth (1976) on the expected number of stable matchings between $n$ men and $n$ women under uniform random preferences, it was shown that, as $n \to \infty$,...
3
votes
2answers
146 views

How many cuts are required for a weighted-proportional cake-cutting?

In proportional cake-cutting, there are $n$ agents with equal entitlements to a "cake" (an interval). Each agent $i$ has a nonatomic value measure $V_i$ over the cake, and it is required to create a ...
2
votes
1answer
75 views

How a “sequentially Cohen–Macaulay” simplicial complex relates to “Cohen–Macaulay” simplicial complex?

Let $\Delta$ be a simplicial complex on $[n]$ of dimension $d − 1.$ Let $0\le i\le d-1.$ One defines the pure i_th skeleton of $Δ$ to be the pure subcomplex $\Delta(i)$ of $\Delta$ whose facets are ...
4
votes
0answers
119 views

Characterizing the RSK corespondance

The Robinson-Schensted-Knuth correspondence is an algorithm which takes as input a word $w$ on the alphabet $\{1,\dots,n\}$ of length $k$ and returns a pair of a tableau $P(w)$ and a standard tableau $...
3
votes
1answer
249 views

Comparison nauty vs. bliss of canonical form of bipartite graphs

I need to compute canonical forms of many (~10^6-10^8) vertex-facets incidence graphs of polytope. Two rather big examples I want to consider are the 600-cell with 120 vertices and 600 facets (...
2
votes
1answer
347 views

Can the Units of a Cubic Field be Proven from Pigeonhole Principle alone?

I would like to run through the proof of Dirichlet Unit Theorem for a cubic field. Let's try $\mathbb{Q}[x]/(x^3 - x - 1)$. This has 1 real root and 2 complex roots (or embeddings). The units in ...
-4
votes
1answer
88 views

Expression for a complex summation involving factorial [closed]

It is known that $\sum_{k = 0}^{n } {n \choose k}(k!) = \lfloor e \cdot n! \rfloor $ But is it known what $\sum_{p = 0}^{n} \sum_{q = 0}^{n - p} {n \choose p}{{n - p} \choose q} p! \cdot q! \cdot (n-p-...
0
votes
1answer
39 views

Augmention property of matroid along perfect matching

Let M be a matroid of rank k, B a base, X a set of rank rank(X) < k, and P a perfect matching of the complete bipartite graph (X, B). Is it true that there exists an edge (x, b) of P augmenting X (...
3
votes
1answer
124 views

Lower bound construction for Multidimensional Szemerédi's Theorem

The Multidimensional version of Szemerédi's theorem given by Theorem 10.2 in Tim Gower's paper from 2007 has the following statement. Let $\delta>0$ and $k\in\mathbb{N}$. Then if $N$ is ...
5
votes
1answer
170 views

Subgroup ranks of the symmetric group

It's well known that every subgroup $G$ of $S_n$ has a generating set of size at most $n-1$ and that this generating set can be found algorithmically (by Jerrum's filter) I have heard many times a ...
0
votes
0answers
61 views

Number of polyhedra with N faces?

A. Up to isomorphism, how many polyhedra with N faces are there? Assume each face can be a triangle, square, pentagon, hexagon, etc... Furthermore each edge can be resized to any nonzero positive ...
2
votes
0answers
77 views

Enumerating group actions with constrained images, up to symmetries

Consider the following combinatorial problem: Let $G$ be a finite group, and $X = \sqcup_{i\in I} X_i$ be a finite set. Suppose that for each $g\in G$ and $i\in I$ we have sets $Y_{g,i} \subset ...
3
votes
1answer
105 views

Base decomposition of matroids

I want to find a generalization of the idea that, in a graphic matroid, every base can be decomposed on the stars (edges adjacent to a vertex). For example one could say that a matroid $M$ of rank $k$...
8
votes
1answer
276 views

How many chromatic polynomials of planar maps are there?

Let P(n) be the set of polynomials that can occur as the chromatic polynomial of a planar map with n countries. What is known or conjectured about the growth of |P(n)|? PS: Thanks Gerry and Noam, ...
9
votes
0answers
195 views

Greedy permutation of the set $\{1,2,\dots,n\}$ and prime numbers

Answering this question, another question came to my mind. For which $n$ will the greedy algorithm work? We define a sequence of natural numbers $x_n$ recursively: $$x_1 =1,$$ $$x_n \mbox{ is the ...
6
votes
1answer
126 views

Number of linear orderings of a set to have balanced frequencies of triple orders

Let $S$ be a set of $n$ elements and let $Q = (s_1, s_2, \ldots, s_n)$ be a linear ordering of $S$. We write $s_i <_Q s_j$ when $s_i$ appears before $s_j$ in $Q$. I want to construct a set (or ...
0
votes
0answers
26 views

Possible Number of Repetation of a Submatrix

Notation: $H$ is the adjacency matrix of graph $H'$ respectively. $H_k$ is the block or sub-matrix of matrix $H$. The adjacency matrix of graph $H_k \cup H_e$ (subgraphs of $H'$) is $M_{(k,e)}$ ...
4
votes
1answer
245 views

Imprimitive solutions to $x^2+y^3=z^7$

Poonen, Schaefer, & Stoll give the primitive solutions to $x^2+y^3=z^7$: $$ (±1, −1, 0), (±1, 0, 1), ±(0, 1, 1), (±3, −2, 1), (±71, −17, 2),\\ (±2213459, 1414, 65), (±15312283, 9262, 113), (±...
21
votes
5answers
1k views

For which $n$ is there a permutation such that the sum of any two adjacent elements is a prime?

For which $n$ is it possible to find a permutation of the numbers from $1$ to $n$ such that the sum of any two adjacent elements of the permutation is a prime? For example: For $n=4$ the permutation $...