19 votes
Accepted

Splitting the integers from $1$ to $2n$ into two sets with products as close as possible

Original question Is this sequence strictly increasing? No. ...
Peter Taylor's user avatar
  • 6,431
14 votes

Splitting the integers from $1$ to $2n$ into two sets with products as close as possible

Here are optimal solutions for $n \le 10$, and the two sets happen to be equicardinal even if you don't enforce that: \begin{matrix} n & a_n & \text{solution} \\ \hline 1 & 1 & \{2\},\{...
RobPratt's user avatar
  • 5,149
11 votes
Accepted

Stable marriage with contracts: is it known?

There is a humongous literature on "matching with contracts", starting with: Hatfield, John William, and Paul R. Milgrom. "Matching with contracts." The American Economic Review 95.4 (2005): 913-...
Michael Greinecker's user avatar
11 votes
Accepted

Spreading $n$ points in $\{0,1\}^n$ as far as possible

If I understood the question correctly, what you're asking is related to the maximum distance of binary codes with large minimum distance $d\geq s$. In coding theory, $A_q(n,d)$ is defined as the ...
kodlu's user avatar
  • 10k
11 votes

Optimization algorithm sought

It is equivalent to look for the largest positive value $x$ such that, for some $M$-subset, $\sum (a_i-x b_i)\ge 0$. Plot the $n$ lines $y = a_i - x b_i$ in the plane. The $M$-subset that maximizes $\...
David Eppstein's user avatar
11 votes
Accepted

A discrete optimization problem related to the AM-GM inequality

This was essentially answered by Nate in the comments, but here are some more details. As Nate argues, $|m_i - m_j| \leq 1$ for all distinct $i,j$. Thus, if $s=ak+r$, where $a,r \in \mathbb{N}$ and $...
Tony Huynh's user avatar
  • 31.4k
10 votes
Accepted

Menger's theorem with restrictions on where the paths can begin and end

There is no known necessary and sufficient condition like in Menger's theorem. However, there is a polynomial-time algorithm that decides if the paths exist. This is one of the main results of the ...
Tony Huynh's user avatar
  • 31.4k
10 votes
Accepted

Desargues ten point configuration $D_{10}$ in LaTeX

This example shows that $s\le 2$ and for this $s$, $c\le 3$. Note that we are lucky with the latter, because there is a configuration for which every combinatorially equivalent realization has at ...
Alex Ravsky's user avatar
  • 4,027
9 votes

Optimal Talmudic Zigzag

This is a special case of finding the longest path in a directed acyclic graph. Namely, the vertices of our graph are $1$, $2$, ..., $n$, there is an edge $i \to j$ for each $i<j$ and the length of ...
David E Speyer's user avatar
9 votes

n sets, each is large, the intersection of every three is small, what is the size of the union?

It can be $O(n^{\frac32})$ for $a\ge 1$ if the sets $A_i$ correspond to the $p^2$ points of a smooth surface in an appropriate surface in a 3-dimensional space over $\mathbb F_p$ and your points are ...
domotorp's user avatar
  • 18.2k
9 votes
Accepted

Smallest relation in complement of partial order that prohibits its extension

I claim that the relation $R$ is in fact unique. The uniqueness follows from the one pair extension property of finite partially ordered sets. Proposition: Suppose that $X$ is a finite set with ...
Joseph Van Name's user avatar
9 votes

Splitting the integers from $1$ to $2n$ into two sets with products as close as possible

