# Tag Info

59

If you really want to know what led Neil Robertson and me to tree-width, it wasn't algorithms at all. We were trying to solve Wagner's conjecture that in any infinite set of graphs, one of them is a minor of another, and we were right at the beginning. We knew it was true if we restricted to graphs with no k-vertex path; let me explain why. We knew all such ...

41

An example that I love is the problem where, given distinct $a_1, a_2, \ldots, a_n \in \mathbb{N}$, decide if: $$\int_{-\pi}^{\pi} \cos(a_1 z) \cos(a_2 z) \ldots \cos(a_n z) \, dz \ne 0$$ This at first seems like a continuous problem to evaluate this integral, however it is easy to show that this integral is not zero iff there exists a balanced partition of ...

30

Let $f\colon \{0,1\}^n \to \{0,1\}$ be a boolean function. If it has a polynomial representation $P$ then it has a multilinear polynomial representation $Q$ of degree $\deg Q \leq \deg P$: just replace any power $x_i^k$, where $k \geq 2$, by $x_i$. So we can restrict our attention to multilinear polynomials. Claim: The polynomials $\{ \prod_{i \in S} x_i : ... 29 The answer depends on$k$,$m$, and$n$. Exact counts are generally not known, but there is a "threshold" phenomenon that for most settings of$k$,$m$,$n$, either nearly all$k$-SAT instances are satisfiable, or nearly all instances are unsatisfiable. For example, when$k=3$, it has been empirically observed that when$m < 4.27 n$, all but a$o(1)$... 29 You should check the Hajós calculus. Hajós showed that every graph with chromatic number at least$k$has a subgraph which has a "reason" for requiring$k$colors. The reason in question is a proof system for requiring$k$colors. The only axiom is$K_k$, and there are two rules of inference. See also this paper by Pitassi and Urquhart on the efficiency of ... 27 Here are a few other examples. Diaconis and Shahshahani (1981) studied how many random transpositions are required in order to generate a near uniform permutation. They proved a sharp threshold of 1/2 n log(n) +/- O(n). Generating a Random Permutation with Random Transpositions. Kassabov (2005) proved that one can build a bounded degree expander on the ... 26 Let$p$be a polynomial such that for all$x\in \{0,1\}^n$,$p(x) = \sf{OR}(x)$. Consider the symmetrization of the polynomial$p$: $$q(k) = \frac{1}{\binom{n}{k}} \sum_{x: |x| = k} p(x).$$ Note that, since the OR function is a symmetric boolean function, we have that for$k = 1, 2, \ldots, n$,$q(k) = 1$, and$q(0) = 0$. Since$q-1$is a non-zero ... 26 There are many continuous problems of the form "test whether this combinatorial input can be realized as a geometric structure" that are complete for the existential theory of the reals, a continuous analogue of NP. In particular, this implies that these problems are NP-hard rather than polynomially solvable. Examples include testing whether a given graph is ... 23 Some of you are probably aware of this, but the 17 x 17 coloring problem has been solved by Bernd Steinbach and Christian Posthoff. See Gasarch's blog post here. 23 According to the introduction of , The complexity of determining if a single polyomino tiles the plane remains open [2,3], and There is an undecidability proof for sets of 5 polyominoes .  Stefan Langerman, Andrew Winslow. A Quasilinear-Time Algorithm for Tiling the Plane Isohedrally with a Polyomino. ArXiv e-prints, 2015. arXiv:1507.02762 [cs.CG] ... 22 No such matrix exists. The Desnanot-Jacobi identity says that for$i \neq j$, $$\det M_{ij}^{ij} \det M = \det M_i^i \det M_j^j -\det M_i^j \det M_j^i$$ so using this, we get $$\det M_{12}^{12} \det M = \det M_{1}^{1} \det M_{2}^{2} - \det M_{1}^{2} \det M_{2}^{1}$$ But your requirements force the left-hand-side to be 0 (mod 2) and the right-hand-... 21 Applications of Ramsey theory to CS, Gasarch 20 No, you can not identify the sum of two permutations in polynomial time unless P=NP. Your problem is NP-complete since the decision version of your problem is equivalent to the NP-complete problem$2$-Numerical Matching with target sums: Input: Sequence of$a_1, a_2, \ldots a_n$of positive integers,$\sum_{i=1}^n a_i = n(n+1)$,$1 \le a_i \le 2n$for$1 \...

20

There are several algorithms that count the simple paths of length $k$ in $f(k)n^{k/2+O(1)}$ time, which is a whole lot better than brute force ($O(n^k)$ time). See e.g. Vassilevska and Williams, 2009.

19

The definitive article is a paper by Hlineny and Kratochvil from 2001. In it they show that the problem of recognizing a disk intersection graph (your question) is NP-hard, which suggests that it will be difficult to come up with a clean characterization. They also point out that $K_{3,3}$ cannot be represented as the intersection of disks, answering the ...

19

The question is, in my opinion, quite vague and involves some misunderstanding, so this answer attempts only to provide the right vocabulary and point you in the right direction. There are two fields of computer science that directly study such problems. Inductive inference and computational learning theory. The two fields are very closely related and the ...

19

The current fastest algorithm is actually linear in the length of the integer linear program for every fixed value of $n$. In his PhD thesis, Lokshtanov (2009) nicely summarizes the results by Lenstra (1983), Kannan (1987), and Frank & Tardos (1987) by the following theorem. Integer Linear Programming can be solved using $O(n^{2.5n+o(n)} \cdot L)$ ...

19

There is a simple construction: Take any $d$-regular non-bipartite expander $G=(V,E)$ - there are several constructions of those, e.g., Margulis, or the Zig-Zag construction. Now, turn it into a bipartite graph $G' = (V_1 \cup V_2, E')$ as follows: $V_1$ and $V_2$ are copies of $V$. Two vertices $v_1 \in V_1$ and $v_2 \in V_2$ are adjacted in $G'$ if and ...

