1/2

I want to find a particular sequence of permutations. The requirements are:

* you start with the identity
* each permutation differs from the next by a permutation with only adjacent transpositions
* each number appears in every position at least once.

For example, for $n = 4$, here's an example:

1234,2143,2413,4231,4321,3412

What's the shortest such sequence as a function of $n$?

I have one algorithm that produces such a sequence that is length $2n +2$ for even $n$, and $2n-1$ for odd $n$. The attached photo should make the algorithm clear. But I don't have a good proof that this is optimal.

This is related to some #crochet I'm working on, surprisingly enough.

"How Anime Fans Stumbled upon a Mathematical Proof: When a fan of a cult anime series wanted to watch its episodes in every possible order, they asked a question that had perplexed combinatorial mathematicians for years."

#math #combinatorics #anime #4chan #compsci #computerscience

https://www.scientificamerican.com/article/the-surprisingly-difficult-mathematical-proof-that-anime-fans-helped-solve/

A question for the (combinatorial) hive mind.

There are a lot of extremal results that are matched asymptotically by some probabilistic construction, but with some gap, often quite substantial. I'm thinking about the Ramsey numbers R(k,k) or R(3,k), but examples of this phenomenon are prevalent.

I'm curious, does someone out there know of good examples of (extremal) results where some probabilistic construction (e.g. via a random graph) is matched asymptotically, and very precisely?

A post of @11011110 has reminded me that (after a year and a half lurking here) it's never too late for me to toot and pin an intro here.

I am a Canadian mathematician in the Netherlands, and I have been based at the University of Amsterdam since 2022. I also have some rich and longstanding ties to the UK, France, and Japan.

My interests are somewhere in the nexus of Combinatorics, Probability, and Algorithms. Specifically, I like graph colouring, random graphs, and probabilistic/extremal combinatorics. I have an appreciation for randomised algorithms, graph structure theory, and discrete geometry.

