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.
...

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\},\{...

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-...

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 ...

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 $\...

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 $...

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 ...

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 ...

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 ...

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 ...

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 ...

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,
...

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,...

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 ...

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 ...

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 ...

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 ...

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,...

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 ...

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
\...

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 ...

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 ...

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:
$\...

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(...

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 ...

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 $...

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 ...

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 ...

5
votes

Accepted

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

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

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

#### Related Tags

combinatorial-optimization × 434co.combinatorics × 169

graph-theory × 121

algorithms × 61

oc.optimization-and-control × 54

computational-complexity × 40

linear-programming × 38

integer-programming × 32

linear-algebra × 30

reference-request × 29

mg.metric-geometry × 27

discrete-geometry × 26

pr.probability × 22

nonlinear-optimization × 22

convex-optimization × 21

approximation-algorithms × 19

matrices × 17

inequalities × 16

traveling-salesman-problem × 14

extremal-graph-theory × 13

np × 13

graph-colorings × 12

global-optimization × 12

heuristics × 12

computer-science × 10