# Tag Info

11

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-935. The existence result of that paper is actually a special case of the earlier, even up to the basic proof approach (via Tarski's fixed point theorem). ...

11

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 maximum cardinality of a $q-$ary code with length $n$ and minimum distance $d.$ You can never have more than 2 codewords at full distance by binary geometry. In ...

11

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 $\sum (a_i-x b_i)$ for a given $x$ is the one defined by the $M$ lines from this arrangement that have the highest crossings with a vertical line through $x$. (...

9

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 that edge is $\log \tfrac{p_i + p_j}{2 \sqrt{p_i p_j}}$. We want the longest path from $1$ to $n$. There are a number of standard efficient algorithms for ...

9

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 the $p^3$ general position planes, with $p^2$ planes through each point. There are no 3 collinear points if the surface is chosen appropriately, so for any 3 ...

8

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,b)\in\{(0,0),(1,1),(1,0),(0,1)\}$. Our first task will be to eliminate any $(1,0)$ or $(0,1)$ options. For that, use the Hadamard matrix without the ...

8

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 up to the eigenvalues of $B=J+xA_G$. Note that the spectrum of $J$ is $\{0^{n-1}, n^1\}$, and that the eigenvalue $n$ corresponds to the eigenvector $(1,...,1)$. ...

7

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,A_2,…,A_m$ corresponds to a $m$-coloring of $G$. The graph $G$ has degree no more than $6{n\choose 2}$, so $G$ can be colored in no more than $6{n\choose 2}+1$ ...

7

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 your graph is bipartite, the problem is infeasible when the number of nodes is odd. For $n\in\{2,4,6,8\}$, the optimal objective values are $0, 4, 8, 8$, so your ...

7

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 \begin{eqnarray*} \|x\|_{a,b} & = & \|x_1a+x_2b\|_1 \\ & \ge & \|x_1a+x_2b\|_2=\sqrt{x_1^2+x_2^2}=\|x\|_2 \\ & \ge & \frac{1}{\sqrt{2}}\|x\|...

7

I have just found out a very similar theorem to the one in the question. Some work still must be done, but it seems clear that it is very closely related. https://arxiv.org/pdf/1806.08303.pdf Let $G = (V, E)$ be a simple graph. For $B$ a subset of the vertex set $V$ , we define the spread of $B$ as \mathrm{sp}(B) = \Big\{\max[\mathrm{deg}(u)]− \min[\mathrm{...

7

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 Karpinski showed that it is NP-hard to approximate TSP within a factor of $\frac{741}{740} - \epsilon$, for any $\epsilon > 0$.

6

Here is an optimal method that I think is equivalent to your greedy method. We start with a constant random variable, say $0$. Inductively, after $n$ steps we have a random element uniformly distributed on a set of $k$ elements where $k \equiv 2^n \mod p$ and $k \lt p$. At each step, we flip the coin and produce a random element in a set of size $2k \equiv ... 6 Writing up the comment: You just need to "pixelate" the line by finding all lattice boxes that it crosses: Then the answer vector$v$must connect to one of the corners of the shaded boxes. Instead of first collecting the boxes, try the following zig-zag algorithm: start from the origin and poll the up and right nearest lattice points. One of them is closer ... 6 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:$\bullet$every member of that family$\mathcal{A}$has 3 elements;$\bullet$all sets in$\mathcal{A}$are pairwise disjunct. Let$|\mathcal{A}| =a$and let$A= \...

6

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 the 5-cycle gave the worst approximation ratio). Graphs for which the Max-Cut value and the SDP relaxation coincided were called 'exact'. As Dima says, there ...