$\newcommand{\sub}[1]{_{\substack{m\in[1,2n] \\ #1}}}$ $\newcommand{\td}{{\widetilde d}}$ $\renewcommand{\cP}{{\mathcal P}}$ For the growth rate, we have the upper bound $a_n\le 2^nn!$ and, ...
Seva's user avatar
  • 22.8k
8 votes
Accepted

NP-hardness of finding 0-1 vector to maximize rows of {-1, +1} matrix

Here is a simple embedding of 3-SAT into the current setup (the question is just if we can get all vectors good). Call the first column special with $1$'s. Split the other variables into pairs $(a,...
fedja's user avatar
  • 59.3k
8 votes
Accepted

Eigenvalues of adjacency matrix of a k-regular graph

If $G$ is regular, then $J$ and $A_G$ are simultaneously diagonalizable (i.e. they have a common set of eigenvectors). That is, the eigenvalues of $xA_G$ and $J$ (to the same eigenvectors) just add ...
M. Winter's user avatar
  • 12.3k
8 votes
Accepted

What is the smallest size of a shape in which all fixed $n$-polyominos can fit?

It is actually $\ge cn^2$ with some $c>0$. The value of $c$ I'll obtain is pretty dismal but I tried to trade the precision for the argument simplicity everywhere I could, so it can be certainly ...
fedja's user avatar
  • 59.3k
7 votes

Partition of a graph into subgraphs with small maximum degree

Yes, every graph $G$ with maximum degree $\Delta$ can be partitioned into $k$ sets $X_1, \dots, X_k$ such that the maximum degree of $G[X_i]$ is at most $\lfloor \Delta / k \rfloor$ for all $i$. This ...
Tony Huynh's user avatar
  • 31.4k
7 votes

Exactness of the semidefinite programming (SDP) relaxation of maximum cut (Max-Cut)

This question was studied somewhat in the early '90s (before Goemans--Williamson, in fact; note that it was Delorme and Poljak who first gave a poly-time SDP algorithm for Max-Cut, conjecturing that ...
Ryan O'Donnell's user avatar
7 votes
Accepted

What is the best way to partition the $4$-subsets of $\{1,2,3,\dots,n\}$?

This problem can be reformulated in terms of graph coloring: Let the graph $G=(V,E)$, $V=\mathcal A$, $(x,y)\in E \leftrightarrow x \cap y \geq 2$ Then a partition of $\mathcal{A}$ into groups $A_1,...
LeechLattice's user avatar
  • 9,411
7 votes

Snake algorithm that minimizes straight lines

This problem is a special case of the quadratic traveling salesman problem in which the cost for traversing three consecutive nodes that have no turn is $1$ and the cost is $0$ otherwise. Because ...
RobPratt's user avatar
  • 5,149
7 votes
Accepted

On a certain norm of the identity operator on $\mathbb R^2$

Simply observe that $$\|x\|_{a,b}=\|x_1a+x_2b\|_1\,.$$ Thus, by orthogonality of $a,b$ and the easily-derived inequality $\|y\|_2\le\|y\|_1\le\sqrt{n}\|y\|_2$ for any $y\in\mathbb{R}^n$, we have \...
Jack L.'s user avatar
  • 1,423
7 votes

Metric TSP with integer edge cost

No polynomial-time algorithm exists, unless P=NP. Indeed, even for TSP instances where all distances are $1$ or $2$ (note that these automatically satisfy the triangle inequality), Engebretsen and ...
Tony Huynh's user avatar
  • 31.4k
7 votes
Accepted

Connecting $2n$ points in $\mathbb R^2$ with line segments s.t. each point belongs to exactly one line segment

You can solve this as a minimum-weight perfect matching problem in a graph with a node for each point and an edge for each pair of points. Because the distances satisfy the triangle inequality, an ...
RobPratt's user avatar
  • 5,149
6 votes

Domination problem with sets

Clearly we can assume that each element in $M$ appears in exactly $4$ subsets. Let $|M| =n$. Stage 1. Take maximal subfamily $\mathcal{A} \subseteq \{S_1,....,S_k\} =:\mathcal{S} $ such that: $\...
nonuser's user avatar
  • 237
6 votes
Accepted

Subsets of a ball/sphere with the largest sum of distances

Negative answers to some of those questions: Q1 Not always; for $n=8$ a square antiprism is better than a cube. For example, in radius $\sqrt 3$, the cube with vertices $(\pm 1, \pm1, \pm1)$ gives $16(...
Noam D. Elkies's user avatar
6 votes
Accepted

n sets, each is large, the intersection of every three is small, what is the size of the union?

Let $m$ be chosen later, and let $A_1, A_2, \dots, A_n$ be independently chosen random subsets of $\{1,2,\dots m\}$, each having size $n$. For a fixed $a+1$-tuple $(x_1, x_2, \dots, x_{a+1})$ of ...
Kevin P. Costello's user avatar
6 votes
Accepted

Graph combinatorial optimization problem

The answer is $k=n-2$. To see this, first note that $k \geq n-2$, since the complete graph on $n$ vertices minus an edge has the desired property for $k=n-3$. For the other inequality suppose that $...
Tony Huynh's user avatar
  • 31.4k
6 votes

What is the smallest size of a shape in which all fixed $n$-polyominos can fit?

It seems $S_n$ is $\geq\displaystyle\Theta\left(\frac{n^2}{\log(n)}\right)$. In the following, I will consider polyominos as subsets of $\mathbb{Z}^2$ (so, a polyomino is represented by the set of ...
Saúl RM's user avatar
  • 7,916
6 votes
Accepted

Finding an optimal covering trail for the set $\{0,1,2,3\}\times\{0,1,2,3\}\times\{0,1,2,3\}$

In order to address Q1, I have computes all intersection points and all maximal line segments between such points (including all intermediate points). There are 13,307 intersection points and 1,492 ...
Max Alekseyev's user avatar
5 votes
Accepted

Constructing graphs with independence number $\alpha (G)<k$

This is TurĂ¡n's theorem (for a complement graph).
Fedor Petrov's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible