## New answers tagged co.combinatorics

1
vote

### Some ideas about parking functions and integer partitions

(1). Can we study the enumeration of separated parking functions with type $\lambda$? And how?
...

1
vote

### reference for a formula of the Motzkin triangle on OEIS

I contacted Barry and Kruchinin, and they kindly provide some information that is very helpful to me. According to their reply, the result can be deduced from the Lagrange inversion formula, by ...

6
votes

Accepted

### Euro2024-inspired scoring problem

Q1: No. We can see this by attempting to construct $s$. Without loss of generality we can assume $s$ is strictly increasing.
We must have $s(0)=0$ and $s(1)=1$, otherwise no game has attractivity $1$. ...

0
votes

### Shortest polygonal chain with $6$ edges visiting all the vertices of a cube

My solution for the above-stated problem is provided by the $6$-link polygonal chain $(0,0,1)-(0,0,0)-\big(1+\frac{x+2+\sqrt{2}}{2\cdot\sqrt{2}\cdot(x+\sqrt{2})},1+\frac{x+2+\sqrt{2}}{2\cdot\sqrt{2}\...

5
votes

Accepted

### Is every connected edge-swapping graph edge-transitive?

No - consider the vertex-and-edge graph of a truncated cube. Some but not all edges are part of 3-cycles, so this graph is not edge-transitive, but it is clearly edge-swapping.

2
votes

Accepted

### The number of small sum-free subsets of $[n]$

Note: I'm working mod $n$ here, which is directly transferable to the integers for the lower bound, and for the upper bound it's only a multiplicative error of a constant which doesn't affect the ...

2
votes

### Open questions about posets

A finite, non-empty poset $P$ has dimension $k\in\mathbb N_0$ if $k$ is the smallest number of chains (totally ordered sets) into a product of which one can order-embed $P$.
$S_3$ is the standard ...

Community wiki

45
votes

### How decreasing can a bijection $f:\mathbb{N}\to\mathbb{N}$ be?

This problem arises in Section 4.3 of my PhD thesis in connection with a Ramsey-type result for infinite tournaments. The answer of $3/4$ is also confirmed by Theorem 4.5 in that section, and the ...

8
votes

Accepted

### *Friendly* coloring of a digraph

Carsten Thomassen (1983) proved that a digraph with minimal out-degree at least 3 has two vertex-disjoint cycles, call them $C_1$, $C_2$ and color black and white respectively. Then proceed as follows:...

2
votes

Accepted

### Conjecture about separating union-closed families

Checking more carefully, I have found that this answer can be used as a counterexample here as well, since $S = [21] \setminus \{18\}$.

52
votes

Accepted

### How decreasing can a bijection $f:\mathbb{N}\to\mathbb{N}$ be?

A fun problem. The answer is $3/4$.
Lower bound: We first make some relaxations to the problem.
Firstly we observe that we can relax the requirement that $f$ be bijective to $f$ being injective, ...

1
vote

### Questions on symmetric Hadamard matrices

Currently, this is an open problem. So I only got a partial answer.
We just need to consider the following two different situations:
Case 1: $n$ is not a perfect square. There is no solution if $\...

11
votes

Accepted

### Min–max reversing bijections $f:\mathbb{N}\to\mathbb{N}$

$\newcommand\N{\mathbb N}$No, it is not possible to have $\mu_{[\N]^2}\big({\operatorname{rev}(f)}\big) = 1$.
Given the function $f$, we will say that $n\in\mathbb{N}$ is good if $f(n)<f(k)$ for ...

9
votes

Accepted

### Joining the $2^k$ points of $\{0,1\}^k$ with the shortest tree

I suspect that the optimum, for a cube of side length $2$, is $2^k \sqrt{3} - 2 \sqrt{3}+2$. Note that the optimum if we use edges of the cube is $2 (2^k-1)$, so this is better by a factor of roughly $...

3
votes

Accepted

### Generate all non-isomorphic caterpillar trees with $n$ vertices

Here is a SageMath code generating caterpillar graphs on $n$ nodes based on enriching a path graph with leaves. As an example it shows all such graphs on 6 nodes.

3
votes

### Counting equal covering sets

The functions $g(s,k,n,m)$ equals the coefficient of
$M_{m^n}$ in the expansion of
$$\exp\big(\sum_{i\geq 1} \tfrac{(-1)^{i-1}}i M_{i^k}\big),$$
where $M$ denote monomial symmetric polynomials, whose ...

6
votes

Accepted

### Sparse "bijection-proof" subsets of $[\mathbb{N}]^2$

Note that $\left\{\{1,a\} \mid a \in \mathbb{N}_{>1}\right\}$ is bijection-proof and $\mu_{\left[\mathbb{N}\right]^2}\left(\left\{\{1,a\} \mid a \in \mathbb{N}_{>1}\right\}\right) = 0$.

0
votes

### Looking for q-analog of derangement anagrams for a word

Use $\textbf{Theorem 1.1}$ from [1],
The linearization coefficients of q-Laguerre polynomials are given by
$$
\mathcal{L}\left(L_{n_1}(x ; q, y) \cdots L_{n_k}(x ; q, y)\right)=\sum_{\sigma \in \...

2
votes

Accepted

### Generalizations of a theorem of Edmonds/Tutte on existence of a perfect matching in a graphs

It is highly unlikely that such a generalization would exist, because the 3-dimensional matching problem is NP-complete, while polynomial identity testing can be solved efficiently using randomized ...

3
votes

Accepted

### "Spanning trees" for connected linear hypergraphs

Counterexample. Let $\mathbb N=\{1,2,3,\dots\}$. For $n\in\mathbb N$ let $[n]=\{1,2,\dots,n\}$. Let $V=\mathbb N\times\mathbb N$. For $n\in\mathbb N$ let $e_n=\{n\}\times\mathbb N$ and $f_n=[n]\times\{...

6
votes

Accepted

### Is a weak version of the three sets Lemma provable in ZF?

The answer is indeed no. Consider a Russell sequence $A_i,i\in\mathbb N$, that is a collection of disjoint two-element sets such that no infinite subfamily of them has a choice function. It is ...

4
votes

Accepted

### Asymptotics on sum of product of binomial coefficients

Such sums may be approximated by using the local central limit theorem.
Note that ${a-k\choose k}p^k(1-p)^{a-2k}$ and ${b\choose k}q^k(1-q)^{b-k}$, where $p,q\in [0,1]$ are binomial probabilities. In ...

10
votes

Accepted

### Szemerédi-Trotter theorem for planes and lines

The very same bound holds. This is because if you intersect your configuration with a generic plane, then you get a point-line configuration with the same incidences. On the other hand, of course, any ...

10
votes

Accepted

### Bijection $\varphi:\mathbb{N}\to\mathbb{N}$ that distorts every finite arithmetic progression

$\newcommand{\N}{\mathbf{N}}$Define, say, $Q=\{2^{2^n}:n\ge 4\}$.
Let $f$ be the permutation of $\N$ exchanging $Q$ and its complement, and increasing on both. I claim that $f$ maps no finite ...

20
votes

### Bijection $\varphi:\mathbb{N}\to\mathbb{N}$ that distorts every finite arithmetic progression

It exists for rather trivial reasons. Define this map inductively. In the even steps, send the smallest element of the domain, which does not yet have an image to the smallest element of the range, ...

6
votes

Accepted

### Shrinking and expanding pairs in bijections $\varphi:\mathbb{N}\to\mathbb{N}$

One has $\max\big\{\mu\big(\exp(\varphi)\big) :\varphi \in S_{\mathbb{N}}\big\}=1$, as mentioned by Emil Jeřábek in the comments.
We can also create a function $\varphi$ with $\mu\big(\text{shr}(\...

5
votes

Accepted

### Is there always a permuted tuple of $n+1$ elements such that multiplying elementwise$\bmod n + 1$ on $(0, 1, \ldots, n)$ yields a binary $n+1$ tuple?

Such a permutation exists if and only if $k$ is $1$, $6$, $8$, $p$, or $p^2$ for some prime $p$, and if so, one such permutation has a simple explicit description.
The cases $k=1,6,8$ are easy. If $k=...

2
votes

Accepted

### Minimum area of the symmetric difference of odd number of translated copies of a unit circle $C$

This seems to be an open problem:
Rom Pinchasi, On the odd area of the unit disc, Israel Journal of Mathematics 256, 619-637.
https://doi.org/10.1007/s11856-023-2518-4
Amir Carmel and Rom Pinchasi,
...

5
votes

Accepted

### Sign of the permutation when I show that $\star{\star w}= (-1)^{n(n-k)} w$ for the Hodge operator

$\newcommand\dvol{d{\operatorname{vol}}}$If $I \subset \{1, \dotsc, n\}$, write $I^c$ for the complement. Then ${\star dx_I} = \pm dx_{I^c}$, where the sign is such that $dx_I \wedge {\star dx_I} = \...

7
votes

### Is there always a permuted tuple of $n+1$ elements such that multiplying elementwise$\bmod n + 1$ on $(0, 1, \ldots, n)$ yields a binary $n+1$ tuple?

No. For $n=14$ it's not possible. There are at most $\phi(15)=8$ ones modulo $15$ in the product, and thus a least $15-8=7$ zeros. However, each zero must result from the product of numbers at least ...

0
votes

### Ask for a generating function or an explicit expression of a triangle of positive integers

Motivated by the formula
$$
C_{n,k}=\sum_{j=0}^{k}\frac{(-1)^j}{2j+1}\binom{n}{k-j},\quad 0\le k\le n-1,
$$
we considered the function
$$
q_k(z)=\sum_{j=0}^{k}\frac{(-1)^j}{2j+1}\binom{z+1}{k-j}
$$
...

1
vote

Accepted

### Efficient counting of integer solutions to linear system

I've discussed this problem privately with Winfried Bruns (the author of Normaliz), and what follows is the courtesy of Winfried:
The inequalities define a rational polyhedron $P$. It is unbounded. ...

Community wiki

7
votes

Accepted

### Asymptotic size of largest subset in $\mathbb F_p^2$ defining only lines of different slopes

Surely, we have $|S|\leq O(\sqrt p)$, as the number of slopes cannot exceed $p+1$. This estimate is sharp, up to a multiplicative constant.
Indeed, let $A$ be a Sidon set in $\mathbb F_p$, that is --- ...

5
votes

### What is the max number of self-segregating words of length n?

Here is a solution for $n=3$.
1. We claim that maximum cardinality of $S$ is $(N-1)N(N+1)/3$. Notice that this is achieved by the set of all words of the form $a_ia_ja_k$ with $i\geq j<k$: this set ...

0
votes

### A variant of set cover problem reformulated

Regarding your second question. There is a (1/2)-approximation algorithm for your problem.
In detail, the input consists of k collections of subsets of a given universe. The goal is to select exactly ...

3
votes

### On cutting tetrahedrons into mutually congruent pieces

This MSE question exhibits two non-regular tetrahedra which can be decomposed into 8 smaller copies congruent to themselves; this yields $8^n$ for any $n$.

8
votes

### Does anyone remember what happened to the experimental search for polynomial identities for $\pi$?

4 sources with state-of-art information about this topic on some recent Polynomial identities for $\pi^c$ are:
1.- "Rational Hypergeometric Ramanujan Identities for $1/π^c$: Survey and ...

4
votes

### Does anyone remember what happened to the experimental search for polynomial identities for $\pi$?

To follow up on my comment, the specific experimental search for polynomial identities that relate powers of $\pi$ and values of the Riemann zeta function, is in Experimental Evaluation of Euler Sums ...

6
votes

Accepted

### Does anyone remember what happened to the experimental search for polynomial identities for $\pi$?

I'm not aware of a perfect match to your description, but here are a few possibilities. Even if they are near-misses, perhaps they will help you with your search.
Jesús Guillera's webpage has a list ...

7
votes

Accepted

### What is known/expected on the co-growth series of the braid group?

I don’t know much about the exponential generating series, so I’ll just address Question 1.
For the braid group on $n=3$ strand, the cogrowth series is $D$-finite by results of Alex Bishop for any ...

9
votes

Accepted

### Has Plummer's open problem on the cyclic connectivity of planar graphs been solved?

Yes, it has been solved.
In 1989 Borodin proved that the maximum cyclic edge connectivity of a 5-connected planar graph is at most 11, improving on Plummer's upper bound of 13. The 11 bound is tight [...

2
votes

Accepted

### Preserving simple-connectedness under intersection complexes

Yes.
There is a map $X\to X_U$, taking each point $x$ to some point in the simplex corresponding to the set of all $i$ such that $x\in U_i$.
This map induces a surjection $\pi_1(X)\to \pi_1(X_U)$. To ...

6
votes

Accepted

### Closed form for the A110501 (unsigned Genocchi numbers (of first kind) of even index)

This is a known result. To quote from Richard Stanley's Enumerative Combinatorics, Volume 2, second edition, solution to problem 8(e) of Chapter 5, page 115: This is equivalent to a conjecture of J. M....

2
votes

Accepted

### Prove ${^{b}a} \equiv {^{b+1}} a \pmod {10^{\lfloor{\log_{10} (^{b}a) }\rfloor + 1}} \Rightarrow a=5$ as $a$ and $b$ are two integers greater than $1$

Extending your definition of ${^{b}}a$ to have it be just $a$ for $b = 1$, so ${^{b}}a$ is $a^{({^{b-1}}a)}$ for $b \ge 2$, then your equivalence relation becomes
$$a^{({^{b-1}}a)} \equiv a^{({^{b}}a)}...

Top 50 recent answers are included

#### Related Tags

co.combinatorics × 10855graph-theory × 2272

nt.number-theory × 1261

reference-request × 1047

pr.probability × 786

discrete-geometry × 603

rt.representation-theory × 514

linear-algebra × 502

gr.group-theory × 458

sequences-and-series × 403

enumerative-combinatorics × 386

permutations × 345

graph-colorings × 340

algorithms × 329

additive-combinatorics × 319

polynomials × 294

partitions × 289

ag.algebraic-geometry × 287

binomial-coefficients × 257

matrices × 248

mg.metric-geometry × 242

convex-polytopes × 237

computational-complexity × 225

generating-functions × 211

finite-groups × 184