co.combinatorics – Optimization problem on sums of differences between real numbers with combinatorial constraints

We are given a sequence $S_n$ of $n$ points on a straight line $L$, whose coordinates are denoted by $x_1, x_2, ldots, x_n$ in non-decreasing order (i.e., the corresponding non-decreasing ordered sequence of Euclidean distances between each point of $S_n$ and an arbitrarily chosen point of $L$). Let $D$ be equal to $max_{i,jin (n)} |x_i-x_j|$.

We denote by $tau$ a threshold point on $L$ maximizing the following sum $R(tau)$:

$$R(tau):=left(sum_{substack{1le i<j<kle n: \ x_i,x_j<tau,~~x_k>tau}}
D-(x_j-x_i)right)+
left(sum_{substack{1le i<j<kle n: \ x_i<tau,~~x_j,x_k>tau}}
D-(x_k-x_j)right)~.
$$

Given three distinct points with indices $i, j$ and $k$, we define

$$R(i,j,k):={sum_{1le i<j<kle n}
max{D-(x_j-x_i),D-(x_k-x_j)}}~,$$

and

$$R'(tau):=left(sum_{substack{1le i<j<kle n: \ x_i,x_j<tau,~~x_kgetau}}
R(i,j,k)right)+
left(sum_{substack{1le i<j<kle n: \ x_i<tau,~~x_j,x_kgetau}}
R(i,j,k)right)~.
$$