18

An upper bound on the maximum number of stable matchings for a Stable Marriage instance is given in my Master's thesis and it is extended to the Stable Roommates problem as well.The bound is of magnitude $O(n!/2^n)$ and it can be shown that it is actually of magnitude $O\left((n!)^\frac{2}{3}\right)$. The document is thesis number 97 on page http://mpla....

18

Here are two related courses: Analytical methods in combinatorics and CS by Ehud Friedgut at University of Toronto (2009), Analytical Methods in Combinatorics and Computer-Science by Irit Dinur and Ehud Friedgut at Hebrew University (2006). Also check Ryan O'Donnell's notes for his book: Analysis of Boolean Functions by Ryan O'Donnell. and the links on ...

18

Many search problems in artificial intelligence (such as searching the game tree of a chess game, or searching for solutions to puzzles like the Rubik's cube, or more generally searching for sequences of actions to perform in order to accomplish some desired goal) are, in effect, algorithms on infinite graphs, even though the desired answer is a finite path. ...

18

It's #P-complete (Valiant, 1979) so you're unlikely to do a whole lot better than brute force, if you want the exact answer. Approximations are discussed by Roberts and Kroese (2007). B. Roberts and D. P. Kroese, "Estimating the number of $s$--$t$ paths in a graph". Journal of Graph Algorithms and Applications, 11(1):195-214, 2007. L. G. Valiant, "The ...

18

First, the name of the conjecture is "Hartmanis-Stearns", not "Hartmanis-Stearn". Second, the Hartmanis-Stearns conjecture concerns those real numbers computable by a multi-tape Turing machine in real time; in other words, the TM must compute the n'th digit in n time. Third, the result of Adamczewski et al. is only about finite automata and deterministic ...

17

This recent paper finally proves that edge contractions do not preserve the property that a set of graphs has bounded clique-width.

17

Kenneth Oksanen has published an expanded table of values up to $n=15$, based on his own computer search. Okansen also provides descriptions of the optimal comparison trees for most of the values he reports. Here's a screenshot of his table: Thanks to @MarkusBläser for the lead!

17

The answer is “yes”. The proof is by contradiction. For notational convenience, let us denote the first $n/2$ variables by $x$ and the second $n/2$ variables by $y$. Suppose that $f(x,y)$ is $\delta$-close to a function $f_1(x,y)$ which depends only on $k$ coordinates of $x$. Denote its influential coordinates by $T_1$. Similarly, suppose that $f(x,y)$ is $\... 17 Timothy Chan and Moshe Lewenstein have a paper on 3SUM and related problems in the upcoming STOC, which applies an effective version of the BSG theorem from additive combinatorics to solve variants of 3SUM faster than n^2 time. See this link to Chan's papers. 17 Interestingly, there is a nascent mathematisation of version control systems, although at this point it's only partially applicable to Git. It's called patch theory [1, 2, 3, 4, 5] and arose in the context of the DARCS version control system. It can be seen as an abstract theory of branching and merging. Recently patch theory has been given HoTT [ 6 ] and ... 16 The disjoint union of$n$copies of$K_5$(or$K_{3,3}$) is a minimal forbidden minor for the graphs of genus$n-1$; the same is true for a graph in which some of these copies share a single vertex, so that the blocks of the graph are$K_5$or$K_{3,3}\$. This follows from results in J. Battle, F. Harary, Y. Kodama and J.W.T. Youngs, "Additivity of the genus ...

16

This is really less about graph per se and more about topology. A combinatorial embedding defines a 2-manifold, a topological space in which every point has a neighborhood homeomorphic to a 2-dimensional open disk: the embedding allows a face to be defined, and we can define a topological space by choosing a disk for each face and gluing them together along ...

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