# Tagged Questions

**5**

votes

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**2**answers

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

**2**answers

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**0**answers

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

**2**answers

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

**3**answers

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

**0**answers

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

**1**answer

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

**2**answers

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**0**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**0**answers

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

**2**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**0**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**5**answers

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 $...