Question: What is the minimum value for the ratio $frac{R(tau)}{R'(tau)}$ over all possible sequences $S_n$, asymptotically for $ntoinfty$?

co.combinatorics – Is this model of converting integers to Gray code correct?

The model shown in the figure converts all numbers that have k digits in the binary system to Gray code without any calculation, but I have no proof that guarantees this claim.

enter image description here

Here is some information on how to use it.

Conversion model of all integers that have k digits in the binary system in Gray code.

Rules

  1. You will need k columns of numbers. The numbers to be encoded are arranged in the last column.

  2. The conversion is done gradually by transferring groups of numbers to the adjacent columns in the way the arrows show. There are two types of paired arrows, parallel (=) and intersecting (×). Symbolically, the (=) and (×) are considered inverse of each other.

  3. Each column with arrows is formed by an exact copy of the previous column and by a copy of the previous column that has inverted pairs of arrows, which is placed below the exact copy.

Observation

If we set “=” = 0 and “×” = 1, then the successive columns containing arrows form the Thue Morse sequence which essentially forms the rules for converting integers to Gray code.

co.combinatorics – Combinatorics of multivariate faa di bruno formula

This question is a followup on this one on stackoverflow where i implement in python this issue. I am applying the faa di bruno formula to obtain the $mathbf{i}$th derivatives of the function $f = ln circ g$ in terms of the derivatives of $g$, a function with $n$ variables. This yield the following formula, denoting by $f^{(mathbf i)}$ the $mathbf i$th derivative of a function f

$$f^{(mathbf i)}(t) = sumlimits_{pi in Pi(mathbf{i})} (lvert pi rvert -1) (-1)^{lvert pi rvert -1} g(t)^{- lvert pi rvert} prodlimits_{B in pi} g^{(mathbf{i}(B))}$$

where the notation follows this section of the wikipedia page, plus a small variation that recover the multiindex $mathbf i(B)$ from the set of dimension indexes $B$.

The problem is that, since the exponential function has all it’s derivatives equal, as soon as we want to derivate twice on the same variable, i obtain several $pi$ inside $Pi(mathbf i)$ that are equivalent.

For exemple, set $mathbf i = (2,0,0)$ in a three-dimensional problem. Then, the partitions inside $Pi(mathbf i)$ are:

  • $(0,0,1)$
  • $(1), (0,0)$
  • $(0), (0,1)$
  • $(0, 1), (0)$
  • $(0) (0) (1)$

There is here a partition that appears twice (without taking into account the order of blocks inside a partition), and which will have the same value into the sum.

This happends a lot (run my code from stackoverflow to find out). Is there a way i could ‘factorise’ the formula ?

Edit: For $n = 1$, in a one-dimensional problem, the formula indeed factorises to the Bell polynomials, and the number of occurences of similar partitions are the Bell numbers. Is there somewhere a multivariate equivalent ?

co.combinatorics – Given point A on a 2D coordinate plane and 1-19 other secret points, can you find some secret point S given also a distance range between every point?

I am… not math oriented, dropped out of High School Geometry, and this is a random problem I ran into while working on a project.

I dabble in crypto for cryptocurrency related work, so I’m familiar with very basic graph theory, DAGs and the like, and I guess algebra.

I hope I’m wording my question appropriately. Let me try and add some context and put the problem into laymen terms in case I very terrible misworded my title.

  • There is a 10v10 player video game. On each team, there is a designated captain.
  • Each side only has access to the x, y position of their own captain. This is the only exact data we have.
  • Players don’t even know their own x, y on the map.
  • Each player knows the distance (within a 5 or 10 unit range, ie. 5 – 15 units away) to another player from their location, if under 40 units.
  • The map is a few thousand units by a few thousand units. Lets say 3000×3000 for the example.
  • When a player gets <40 units from the enemy captain, they will know within a 5 or 10 unit range how far they are.
  • The enemy captain does not report their distance from us.
  • You know which of the 1-19 secret points is the enemy captain.
  • These limitations are on data given to plugins for automation only. The actual gameplay does not have these limitations, so don’t imagine real people running around blind in a dark room.

Assume that each team player can share their own data with each other, each player has access to the following data:

  • Their captain’s exact x, y position.
  • Their distance as a 5 or 10 unit range from every player of their team as well as the enemy captain, if under 40 units.
  • Each player’s distance from enemies as a 5 or 10 unit range (within 40 units), but not vice versa (enemies do not report to us).

Essentially, we have a maximum of 20 data points (distance ranges between every team player and every other player, enemies included). Plus we have the single x, y of the team captain.

I may be completely off here, but drawing this out, it seems like we can start at our known captain position a and draw “donuts” (min range, max range) representing potential locations of other players, removing the “donut hole” as possibilities.

If possible, I need an algorithm that will use the given data and “estimate” the position of the enemy captain.

So ideally, players would group up within 40 units to get the most information, and then once we can get a high enough “resolution” for the estimation, we’d consider it a success and report that to our team. My suspicion is that because we know our captain’s (x, y), once they get <40 yards from the enemy captain, if we have enough players nearby, we can “bruteforce” a configuration (the distances between players) to find a set of points where their distances match the ranges we have recorded from the game.

I have a couple of concerns.

  • When visualizing this it started to eerily remind me of asymmetric cryptography, more specifically, the discrete log problem to solve for the secret key. Not quite the same, but I am worried the complexity may be high or even unsolvable due to time.

  • It is essentially a starting point surrounded by many “donuts” with holes (because distance is a range and not exact units – so we draw two circles and the area between is our “donut”), and those donuts then have their own donuts to represent their distances from each other. Some configuration should give a perfect overlap on the donuts where we can estimate an “area” where our hidden point / enemy is. Do we just start rolling the dice and bruteforce the infinite possibility of x, y positions for each player, until we “match” our data set?

  • Is the answer always going to be some infinite set of points within some locus or circle because we only have a range for each player and not exact distance? Can we narrow our secret coordinate guess to within a couple units somehow? A couple dozen? hundred?

  • If solvable, is there a “magic” or “good enough” number of values I’d need to solve? Because we only know distances between players if they’re <40 units apart, our data set fluctuates wildly in real time. Is there some number of distance sets where this becomes feasible to solve?

Okay… please school me. Is this doable? How do I begin to deconstruct these circles into pseudocode and what kind of number theory helps me figure out problems similar to these? Is this possible WITHOUT at least a partial bruteforce?

co.combinatorics – A conjecture on circular permutations of n elements in an abelian group of odd order

In 2013 I formulated the following conjecture in additive combinatorics.

Conjecture. Let $G$ be an additive abelian group of odd order, and let $A$ be a subset of $G$ with $|A|=n>2$. Then, there is a circular permutation $(a_1,ldots,a_n)$ of all the elements of $A$ such that all the adjacent sums $ a_1+a_2,ldots,a_{n-1}+a_n,a_n+a_1$
are pairwise distinct.

Recently, Mr. Yu-Xuan Ji, a student at Nanjing Univ., verified this conjecture for $|G|<30$.

I’m even unable to show the conjecture for $G=mathbb Z/pmathbb Z$ with $p$ an odd prime.

Any ideas towards the solution of this conjecture? Your comments are welcome!

co.combinatorics – An inequality related to the numbers of faces of polytopes with d+2 facets

I would like to prove an inequality related to the number of $k$-faces of two $d$-polytopes with $d+2$ facets; see (1) below.

Let $r>0$, $s>0$, $tge 0$, and $dge 2$ be such that $d=r+s+t$. We denote by $Delta({r,s})$ the sum of an $r$-dimensional simplex and an $s$-dimensional simplex with $r,s>0$, lying in complementary subspaces. The polytope $Delta(r,s)$ is a simple polytope of dimension $r+s$. A $d$-dimensional $P$ polytope with $d+2$ facets is a $t$-fold pyramid over $Delta({r,s})$. The number $f_k$ of its $k$-dimensional faces is as follows.

$$f_k(P)= binom{r+s+t+2}{k+2} -binom{s+t+1}{k+2}-binom{r+t+1}{k+2} +binom{t+1}{k+2}.$$

I am interested in finding the $d$-polytopes with $d+2$ facets, $2d+1$ vertices, and a smallest number of faces. Having $2d+1$ vertices amounts to saying that $d=rs$.

Let $r_{2}>r_{1}>0$ and $s_{1}>s_{2}>0$ be such that $r_{i}le s_{i}$ for $i=1,2$. And let $t_{1},t_{2}ge 0$ and $dge 2$ be such that $d=r_{i}+s_{i}+t_{i}$ and $d=r_{i}s_{i}$ for $i=1,2$. Suppose that $P_{i}$ be a $t_{i}$-fold pyramid over $Delta({r_{i},s_{i}})$. Experimentation has shown that

begin{equation}
(1)quad f_{k}(P_{1})< f_{k}(P_{2})quad text{for each $kin (2,d-2).$}
end{equation}

Is (1) known? I have tried unsuccessfully to prove (1) for every possible triple $(r,s,t)$.

Any help would be greatly appreciated.

Thank you, and regards,
Guillermo

co.combinatorics – Vertices of a particular transportation polytope

Let $X$ be a $ntimes n$ matrix ($ngeq 3$) such that $x_{ii}=0$ for every $i$, $x_{ij}geq 0$ for every $(i,j)$, and the sum of the $i$-th row equals to the sum of the $i$-th column for every $i$ (call the sum $a_i$).

WLOG let’s assume $a_1leq a_2leqcdotsleq a_n$. Let $P$ be the set containing all such $X$, then $P$ is a polyhedra. Moreover, $Pneq emptyset$ if and only if $a_nleqsum_{k=1}^{n-1} a_k$. The ‘only if’ part is easy, and the ‘if’ part can be done by explicit construction.

My question is: what are the vertices of $P$, or at least can we found a set of points that contains all vertices of $P$ (for example, writting $P$ as the sum of some polyhedron)?

co.combinatorics – Inependent sets in Complement of Kneser Graphs

Intuition strongly suggests that there exist $frac{binom{n}{k}}{lfloorfrac{n}{k}rfloor}$ indpendent sets in the complement of a kneser graph each having $lfloorfrac{n}{k}rfloor$ vertices in it. Is this true. If true how do establish it.

A construction of such a set of cliques in the kneser graph $K(6,2)$ is as follows:
$$(12)(34)(56)$$
$$(13)(25)(46)$$
$$(14)(26)(35)$$
$$(15)(24)(36)$$
$$(16)(23)(45)$$
Thus, in this example we have $5$ triangles in the kneser graph $K(6,2)$ which correspond to an equitable $5$ coloring of the complement graph $overline{K}(6,2)$. Can such a construction be always done? I think this is related to the number of order $2$ elements in the symmetric group of order $n$. Thanks beforehand.

co.combinatorics – finding n-th combination in an ordered statistics

7 digit numbers are formed by using the digits 1, 2, 3, 4, 5, 6, 7. We are allowed to use every digit only once, and the number shouldn’t be divisible by 5. If we sort all the combinations in ascending order, what will be the 2000-th number in the list?

Also, is there a generalised way to approach n-th combination in ordered statistics problems like this?

co.combinatorics – The average size of downward closed family of the subsets of $[n]$ is at most $n/2$?

I learned that the average size in any ideal of subsets of $(n)$ is at most $n/2$, but I think the downward closed family of the subsets of $(n)$ also satisfied. I want to know how to proof it or it is wrong. A downward closed family $mathcal{F}$ means for any $A in mathcal{F}, B subseteq A$, we have $B in mathcal{F}$, and the ideal’s definition is here https://en.wikipedia.org/wiki/Ideal_(set_theory).