Around 2020, I began taking a more active role in the community, especially in efforts towards improved fairness and openness in science. I am proud to be part of a team that founded the journal, Innovations in Graph Theory (https://igt.centre-mersenne.org/), that launched in 2023. (That is probably the main reason I joined mathstodon!) I have also been a coordinator since 2020 of the informal research network, A Sparse (Graphs) Coalition (https://sparse-graphs.mimuw.edu.pl/), devoted to online collaborative workshops. In 2024, I helped spearhead the MathOA Diamond Open Access Stimulus Fund (https://www.mathoa.org/diamond-open-access-stimulus-fund/).

Until now, my posts have mostly been about scientific publishing and combinatorics.

#introduction
#openscience
#diamondopenaccess
#scientificpublishing
#openaccess
#RemoteConferences
#combinatorics
#graphtheory
#ExtremalCombinatorics
#probability

Does anyone know an algorithm for counting perfect matchings on complete k-partite graphs? Are there any results on estimating this number for large graphs? #combinatorics

New account, new introduction!

I'm Beth. I'm a queer mathematician who loves musical theater, webcomics, teaching math, and my cat.

Favorite areas of math: Topology, geometry, and combinatorics.

Favorite musicals: Chess, Into the Woods, Next to Normal, Sunday in the Park With George, Sweeney Todd

Favorite webcomics: this is long enough to get its own post:
https://transfem.social/notes/9ius8efgn12cewcz

#Introduction #Queer #Mathematician #Math #Musicals #MusicalTheater #MusicalTheatre #Webcomics #Teaching #TeachingMath #Cat #Cats #SillyGoose #Topology #Geometry #Combinatorics #Chess #ChessTheMusical #IntoTheWoods #NextToNormal #SundayInTheParkWithGeorge #SweeneyTodd #PandorasTaleWiki

Sigh. Will be revisiting combinatorics and the general mathematics of links.

This is because at my work I have resurrected an SQL technique for a link data spider from about twenty years ago.

Having got it to work again it's probably wise for me to be clear about methods for predicting how it will cope with scale as I gradually increase the number of rows I seed into it.
#SQL #combinatorics

A numerical evaluation of the Finite Monkeys Theorem

"From this, we can see that all but the most trivial of phrases will, in fact, almost certainly never be produced during the lifespan of our universe. There are many orders of magnitude difference between the expected numbers of keys to be randomly pressed before Shakespeare's works are reproduced and the number of keystrokes until the universe collapses into thermodynamic equilibrium..."

Woodcock, S. and Falletta, J. (2024) 'A numerical evaluation of the Finite Monkeys Theorem,' Franklin Open, p. 100171. https://doi.org/10.1016/j.fraope.2024.100171.

I've found a citation of my own work on Wikipedia for the first time!

https://en.wikipedia.org/wiki/Commutative_magma

Naturally, I read this page before I wrote my rock-paper-scissors paper. It's neat to see that my own work is now the citation for something that was unsourced "original research" on Wikipedia.

456 ways to subdivide a 4 x 2 rectangle (merging 1 x 1 sub-regions) Code at: https://github.com/villares/sketch-a-day/tree/main/2024/sketch_2024_10_09
More sketch-a-day: https://abav.lugaralgum.com/sketch-a-day
I really need your support to keep going, if you can, donate any amount at: https://www.paypal.com/donate/?hosted_button_id=5B4MZ78C9J724 #math #maths #combinatorics #Processing #Python #py5 #CreativeCoding

1434 ways of subdividing a square merging areas from a grid of 9 sub-squares. Code at: https://github.com/villares/sketch-a-day/tree/main/2024/sketch_2024_10_08
More sketch-a-day: https://abav.lugaralgum.com/sketch-a-day
I really need your support to keep going, if you can, donate any amount at: https://www.paypal.com/donate/?hosted_button_id=5B4MZ78C9J724
#shapely #ProgramaçãoCriativa #math #maths #combinatorics #Processing #Python #py5 #CreativeCoding

My fourteenth Math Research Livestream is now available on YouTube:

https://www.youtube.com/watch?v=pVoFfZAyXzk

I talked about some topics related to my recent preprint (https://arxiv.org/abs/2409.12923) about topological lattices.

I decided to skip streaming today because I wanted to talk about polyhedral products, but I haven't found the old calculation that I wanted to talk about yet. Shocking I couldn't find something I did like six years ago in the ten minutes before I would start streaming. I'll look for it now, so hopefully I'll be ready next week.

#Mathober #Mathober2024

The prompt for day 5 was 'Integer Partitions'. In number theory, a partition is a way to write an integer as a sum of positive integers. For example, there are 5 partitions of 4, given by 1+1+1+1, 2+1+1, 2+2, 3+1 and 4. The partition function is the name given to the function that counts how many partitions a given integer has. So the above examples show that p(4)=5. The first few values of the partition function are 1, 1, 2, 3, 5, 7, 11, ....

In 1937, Hans Rademacher found a complicated formula for the partition function in the form of an infinite series. You can see the full formula here https://en.wikipedia.org/wiki/Partition_function_(number_theory)#Approximation_formulas. One interesting feature of this formula is that it allows you to calculate a value of p(x) even when x is not an integer. This was explored and graphed a bit by Fredrik Johansson over at https://mathoverflow.net/questions/366733/does-rademachers-convergent-series-for-pn-define-an-analytic-function/366805#366805. He points out that when x is n+1/2 for natural n, the infinite series is zero for every term except the first. This then gives you a closed form expression, which he doesn't actually write out because it's awful:

p(x) = (√(2/3)cosh(π√(2/3)√(x-1/24)) - sinh(π√(2/3)√(x-1/24))/(π√(x-1/24)))/(2√2(x-1/24))

It's interesting that p(n+1/2) has this closed form formula, because no such formula is known for p(n) itself.

Of course it would be quite irresponsible to say 'There are 0.8458... ways to write 1/2 as the sum of natural numbers', so I won't.

I find it strange to fathom how a casual, summery dinner chat with colleagues has led, after several years (and much coordinated effort!), to this:

https://igt.centre-mersenne.org/item/10.5802/igt.0.pdf

The first papers of our new journal, Innovations in Graph Theory (https://igt.centre-mersenne.org/), went up today!

poster: https://staff.fnwi.uva.nl/j.r.kang/posterIGT.pdf

This illustration of a 38-sided space-filling polyhedron is great! https://wolfr.am/Engel-38

This is the largest number of sides known for any convex space-filing polyhedron. The theoretical upper bound is 92, given by https://arxiv.org/abs/0708.2114

To determine the number of possible labeled graphs for a fixed number of vertices n:

- For each possible edge, decide whether to include it or not.
- This results in a binary choice for each edge.
- The number of possible edges is the number of combinations of 2 vertices.
- The number of combinations of 2 vertices among n is n(n−1)/2​.
- The number of possible graphs is 2^(n(n−1)/2)​.
- For 5 vertices, this number is 2^10=1024.
illustration done with #python

#math
#graph
#combinatorics
#gif

Freudian slip of a typo I just made: "addictive combinatorics"

As a mathematician who studied combinatorics, and now a software developer, my kryptonite is off-by-one errors. Also called fencepost errors. They are just deadly to me and I make them all the time.

We had some very severe storms this week, and so it was fitting that this was the major damage we sustained.