6

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(1 + 2\sqrt{2} + \sqrt{3}) = 88.9676+$ while changing the $z=+1$ vertices to $(\pm\sqrt2, 0, 1)$ and $(0,\pm\sqrt2,1)$ gives $16\bigl(\!\sqrt{8+\sqrt{8}} + \... 6 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 distinct elements from$\{1,\dots,m\}$, and a fixed triple$(i,j,k)$, the probability that$\{x_1, \dots, x_a\} \subseteq A_i \cap A_j \cap A_k$is at most$\left(\...

5

Reading between the lines of your comment about increasing the number of faces under projections, I'm guessing that you're interested in the subject known as "extension complexity." Starting with some complicated polytope like the traveling salesman polytope, one wants to know if it is the projection of a much simpler polytope in slightly higher dimension. ...

5

It is known that the number of non-crossing spanning cycles (called "simple polygonalizations") of $n$ points in the plane can be as low as $1$ (for points in convex position) and as high as $4.64^n$, and that it is never higher than $94^n$. See: On the Number of Crossing‐Free Matchings, Cycles, and Partitions. Micha Sharir and Emo Welzl. SIAM J. Comput. 36(...

5

This problem is reducible from VERTEX-COVER. A rough description: let the input graph to VERTEX-COVER be $G = (V, E)$ with $|V| = n$. Choose integer $n << t = O(n^c)$, and create a convex polygon $P$ on $1 + n + 2t$ vertices $C_0$, $C_1$, $\ldots$, $C_n$, $D_1$, $\ldots$, $D_t$, $E_1$, $\ldots$, $E_t$. Choose vertices $V_1$, $\ldots$, $V_n$ on sides $... 5 It looks like even the sharp upper estimate 1 may be obtained. We use the following Lemma. If$q_0,\dots,q_{N-1}$are non-negative real numbers such that$q_i-q_{i+1}+q_{i+2}-\dots+q_{i+2s}\geqslant 0$for all$0\leqslant i\leqslant i+2s\leqslant N-1$, then there exist non-negative numbers$p_0,\dots,p_{N}$such that$q_i=p_i+p_{i+1}$for$i=0,\dots,N-1$. ... 5 Indeed the problem is NP-complete: Fekete, Sándor P. "On simple polygonalizations with optimal area." Discrete & Computational Geometry 23, no. 1 (2000): 73-110. (Journal link.) Your problem is what Fekete calls$\text{Min-Area}$. He also proves$\text{Max-Area}$is NP-complete, and addresses higher-dimensional variations. &... 5 It is convenient to consider the vertex set of$B_h$as a partially ordered set with its natural genealogic order, with minimum element its root. Any subtree$T'$as described in your procedure (also including the empty tree) is then exactly an initial segment. (For the notation:$B_1$is the one-vertex tree, and so on) Removing$T'$from$B_h$leaves a ... 5 For$n\in\mathbb N$and$s,t\in\mathbb R$with$0\lt t\le s\le n$, let$F(n,s,t)$be the greatest integer$m$such that any family of$n$numbers$a_1,\dots,a_n\in[0,1]$with$a_1+\cdots+a_n=s$can be partitioned into$m$subfamilies, each with sum$\ge t$. Lemma 1. If$k\in\mathbb N$and$s\le k\le n$, then$F(n,s,t)\le\left\lfloor\frac k{\lceil kt/s\rceil}...

5

I will guess that the optimum occurs for $k$ isolated vertices and a complete graph on the other $n-k$ where $k=\lfloor\frac{n+1}5\rfloor.$ The same count occurs for $k$ vertices of degree $n-1$ and no other edges so the other $n-k$ have degree $k.$ Past that I have these observations: A graph $G$ and the complement $\bar G$ give the same value to the sum. ...

4

Note: The question can be rephrased as follows: Two players $A$ and $B$ play a game on a graph. $A$ cuts the graph into two connected components, and $B$ chooses one component of the resulting graph. $A$ wants to maximize and $B$ wants to minimize the edge connectivity of the result. The bounds are the question: What would $A$ or $B$ say if they were to pick ...

4

General references on polytopes are: Ziegler: Lecture on Polytopes (already mentioned by Joseph O'Rourke in a comment) Grünbaum: Convex Polytopes Thomas: Lectures in Geometric Combinatorics Bronsted: An introduction to convex polytopes Matousek: Lectures on Discrete Geometry, Chapter 5 Barvinok: A Course in Convexity, Chapter VI A interesting survey about ...

4

Short answer: with negative $b_i$'s, it's NP-hard, but otherwise it's polynomial time. If you allow negative $b_i$ then it is hard (set all the $a_i=1$, so the goal is to get the chosen subset of $b_i$'s to sum to a number close to but greater than $-1$ in order to make the denominator as small as possible — this is a subset sum problem. If the $a_i$'s and ...

4

According to graphclasses 3-Colourability of 4-regular ∩ planar is NP-hard. Check "+details" for reference.

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