Skip to main content

New answers tagged

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? ...
138 Aspen's user avatar
  • 173
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 ...
xmchenhit's user avatar
  • 135
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$. ...
Jukka Kohonen's user avatar
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}\...
Marco Ripà's user avatar
  • 1,275
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.
Noah Schweber's user avatar
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 ...
Daniel Weber's user avatar
  • 3,009
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 ...
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 ...
Alistair Benford's user avatar
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:...
Fedor Petrov's user avatar
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\}$.
Fabius Wiesner's user avatar
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, ...
Terry Tao's user avatar
  • 112k
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 $\...
user369335's user avatar
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 ...
Saúl RM's user avatar
  • 10.3k
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 $...
David E Speyer's user avatar
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.
Max Alekseyev's user avatar
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 ...
Max Alekseyev's user avatar
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$.
1001's user avatar
  • 911
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 \...
138 Aspen's user avatar
  • 173
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 ...
domotorp's user avatar
  • 18.5k
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\{...
bof's user avatar
  • 12.6k
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 ...
Wojowu's user avatar
  • 27.6k
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 ...
Fedor Petrov's user avatar
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 ...
domotorp's user avatar
  • 18.5k
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 ...
YCor's user avatar
  • 61.8k
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, ...
HenrikRüping's user avatar
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}(\...
Saúl RM's user avatar
  • 10.3k
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=...
Emil Jeřábek's user avatar
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, ...
Jan Kyncl's user avatar
  • 6,036
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} = \...
mme's user avatar
  • 9,463
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 ...
Max Alekseyev's user avatar
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} $$ ...
qifeng618's user avatar
  • 942
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. ...
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 --- ...
Ilya Bogdanov's user avatar
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 ...
Ilya Bogdanov's user avatar
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 ...
jesús garcía's user avatar
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$.
RavenclawPrefect's user avatar
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 ...
Jorge Zuniga's user avatar
  • 2,460
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 ...
Carlo Beenakker's user avatar
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 ...
Timothy Chow's user avatar
  • 79.5k
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 ...
Corentin B's user avatar
  • 1,232
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 [...
Carlo Beenakker's user avatar
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 ...
Tom Goodwillie's user avatar
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....
Ira Gessel's user avatar
  • 16.5k
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)}...
John Omielan's user avatar
  • 1,016

Top 50 recent answers are included