User zsbán ambrus - MathOverflow

Answer by Zsbán Ambrus for Can a nowhere continuous function be integrable ?

2013-04-22T08:46:34Z

Dpends on which type of integration you are asking for.

If you mean Lebesgue integral, then yes, a function can be nowhere continuous but still have a Lebesgue integral, as Henr.L points out.

If you want Riemann integral, then the answer is no. A theorem sometimes called Lebesgue's theorem states that a bounded function on the reals has a Riemann-integral if and only if the set of points where it is discontinuous has zero measure. The proof of this theorem is quite long but not technically difficult (in my opinion).

Answer by Zsbán Ambrus for Old books still used

2013-01-02T11:19:54Z

Most of the textbooks I use are quite new. The old books are the exception.

The oldest book about mathematics I use is Hajós György: Bevezetés a geometriába, a textbook on elementary geometry (in the sense of Euclid). The first edition is from 1950, I have a copy published in 1960. (Edit: it seems there's a German translation.)

I'm also using Knuth's The Art of Computer Programming, does that count as old now? The translation of the first volume is based on the second edition, of which the original was published in 1973.

Answer by Zsbán Ambrus for The shortest mathematical paper

2013-04-10T09:35:48Z

http://mathoverflow.net/questions/8846/proofs-without-words/29459#29459 claims “Conway and Soifer tried to set a record for least number of words in a mathematical paper.”

Answer by Zsbán Ambrus for Awfully sophisticated proof for simple facts

2012-03-04T13:54:46Z

The following theorem has several essentially different proofs that need quite different levels of mathematical background, ranging from high school to graduate level. Which proof is most natural depends on who you ask, but many people (including me) will find at least some proof unnecessarily complicated.

There exists a set $ A $ that is everywhere dense on the square $ [0, 1]^2 $, but such that for any real number $ x $, the intersections $ A \cap (\{x\} \times [0, 1]) $ and $ A \cap ([0, 1] \times \{x\}) $ are both finite.

(This is a variant of a homework problem posed by Sági Gábor.)

Here's the idea of a few proofs.

$ A = \{(p/r, q/r) \mid p, q, r \in \mathbb{Z} \text{ and } \gcd(p,r) = \gcd(q,r) = 1 \} $ is dense because if you subdivide the square to $ 2^n $ times $ 2^n $ squares, $ A $ contains the center of each square; and has only as many points on each horizontal or vertical line as the denominator of $ x $.
$ A = \{(x + y\sqrt3, y - x\sqrt3) \mid x, y\in\mathbb{Q} \} $ is dense because it's a scaled rotation of $ \mathbb{Q}^2 $, but has at most one point on every horizontal or vertical line otherwise $ \sqrt3 $ would be rational.
Choose $ a_0, b_0, a_1, b_1 $ as four reals linear independent over rationals, this is possible because of cardinalities. $ A = \{(ma_0 + na_1, mb_0 + nb_1) \mid m, n \in \mathbb{Q}\} $ has no two points sharing coordinates because of rational independence, and $ A $ is dense because it's a non-singular affine image of $ \mathbb{Q}^2 $.
A is the set of a countably infinite sequence of random points independent and uniform on the square. This is almost surely dense, but almost surely has no two points that share a coordinate.
Choose a countable topological base of the square, then choose a point from each of its elements inductively such that you never choose a point that shares a coordinate with any point chosen previously.
Choose a continuum (or smaller) size topological base of the square, then choose a point from each by transfinite induction such that when you choose a point, the cardinality of points chosen previously is less than continuum, thus you can avoid sharing coordinates with those points.
Choose $ a, b $ as reals such that $ a, b, 1 $ are linear independent over rationals, possible because of cardinalities. Let $ A = \{((ma + nb) \bmod 1, (ma - nb) \bmod 1) \mid m, n \in \mathbb{Z}\} $ . No two points share coordinates because of rational independence. Looking on the torus, A is dense somewhere on the square and the difference of any two points of A is in A so it must be dense in the origin. As A is closed to addition, it must be dense on a line passing through the origin. As it's also closed to rotation by $ \pi/2 $, it's also dense on the rotation of that line, thus, because it's closed to addition, dense everywhere.
Choose $ a, b $ like above. Let $ A = \{(an \bmod 1, bn \bmod 1) \mid n \in \mathbb{Z}\} $ . Prove A is dense by ergodic theory and Fourier analysis.

Update: Edited the drafts of proofs to somewhat cleaner. Permuted proofs. Also fixed typo in last proof.

Answer by Zsbán Ambrus for Visualizing polyhedra from their 1-skeletons

2013-03-28T10:11:53Z

For your question (1), there is an efficient algorithm [1] known for finding an embedding of a graph in the plane if an embedding exists.

This, however, might not be the end of the story. You may want to get an embedding where every edge is a straight line segment. It is known that such an embedding always exists if there is an embedding and there are no duplicate edges, this is called Fáry's theorem In fact, such an embedding can also be found with an efficient algorithm [2].

Your question (3) is turning a planar embedding to a polyhedron embedded in the space. This has an easy special case: namely if all faces of the planar embedding are triangles and all edges are straight segments. In this case, you can get a polyhedron embedding by slightly bending the plane so you get a sphere with a large radius, then fixing the vertexes and straightening the edges and faces. I believe but I'm not sure that this can be extended to the case when there is one or two faces that are not triangular, but there might not be such an easy method in the general case.

As for (4), if you start from a convex polyhedron, you can get a planar embedding, not necessarily with straight edges, by first projecting the vertexes and edges of the polyhedron to a sphere inside the polyhedron, then projecting that sphere to the plane.

[1] John Hopcroft, Robert Tarjan, "Efficient Planarity Testing", Journal of the Association for Computing Machinery, 21/4 (1974), 549, scanned copy at http://www.cs.princeton.edu/~dpd/Papers/SCG-09-invited/Planarity%20testing.pdf

[2] Walter Schnyder, "Embedding planar graphs on the grid", SODA '90 Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, (1990), 138-148, scanned copy at http://departamento.us.es/dma1euita/PAIX/Referencias/schnyder.pdf , ISBN:0-89871-251-3. Abstract: "We show that each plane graph of order n ≥ 3 has a straight line embedding on the n − 2 by n − 2 brid. This embedding is computable in time O(n). A nice feature of the vertex-coordinates is that they have a purely combinatorial meaning."

Answer by Zsbán Ambrus for Graphs with circulant distance matrices

2013-01-25T15:17:18Z

Any circulant graph has this property. A circulant graph is a graph that has an automorphism that's a cyclic permutation of its vertices. If you apply permute the rows and columns of the distance matrix with the same permutation, you must get the same matrix, so the distance matrix is a circulant matrix.

Graphs other than circulant graphs can't have this property, because the ones in the distance matrix determine the edges.

Answer by Zsbán Ambrus for Majority vote of total orders

2013-01-18T10:02:33Z

You say you are interested in small $ k $. This makes sense, because allowing an arbitrarily large $ k $ makes the question trivial (provided you allow repetition of a linear order with any multiplicity as well).

You can get any tournament as the majority vote of some number of linear orders.

Indeed, suppose you have $ n $ vertices (where $ 3 \le n $) and a tournament on this you want to obtain. For every arc $ (u, v) $ in the tournament, take all $ (n - 1)! $ linear orders in which $ v $ is greater than $ u $ and they are adjacent so there is no vertex between them. In these tournaments, any edge other than $ {u, v} $ occurs the same number of times in the two directions. Gather these linear orders for all edges in the tournament (that's $ n(n-1)(n-1)!/2 $ linear orders), and add any one linear order to make the total odd. The majority vote of these shall give your tournament.

Remark. I don't claim this construction to be optimal, indeed I think instead of the factorial order here, I think that you might be able to choose $ k $ to grow only polynomially in $ n $.

Update: it seems Ben Barber was a bit faster than me to post an answer that proves a bit more than this one.

Answer by Zsbán Ambrus for Proving a determinant = 0

2013-01-13T18:14:08Z

Here are two more conditions.

(D) Find $ n - 1 $ such vectors (of size $ N $ each) that $ n $ rows or columns of your matrix are linear combinations of these vectors.

This is more general than (B), because if you know (B) then you can choose all but one of those rows or columns as your vectors. However, (B) is not more general than (D) because to go from (D) to (B) you have to invert a matrix of size $ n $, where $ n $ can be as large as $ N $, which is as difficult as computing the original determinant in first place.

If $ n = N $, this condition actually says that a matrix has determinant zero if it's the product of an $ N \times (N-1) $ matrix with an $ (N-1) \times N $ matrix.

(E) The sum of the $ N! $ expansion terms of the determinant is zero.

This comes up less often than the others, but it is a way.

Let me illustrate these conditions with an example where three of the conditions can be used.

Suppose $ \mathbf{u}_1, \dots \mathbf{u}_N $ and $ \mathbf{v}_1, \dots \mathbf{v}_N $ are real vectors in $ \mathbb{R}^{N-1} $ . Let $ A $ be the $ N \times N $ matrix whose element $ a_{i,j} $ is the dot product $ \langle \mathbf{u}_i|\mathbf{v}_j\rangle $ . We want to prove that $ \det A = 0 $.

The easiest way to prove this is using the condition (D). Let's take a basis $ (\mathbf{e}_1, \dots, \mathbf{e}_{N-1}) $ of the vector space, and write the vectors in this basis as $ \mathbf{u}_i = \sum_k u_{i,k} \mathbf{e}_k $ and $ \mathbf{v}_j = \sum_k v_{j,k} \mathbf{e}_k $ . A general element of the matrix can be written as $ a_{i,j} = \langle\mathbf{u}_i|\mathbf{v}_j\rangle = \sum_k u_{i,k} v_{j,k} $ . This means that any row $ \mathbf{a}_i = (a_{i,1}, \dots, a_{i,N}) $ is a linear combination of the vectors $ \mathbf{w}_1, \dots, \mathbf{w}_{N-1} $ where $ \mathbf{w}_k = (v_{1,k}, \dots, v_{N,k}) $ , namely $ \mathbf{a}_i = u_{i,1} \mathbf{w}_1 + \dots u_{i,N-1} \mathbf{w}_{N-1} $ .

You can use condition (B) in a similar way. For this you must first find a linear dependence among the vectors $ \mathbf{u}_1, \dots, \mathbf{u}_N $ . Such a dependence must exist because these are $ N $ vectors in an $ N - 1 $ dimensional space. So suppose $ \mathbf{0} = \lambda_1 \mathbf{u}_1 + \dots + \lambda_N \mathbf{u}_N $ where not all coefficients are zero. Now $ \sum_i \lambda_i a_{i,j} = \sum_i \langle\mathbf{u}_i|\mathbf{v}_j\rangle = $ $ \bigl\langle \bigl(sum_i\mathbf{u}_i\bigr)\bigm|\mathbf{v}_j\rangle = \langle\mathbf{0}|\mathbf{v}_j\rangle = 0 $, which means the rows of the matrix are linear dependent.

There is also a way to use condition (E) to give a proof. This proof is complicated compared to the others but has a special place in my heart.

For this, again consider the coordinates of the vectors and write the elements of the matrix in the form $ a_{i,j} = \sum_k u_{i,k} v_{j,k} $ . If you now expand the determinant and completely, you find that the determinant can be written as the huge sum

$$ \det A = \sum_j \sum_k (-1)^j \prod_i u_{i,k_i} v_{j_i,k_i} $$

where $ j : (\{1\dots N\} \to \{1\dots N\}) $ goes over all permutations and $ k : (\{1\dots N\} \to \{1\dots N-1\}) $ over all sequences.

Any such vector $ k $ must have a repetition, because the range is smaller than the domain. Let thus $ k_r = k_s $ where $ r < s $ are indices, and have $ (r, s) $ be the least pair of indices where such a repetition is true (use any total ordering of pairs). Now define $ j' $ as the permutation such that $ j'(r) = j(s) $, $ j'(s) = j(r) $, but $ j' $ is equal to $ j $ in all other places. For any given $ k $, this breaks the permutations into disjoint pairs $ \{j, j'\} $ . Notice now that

$$ \prod_i u_{i,k_i} v_{j_i,k_i} = \prod_i u_{i,k_i} v_{j'_i,k_i} $$

but the signs of the permutation are opposite so $ (-1)^{j'} = -(-1)^j $. This implies the terms in that sum come in pairs that exactly cancel out each other, so indeed the determinant is zero.

Update: edited formulas in proof using (D), for I've made a mistake previously.

Answer by Zsbán Ambrus for Not especially famous, long-open problems which anyone can understand

2012-06-23T12:10:24Z

Are there eight points on the plane, no three on a line, no four on a circle, with integer pairwise distances?

The analogous question for seven points was posed by Paul Erdős and answered positively by Kreisel, Kurz 2008, who have then asked this question.

In general, problems by Paul Erdős are worth to check if you want to find problems you are asking for here.

Tobias Kreisel, Sascha Kurz, There Are Integral Heptagons, no Three Points on a Line, no Four on a Circle, Discrete & Computational Geometry 39/4 (2008), 786-790.

Answer by Zsbán Ambrus for Blackbox Theorems

2012-06-13T22:08:47Z

Jordan's curve theorem is used as a blackbox.

This topology theorem states that a looped continuous path in the plane partitions the points of the plane, such that any continuous path going from a point in one partition to a point in the other intersects the loop.

There seem to be a lot of theorems in calculus of which I don't fully understand the proof, though some of this shows my ignorance of calculus. Jordan's theorem seem to be an extreme example though. Let me list some other examples.

the existance and basic properties of the Lebesgue measure and infinite product measures
the fact that a Wiener process is almost surely everywhere continuous (mentioned below as a separate answer by weakstar)
the fact that the roots of a complex polynomial (or the eigenvalues of a complex matrix) are continuous in the coefficients (though I should learn the proof for this because the more precise statements on how well conditioned the roots are on the coefficients is useful)
the spectral theorem about linear maps on a possibly infinite-dimensional Hilbert-space
~~the proof that a convex function (from reals to reals) is always continuous everywhere and has a left and right derivative everywhere~~ (Update: okay, remove this last one because Ian Morris gave a simple proof below. I seemed to remember it was more difficult than that. Thanks, Ian.)
Rademacher's theorem: every Lipschitz function from an open subset of $ \mathbb{R}^m $ to $ \mathbb{R}^n $ is differentiable almost everywhere. (Added on Paul Siegel's suggestion. For some reason I haven't heared of this theorem before, but it sure sounds useful.)
Lebesgue's criterium which claims that a bounded function from reals to reals is Riemann-integrable iff it's continuous almost everywhere. (The proof is elementary and doesn't require any ideas, but it's laborous.)

Answer by Zsbán Ambrus for Blackbox Theorems

2012-06-13T22:21:19Z

Recognizing hamiltonian graphs is NP-complete.

(A hamiltonian graph is a graph that has a cycle passing through every node.) Everyone likes to use this theorem for proving other NP-completeness proofs, but few people would know an actual proof. Even the simplest proof is somewhat messy. The theorem that 3-colorable graphs are NP-complete is similar.

Answer by Zsbán Ambrus for Blackbox Theorems

2012-06-14T10:09:00Z

The proof for Hilbert's tenth problem, that is, that there is no algorithm to solve general Diophantiane equations.

Benjamin Steinberg has mentioned this above in a comment. I believe the proof is complicated.

Answer by Zsbán Ambrus for Maintaining a search-optimal tree

2012-06-09T23:10:19Z

A binary tree of which every subtree is search-optimal is called an AVL tree (height-balanced tree). Efficient algorithms for AVL trees are described in Knuth's The Art of Computer Programming chapter 6.2.3. In particular, you can insert a new element in $ O(\log n) $ time where $ n $ is the number of elements in the tree. Like Stanislav notes above, they are also described in Cormen–Leiserson–Rivest–Stein, Introduction to Algorithms second edition chapter 13-3.

~~For search, these and related structures are called balanced trees.~~

Update: above is wrong, see comment of Michal R. Przybylek.

Answer by Zsbán Ambrus for covering disks with smaller disks

2012-05-25T17:29:51Z

Erich Friedman's packing center claims that you can't cover with 6 disks, and that this was proved by Károly Bezdek in 1979. If you want a more exact reference, ask Erich Friedman in email.

Answer by Zsbán Ambrus for Demonstrating that rigour is important

2012-05-03T08:23:42Z

Allow me to quote part of the introduction of chapter 9 of Lovász: Combinatorial Problems and Exercises.

The chromatic number is the most famous graphical invariant; its fame being mainly due to the Four Color Conjecture, which asserts that all planar graphs are 4-colorable. This has been the most challenging problem of combinatorics for over a century and has contributed more to the development of the field than any other single problem. A computer-assisted proof of this conjecture was finally found by Appel and Haken in 1977. Although today chromatic number attracts attention for several other reasons too, many of which arise from applied mathematical fields such as operations research, attempts to find a simpler proof of the Four Color Theorem is still an important motivation of its investigation.

So here it's not so much the proof but the search for a proof that has given something extra over just believing the theorem. Does that still count as an answer to this question?

Answer by Zsbán Ambrus for Interesting and Accessible Topics in Graph Theory

2012-04-30T10:59:30Z

I believe the book

Hajnal Péter: Gráfelmélet. 1997, Polygon, Szeged.

is an extended answer to exactly this question. (There's a second edition from 2003, but apparently no translations to other languages.)

The writing style of this book makes it accessible to high school students (as opposed to the Lovász book whose concise style makes it ideal for research mathematicians). Thus, most of the material is accessible at high school level, while at the same time the book covers so many difficult topics that it'd be difficult to cover all the proofs even in a semester long high school course.

The book remains a useful reference for BSc combinatorics exams (not alone though, because some necessary topics are missing).

Here are some of the topics included (many of these were mentioned in other responses).

Flow-cut theorem and algorithm, Menger's theorems, Kőnig-Hall, maximal matching algorithm for bipartite graphs, Tutte's theorem, and even Edmond's algorithm to find maximal matching in any graph.
Euler circuits, then Dirac's sufficient condition for Hamiltonian circuit
Graph coloring, Brook's theorem (when a graph's chromatic number reaches its maximum degree), high chromatic graphs without triangle, Hajós's characterisation of graphs with chromatic number (exercise 9.16 in Lovász), Vizing's theorem on edge coloring,
Turán's theorem, Erdős-Stone theorem about the asymptotic on the number of edges of a graph not containing a particular non-bipartite graph, asymptotic for $ C_4 $-free graphs.
Ramsey theorems.
Complexity theory results about graph problems, including Karp reductions between Hamiltonian circuits and chromatic number and independence number. Does not include the Cook-Levin theorem so no problem is actually proven to be NP-complete.
Planar graphs, duality, Whitney-duals, Euler's theorem, Kuratowski's theorem on the characterization of planar graphs (yes, with a proof), Robertson and Seymour's graph minor theorem without proof, the four color theorem without proof, the five color theorem and Kempe's proof, Hadwiger's conjecture.
Perfect graphs, Lovász's theorem on the complement of perfect graphs (yes, with a proof), comparability graphs of posets are perfect.

Note finally that before any topic, you'd need to cover some of the first chapter which introduces basic terminology about graphs, which is important to plan if you are giving only a few lectures. ~~(Have you told us about the total length of lectures you are planning to give?)~~ Edit: ah, I see the lectures the question is referring to are now in the past, so there's no point to ask such a concrete question.

Answer by Zsbán Ambrus for Large bicliques in r-partite graphs containing no independent sets having one vertex from each class

2012-03-26T12:54:37Z

I believe I can prove this with a standard Ramsey-type argument, though f will grow slower than linear.

You'll need the following useful lemma.

Lemma 1 (bipartite Ramsey). For any natural numbers $ n_0, n_1, m_0, m_1 $, there exist natural numbers $ R_0, R_1 $ such that any bipartite graph with $ R_0 $ upper and $ R_1 $ lower vertices has either $ n_0 $ upper and $ n_1 $ lower vertices inducing a complete bipartite subgraph, or $ m_0 $ upper and $ m_1 $ lower vertices inducing an empty graph.

Proof of lemma goes by induction. Choose an upper vertex u. If this vertex is linked to at least $ R_1(n_0 - 1, n_1, m_0, m_1) $ lower vertices and there are enough upper vertices, then there's either a large empty induced subgraph, or a complete bipartite subgraph that's large enough if you include u. Similarly, if there are at least $ R_1(n_0, n_1, m_0 - 1, m_1) $ lower vertices u is not linked to, you've won. Thus, $$ R_1(n_0, n_1, m_0, m_1) := R_1(n_0 - 1, n_1, m_0, m_1), + R_1(n_0, n_1, m_0 - 1, m_1), $$ $$ R_0(n_0, n_1, m_0, m_1) := 1 + \max(R_0(n_0 - 1, n_1, m_0, m_1), R_0(n_0, n_1, m_0 - 1, m_1)) $$ vertices are enough. The base case when $ n_0 = 0 $ or $ m_0 = 0 $ is trivial.

Now for the theorem you are asking for, we can prove like this.

Lemma 2. For any natural numbers $ r, f $, any simple pattern graph $P$ on the $r$ vertices $ 1, \dots, r $; there is a natural number $ k $ so that any large enough $ r $-partite graph $ G $ (one that has at least $ k $ vertices in each class) always contains either

a $ K_{f, f} $ complete bipartite subgraph, or

vertices $ v_1, \dots, v_r $, one from each class respectively, such that for any $ i $ and $ j $, if $ i $ and $ j $ are linked in $ P $ then $ v_i $ is not linked to $ v_j $.

The case where $ P $ is the complete graph gives the theorem you're asking for:

Theorem. For any natural numbers $ r, f $, there is a natural number $ k $ such that any large enough $ r $-partite graph $ G $ (with at least $ k $ vertices in each class) always contains either

a $ K_{f, f} $ complete bipartite subgraph, or

vertices $ v_1, \dots, v_r $, one from each class respectively, that are pairwise unlinked.

Proof of lemma 2 goes by fixing $ r, f $, then taking induction on $ P $. The base case when $ P $ is an empty graph is trivial: $ m $ vertices in each class of the bipartite graph is enough.

Otherwise, suppose we already have the induction statement for pattern $ P' $, which is $ P $ with the edge $ {i, j} $ deleted, and we found that $ k' $ vertices per class is enough. We have a large enough graph $ G $ (with at least $ k $ vertices in each class, $ k $ is to be determined later) that does not contain a $ K_{f,f} $ complete bipartite graph as a subgraph. We want to prove that $ G $ contains $ r $ vertices unlinked according to the pattern $ P $.

Choose $ k = \max(R_0(f, f, k', k'), R_1(f, f, k', k')) $. Consider the induced subgraph of $ G $ made of only its classes $ i $ and $ j $. Both classes of this bipartite subgraph still has at least $ k $ vertices, and the subgraph still doesn't contain a $ K_{f,f} $ complete bipartite graph. Thus, you can apply lemma 1 with $ n_0 = n_1 = f $ and $ m_0 = m_1 = k' $ to find that this subgraph has an empty induced subgraph formed of $ k' $ vertices from each of the two classes. Now let $ G' $ be the induced subgraph of $ G $ that contains the $ k' $ vertices from class $ i $ and $ k' $ vertices from class $ j $ as chosen above, and all vertices from all other classes. Thus, $ G' $ has no edges between class $ i $ and $ j $. By the induction statement, we can choose vertices $ v_1, \dots, v_r $ from each class of $ G' $ such that they are unlinked accoring to pattern $ P' $, but as $ v_i $ and $ v_j $ are also unlinked, these vertices are also unlinked according to pattern $ P $. QED.

Answer by Zsbán Ambrus for Combinatoric problem with the development of intersection of union of events

2012-01-29T11:46:55Z

This event means that in the sequence of outcomes $ A_1, ..., A_r $ you don't have $ b $ adjacent falses. Suppose $ b \le t $. Let $ r-t $ be the index of the last true event in that sequence. Then $ 0 \le t < b $ you get this sequence from an $ r-t-1 $ long sequence with this property by appending t falses and a true. Thus, if you name the probability of this event a(r), you have the recurrence $$ a(r) = \sum_{0 \le t < b} p(1-p)^ta(r-t-1), $$ and the starting conditions $ a(r) = 1 $ if $ r < b $.

Fix any errors in the above argument, then try to solve the recurrence. For any fixed $ b $, this is a linear recurrence, so it has an explicit solution. With $ b $ as a parameter, it might be hard, though you could still ask for an approximation. The Concrete Mathematics book may help.

Answer by Zsbán Ambrus for Complexity of matching red and blue points in the plane.

2012-01-28T19:48:01Z

Check out the classic Cormen, Leiserson, Rivest, Stein, ''Introduction to algorithms'', second edition. In chapter 33 (Computational Geometry). See the exercises at the end of the whole chapter: exercise 33-3 is your problem. The full solution isn't described, but you will find a hint for a polynomial time algorithm. I have no idea whether that's the fastest algorithm known.

Answer by Zsbán Ambrus for Recognition of graph families.

2011-12-13T10:51:39Z

Garey, Michael R. – Johnson, David S., Computers and intractability, a guide to the theory of NP-completeness, 1979. It's a nice book which includes many problems about decision problems on graphs. It even gives a general sufficient condition that makes recognizing a class of graphs NP-complete. I don't remember the details, but I think it has to do with the class being monotonous.

Answer by Zsbán Ambrus for What is the easiest randomized algorithm to motivate to the layperson?

2011-05-09T12:22:09Z

Suppose that hundreds of undergraduates have written a test and some people in the department have to score these all with a tight deadline. There are a few tests that are tricky to score and so take more time to score, but you can't tell which ones these tests are in advance without actually scoring them. A professor has to divide the tests among all the teachers so they score them. No teacher should get too many hard to score tests, because then they can't finish even if they work all night.

There's no deterministic method to divide the tests in a fair way. On the other hand, it works fine to shuffle the tests and divide them randomly. (You must shuffle because there are many people who leave after fifteen minutes and write almost nothing are very easy to correct, and often many such tests are clustered together in the stack.)

Answer by Zsbán Ambrus for ultrapowers and higher order logic

2011-05-07T21:19:39Z

Look. Suppose you take an infinite sequence of sets $ A_0, A_1, A_2, \dots $ (with no structure apart from equality, that is, no relations or functions), such that $ A_n $ has $ n $ elements. If you take a ultraproduct of these sets (using a non-principal ultrafilter over their indices), can the product be a finite set? No, because for any natural number $ n $, all but finite of these sets have more than $ n $ elements, and ther being more than non-equal $ n $ elements is a first-order property, so this same property must be true for the ultraproduct as well, so the product has more than $ n $ elements for any natural number $ n $. So far, so good.

But now suppose you could take some kind of advanced ultraproduct of these sets that keeps not only the first order statements but all second order statements that are true in the majority of the sets. But there being only finitely many elements is a second order statement, so this advanced ultraproduct would have to be finite as well, because all the sets are finite. This is, in simple terms, why you can't have such a generalization of ultraproducts.

Answer by Zsbán Ambrus for Mathematicians who were late learners?-list

2011-05-06T17:21:05Z

How about Raymond Smullyan? According to his autobiography[1], he has published his first mathematical article at the age of 35, to which Marvin Minsky has reacted by saying Ray has decided to become a child prodigy at the age of 35. Does this count as starting off late in life?

[1] Raymond Smullyan, Emlékek, történetek, paradoxonok. TyopTeX, 2004, original title "Some Interesting Memories. A Paradoxical Life".

Answer by Zsbán Ambrus for Examples of common false beliefs in mathematics.

2011-04-07T11:23:53Z

This might not be common, but I once believed the following.

Let $ A, B $ be integers, and define a sequence by the linear recurrence $ s_n = A s_{n-1} + B s_{n-2} $ with the base case $ s_0 = 0 $, $ s_1 = 1 $. Two important special cases are the Fibonacci sequence ($ A = B = 1 $) and the sequence $ s_n = 2^n - 1 $ (where $ A = 3 $, $ B = -2 $). Then, for any integers $ n $ and $ k $, $ \gcd(s_n, s_k) = s_{\gcd(n,k)} $.

This is true in the two mentioned special cases, so it's tempting to believe it's true in general. But there's a counterexample: $ A = B = k = 2 $, $ n = 3 $.

Update: corrected the powers of two minus one example from B = 2 to B = -2. Thanks to Harry Altman.

Answer by Zsbán Ambrus for Elementary+Short+Useful

2011-04-04T09:14:21Z

Sanov's theorem of large deviations.

I don't have to prove anything, right? If they want a proof, they'll look it up in a book later.

Assume the students already know about the central limit theorem. Explain how the two theorems talk about limits in different direction: let $ S_n $ be the sum of $ n $ independent variables of identical distributions (real valued, with zero mean and finite variance), the central limit theorem gives a limit of the unscaled probability $ P(S_n/\sqrt{n} < c) $, this limit is strictly between 0 and 1; whereas large deviation theorems give the rate of decrease of a probability like $ P(S_n/n < c) $.

Answer by Zsbán Ambrus for Generalizations of Planar Graphs

2011-03-08T16:10:52Z

Alon Amit already has mentioned above the generalization where you ask whether a d dimensional simplicial complex can be embedded continuously to a 2*d*-dimensional space. The case of 1 = d gives planar graphs. Jiří Matoušek: Using the Borsuk-Ulam Theorem however notes that you get a different generalization if you ask for an embedding where every simplex of the original complex is embedded linearly. (This is thus not a topological invariant of the simplicial complex.) This too is a true generalization of the class of planar graphs, for every planar graph can be drawn with straight edges.

Answer by Zsbán Ambrus for Counting card distributions when cards are duplicated

2011-02-20T10:55:10Z

While you've already got a good answer, let me offer a worse one.

Take a random deal of the cards (12 to each player), and let X be the number of card faces whose two cards go to different players. The expected value of $ (48!/12!^4)\cdot2^{-X} $ is then equal to the number of different deals. You can thus use a Monte-Carlo method to estimate this number: you just generate lots of random deals and take the average of that random variable.

I've tried to run a quick and dirty simulation, and got $ 2.25\cdot10^{21} $ as the result, but I didn't verify the code, so the result could be completely wrong (but at least it agrees with Ira Gessel's figure above).

Answer by Zsbán Ambrus for What is an example of a finite centerless group with at least 3 generators?

2011-01-28T08:11:42Z

I can't prove this, but the Rubik's cube group might work.

Update: so this doesn't work. Thanks for the comments.

Pairwise intersecting sets of fixed size

2010-04-13T18:55:27Z

The Erdős-Ko-Rado theorem talks about how large an intersecting set system (a set of pairwise intersecting sets) can be if the size of the base set is fixed. I'm interested about intersecting set systems where the base set is not fixed, but the size of the sets is bounded. I can prove the following lemma (see proof below).

Lemma 1. For every natural number $k$ there is a natural number $N(k)$ such that for every set $C$ each of whose elements are sets of size at most $k$, if every two element of $C$ has a common member, then there is a kernel $A$ which is a set of size at most $N$ so that every two element of $C$ also has a common member that's in $A$.

I'd like to know if this lemma is known in some literature, and whether you can give me a simpler proof for it than mine.

I'd also like to know what bound you can give on $N(k)$. An exact bound is probably hard and not too interesting, but I'd like to get the order of magnitude, say whether you can make $N(k)$ a polynomial of $k$. My proof only gives $N(k) = 2^{O(k^2)}$, so anything with a smaller order of magnitude would be nice. (I know that $N(k)$ has to be $\Omega(k^2)$. You can show this by chosing a prime $q$ between $k/2-1$ and $k-1$ and then letting $C$ be the set of lines of a finite projective plane of order $q$.)

There's also a strengthening of the lemma, which follows easily from my proof and can be useful.

Lemma 2. For every natural number $k$ there is a natural number $N^{\ast}(k)$ such that for every set $C$ each of whose elements are sets of size at most $k$, if every two element of $C$ has a common member, then there is a kernel $A$ which is a set of size at most $N^{\ast}$ so that if $Y \in C$ and $X$ is a set that intersects every element of $C$ and $X$ has at most $k$ elements then $X \cap Y \cap A$ is nonempty.

Update: the original phrasing of lemma 2 was wrong, I added the condition that $|X|\le k$.

I'm asking the same questions as above for this stronger version, and also whether it follows easily from the first lemma.

Proof of lemma 1.

Fix $k$. We will use induction on $p$ to show the existence of a set $A_p$ such that the size of $A_p$ is bounded by a constant natural number depending only on $k$ and $p$ (but not $C$), and that for every $X \in C$ either $p \le |X \cap A_p|$ or the intersection $X \cap Y \cap A_p$ is non-empty for every $Y\in C$. This is enough because $A = A_{p+1}$ satisfies the conditions of the lemma (in fact even $A = A_p$ would work). The case of $p = 0$ is trivial, because $A_0$ can be the empty set.

Now suppose we have found $A_p$ and we want to construct $A_{p+1}$. Now sort the elements of $C$ in equivalence classes such that two element is equivalent if their intersection with $A_p$ is equal. There are at most as many such classes as subsets of $A_p$ (or even subsets with at most $k$ elements), which is a constant bound because the size of $A_p$ is bounded by a constant. Now chose a single element from each equivalence class and let $B$ be the set of these elements. Let $A_{p+1} := A_p \cup \bigcup_{Y\in B} Y$.

Thus all we have to prove is that for every $X \in C$ either $X \cap A_{p+1}$ has at least $p+1$ elements or it intersects every element of $C$. From the induction hypothesis we know that $X \cap A_p$ either has at least $p$ elements or intersects with every element of $C$. If it's the latter, we're done, because $X \cap A_{p+1}$ is a superset of $X \cap A_p$, so let's now assume the former: $X \cap A_p$ has at least $p$ elements. Now if $X \cap A_{p+1}$ intersects all elements of $C$ then we're done, so we can also assume that there is a $Z \in C$ such that $X \cap A_{p+1} \cap Z$ is empty. Now consider the class of $Z$ in the equivalence we defined above, that is, all sets $Y$ for which $Y \cap A_p = Z \cap A_p$, and let $Y$ be the representant element we chose from this class for the construction. This means that $Y \in B$ thus $Y \subset A_{p+1}$. Now $X$ and $Y$ has a common element, say $x$. Now it's not possible that $x \in A_p$, because by our second assumption $X \cap Y \cap A_p = X \cap Z \cap A_p \subset X \cap Z \cap A_{p+1}$ is empty. But then $X \cap A_{p+1}$ has the at least $p$ elements of $X \cap A_p$ from our first assumption (because $A_p \subset A_{p+1}$), and the extra element $x$ which is not in $X \cap A_p$, so it has at least $p + 1$ elements, which completes our proof.

Answer by Zsbán Ambrus for Pairwise intersecting sets of fixed size

2011-02-07T15:32:51Z

I found out that this is a known problem, and was solved in 1973. The Lovász: Combinatorical problems and exercises actually gives a solution in exercise 13.27. This gives asymptotically better estimates than anything we could derive here.

A generalization (where the sets are required to be s-wise intersecting instead of pairwise) can be found in N. Alon, Z. Füredi: On the Kernel of Intersecting Families, Graphs and Combinatorics 3, 91–94 (1987).

Comment by Zsbán Ambrus

2013-05-05T11:57:07Z

Is A and X the same?

Comment by Zsbán Ambrus

2013-05-03T18:26:31Z

I believe there is such an algorithm but it's quite complicated.

Comment by Zsbán Ambrus

2013-04-25T08:22:31Z

You should ask this question on physics.stackexchange.com instead of here. (Btw, does "in nature" mean you don't examine physicists in carefully conducted laboratory experiments like xkcd.com/669 ?)

Comment by Zsbán Ambrus

2013-04-23T09:01:46Z

Ah right, Cantor set. Sorry. Ignore what I said then, and take what Loïc Teyssier says.

Comment by Zsbán Ambrus

2013-04-22T08:40:45Z

@Hentry Wen: Henr.L is right, that function is everywhere discontinuous, because it takes the value 0 and 1 in every interval.

Comment by Zsbán Ambrus

2013-04-15T19:20:13Z

Keyword to search for: online bin packing, next fit.

Comment by Zsbán Ambrus

2013-04-10T09:43:50Z

@Martin Brandenburg: instead of your first link, do you mean mathoverflow.net/questions/7330/… ?

Comment by Zsbán Ambrus

2013-04-07T09:33:12Z

Some of the so called “heuristic algorithms” published in computer science journals are such that a 12 year old kid could have found them by banging randomly on the keyboard then fixing syntax errors. Does that count as a discovery?

Comment by Zsbán Ambrus

2013-04-04T20:01:03Z

Nice! This solution actually seems more easy to understand than the others.

Comment by Zsbán Ambrus

2013-03-19T18:39:36Z

I agree with Douglas Zare. For example, even as an adult, I can't make a convincing drawing of Pappus's theorem (Pascal's theorem applied on two lines used a degenerate conic) come out right if drawn with a straightedge.

Comment by Zsbán Ambrus

2013-03-10T12:42:54Z

Does the death of Archimedes count? The social context has caused his death, and you can find exaggerated claims about how much he could have advanced mathematics and science and engineering if he lived longer.

Comment by Zsbán Ambrus

2013-02-24T15:06:35Z

Could you derive this result from supposing Goldbach's conjecture?

Comment by Zsbán Ambrus

2013-02-24T15:04:20Z

Note that Michael Greinecker has also mentioned Baryshnikov's proof in an earlier reply.

Comment by Zsbán Ambrus

2013-02-22T09:47:33Z

See cstheory.stackexchange.com/questions/2708/…

Comment by Zsbán Ambrus

2013-01-28T13:57:52Z

Could you change the title to something more specific, such as "Difference of two complete powers"?