# Tagged Questions

**1**

vote

**1**answer

99 views

### Convexity of truncated expectation

Let $k, n$ be two positive integers with $k \leq n$, and let $P = \{ (x_1, \dots, x_n) \in [0, 1]^n : \sum_i x_i = k \}$.
Given $x = (x_1, x_2, \dots, x_n) \in P$, let $X_i$ be the random variable ...

**8**

votes

**1**answer

677 views

### A Zero-Multiplicity Problem Related to Foulkes' Conjecture

I'm a combinatorialist that is interested in estimating multiplicities of irreps of $1^{S_{kn}}_{S_k \wr S_n}$ (the action of symmetric group on uniform partitions). I'm aware of the difficulty (or ...

**0**

votes

**2**answers

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

**3**

votes

**1**answer

95 views

### Catalogs/numbers/constructions of non-isomorphic conference matrices

I am interested in complete catalogs of non-isomorphic conference matrices, similar to those of Hadamard matrices. Do such catalogs exist? If yes, then where could they be found, and what is an ...

**2**

votes

**0**answers

43 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

118 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

**1**answer

104 views

### Counting bounded genus non-isomorphic graphs

What is the number of non-isomorphic $2n$ vertex balanced bipartite graphs of degree at most $d$ and genus $g$?
I am most interested in $d\leq3$ and $g=0$.

**4**

votes

**1**answer

216 views

+50

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

**1**

vote

**0**answers

45 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, \...

**7**

votes

**3**answers

498 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

131 views

### Card Game Feasibility 2

We play the following card game:
We are given a deck of $M$ unique cards, each with a color $c\in\left\{ 1,\dots,C\right\}$ , and a number $d\in\left\{ 1,\dots,D\right\}$, so $M=CD$.
We wish to ...

**8**

votes

**1**answer

72 views

### Schur positivity on 2 letter alphabets implies Schur-positivity on n letters?

Suppose we have a symmetric polynomial $P$ in $n$ variables.
We can partition this alphabet into sets with one or two letters, e.g. ${ {x_1}, {x_2, x_3}}.
We can thus see $P$ as an element in $Q[x_1]...

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

**11**

votes

**2**answers

2k views

### Subdivision of triangles into congruent triangles

Recently some old notes of mine have gotten me to thinking about the problem of subdividing a triangle into $N$ smaller triangles, all congruent to one another. A little thought shows the following ...

**1**

vote

**1**answer

327 views

### Doing graph theory after a thesis in pure mathematics [on hold]

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

**8**

votes

**0**answers

649 views

### Path connected set of matrices?

Consider the collection of $n$ by $n$ matrices
$$S=\{ A: A_{ij}\le0,\quad (-1)^{c_i}\det A(P_i;Q_i)<0 \quad \text{for} \quad i=1,\ldots, k\}$$
where $c_i\in \{0,1\}$, $P_i$ and $Q_i$ are disjoint ...

**3**

votes

**2**answers

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

**0**

votes

**1**answer

72 views

### Choosing directed subgraph in a triangulation

Consider triangulation $T.$
Is it always possible to choose such a subgraph $H$ of $T$ that has a common edge with every face of $T$ and can be directed in such way that indegrees of all vertices of ...

**3**

votes

**1**answer

77 views

### Generating Uniquely k-Optimal Point Sets

This question is motivated by the observation that finding an optimal tour through a set of points in the Euclidean plane is especially simple, if the points are in convex configuration and, that the ...

**3**

votes

**2**answers

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

**1**

vote

**1**answer

154 views

### Finding many disjoint sub-trees with many leaves

Let $T$ be a rooted binary tree with $L$ leaves, and let $\ell$ be a natural number smaller than $L$. The question is what is the maximal number of disjoint rooted sub-trees with at least $\ell$ ...

**3**

votes

**2**answers

112 views

### Neighbourhood of a word and Levenshtein distance

The Levenshtein distance or Edit distance $$ lev(U,V) $$ between two strings $U$ and $V$ over a finite alphabet $\Sigma$ of size $ \left| \Sigma \right| = \sigma ,$ is the minimal number of insertions,...

**8**

votes

**0**answers

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

**10**

votes

**7**answers

1k views

### Where on the internet I can find database of graphs?

I am studying graph algorithms.
I need database of graphs on which I can test my algorithms.
Where can I find reliable database of graphs of all kinds?
Thanks!

**1**

vote

**1**answer

238 views

### Some divisibility constraints in Frobenius coin problem

Let's say that the linear form $ax+by$ represents $n$ if $ax+by=n$ for some positive integer $x$ and $y$.
Call a pair $(a,b)\in\Bbb N\times\Bbb N$ with $\mathsf{gcd}(a,b)=1$ excellent if linear form ...

**4**

votes

**1**answer

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

**4**

votes

**0**answers

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

**3**

votes

**1**answer

133 views

### Stirling numbers of the second kind with maximum part size

The stirling number of the second kind $S(n,k)$ counts the number of partitions of the set $[n]$ into $k$ non-empty parts. I found a definition for the numbers called the $r$-associated stirling ...

**1**

vote

**1**answer

41 views

### How to generate a Latin square $M'$ in the same main class as $M \in \mathrm{LS}(9)$ which agrees with $L$ in the most cells?

I'm brainstorming an idea for storing a compressed list of main class representatives of Latin squares of order $9$. One way to compress the list would be to store one Latin square $L_1$, and for $i \...

**3**

votes

**1**answer

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

**19**

votes

**1**answer

1k views

### Simplest form for sum of Binomial Expressions

How difficult is the problem of reducing the number of terms in a sum of binomial expressions? Formally:
Given $a_1, a_2, a_3, … a_n$, and $b_1, b_2, b_3, ... , b_n$, where $a_i, b_i \in \mathbb{Z}$, ...

**12**

votes

**0**answers

450 views

### Possible orders of products of 2 involutions which interchange disjoint residue classes of the integers

Definition / Question
Definition: Let $r(m)$ denote the residue class $r+m\mathbb{Z}$, where
$0 \leq r < m$.
Given disjoint residue classes $r_1(m_1)$ and $r_2(m_2)$, let the class transposition
$...

**0**

votes

**0**answers

15 views

### Correlation matrices: How to find the 4 least correlated elements (between them) among 10 [closed]

I'm currently working on shopping zones (in large towns) products types correlation matrices.
matrix example link
This example matrix is small, only 10 zones, but some matrices can have up to 50 ...

**3**

votes

**1**answer

114 views

### Choosing $K$ “centers” from the space of permutations

Let $\Pi$ denote the space of all permutations of $\{1,\dots,n\}$, and let $d(\cdot,\cdot)$ be a metric on $\Pi$. Suppose I am given a large integer $K$ and I have to select $K$ permutations $\pi_1,\...

**1**

vote

**0**answers

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

**3**

votes

**1**answer

241 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 (...

**1**

vote

**1**answer

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

**5**

votes

**1**answer

290 views

### Paley graphs over $p^{2}$ vertices

I have proved that every Paley graph $P(p^{2})$ over $p^{2}$ vertices, where $p\geq 5$ is a prime number has a cospectral mate, i.e. for every prime number $p\geq 5$ there exists a graph $\Gamma_{p}$ ...

**2**

votes

**0**answers

56 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 |\...

**1**

vote

**0**answers

121 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

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

**5**

votes

**1**answer

683 views

### Is there a name for this fast growing function?

Define $F(n,i)=\prod_{j=1}^nj^{j^i}$. $F(n,0)=n!$ is just the standard factorial, whereas $F(n,1)$ is the so-called hyperfactorial.
Is there a term for $F(n,i)$?
How fast do these grow?
Is the ...

**10**

votes

**1**answer

211 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 ?

**2**

votes

**1**answer

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

**9**

votes

**0**answers

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

**6**

votes

**1**answer

203 views

### Algorithm for Low Discrepancy Sequence of Hamilton Cycles in Complete Graphs

Are there deterministic algorithms that generate a sequence of Hamilton Tours that is superior to a sequence of randomly chosen tours, when applied to the TSP (by applying to the TSP, I understand ...

**2**

votes

**1**answer

240 views

### upper bound on derivatives of a function defined on an arc

This is a simple question I asked in math.SE last month but unfortunately no one gives any comment. So I decided to try some luck here.
You can skip examples below and read from "General setting" at ...

**4**

votes

**0**answers

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

**8**

votes

**2**answers

4k views

### Generalization of a horse-racing puzzle

A well-known puzzle goes:
"Suppose that you have 25 horses and a racetrack on which you can race up to 5 horses. If the outcome of each race only tells you the relative speeds of the horses in the ...