Artículos con la etiqueta ‘Combinatorics (math.CO)’

Szemerédi’s regularity lemma revisited

Por • 5 nov, 2013 • Category: Ciencia y tecnología

Szemer\’edi’s regularity lemma is a basic tool in graph theory, and also plays an important role in additive combinatorics, most notably in proving Szemer\’edi’s theorem on arithmetic progressions . In this note we revisit this lemma from the perspective of probability theory and information theory instead of graph theory, and observe a variant of this lemma which introduces a new parameter F . This stronger version of the regularity lemma was iterated in a recent paper of the author to reprove the analogous regularity lemma for hypergraphs.



Alcuin’s Propositiones de Civitatibus: the Earliest Packing Problems

Por • 9 ago, 2013 • Category: Opinion

We consider three problems about cities from Alcuin’s_Propositiones ad acuendos juvenes_. These problems can be considered as the earliest packing problems difficult also for modern state-of-the-art packing algorithms. We discuss the Alcuin’s solutions and give the known (to the author) best solutions to these problems.



Hedetniemi’s conjecture for uncountable graphs

Por • 7 ago, 2013 • Category: Opinion

It is proved that in Godel’s constructible universe, for every infinite successor cardinal k, there exist graphs G and H of size and chromatic number k, for which the tensor product graph (G x H) is countably chromatic.



Solvability of Cubic Graphs and the Four Color Theorem

Por • 20 jul, 2013 • Category: Crítica

The aim of this paper is to assert that the minimum number of colors required to color a geographical map and the angle-sum of a triangle are twin invariants of the two-dimensional plane. Peter Tait proved, in an 1880 paper, that a bridgeless cubic plane graph G has a 4-face coloring if and only if G has a 3-edge coloring. In this paper, we explore the edge coloring problem of cubic graphs by using the newly proposed complex coloring approach. The concept of variable edges is introduced in the complex coloring method; a proper coloring is achieved by completely eliminating all variables in a color configuration of a cubic graph. The specification of solvable conditions is based on the decomposition of the configuration into maximal two-colored sub-graphs. The class of cubic graphs that does not have 3-edge coloring, called snarks, can be naturally identified by the proposed unsolvability condition.



Planar 4-critical graphs with four triangles

Por • 12 jun, 2013 • Category: Opinion

By the Grunbaum-Aksenov Theorem (extending Grotzsch’s Theorem) every planar graph with at most three triangles is 3-colorable. However, there are infinitely many planar 4-critical graphs with exactly four triangles. We describe all such graphs. This answers a question of Erdos from 1990.



Independent Events in a Simple Random Experiment and the Meaning of Independence

Por • 22 abr, 2013 • Category: Filosofía

We count the number and patterns of pairs and tuples of independent events in a simple random experiment: first a fair coin is flipped and then a fair die is tossed. The first number, equal to 888,888, suggest that there are some open questions about the structure of independence even in a finite sample space. We discuss briefly these questions and possible approaches to answer them.



An Erdős–Ko–Rado theorem for matchings in the complete graph

Por • 21 abr, 2013 • Category: Opinion

We consider the following higher-order analog of the Erd\H{o}s–Ko–Rado theorem. For positive integers r and n with r<= n, let M^r_n be the family of all matchings of size r in the complete graph K_{2n}. For any edge e in E(K_{2n}), the family M^r_n(e), which consists of all sets in M^r_n containing e, is called the star centered at e. We prove that if r



Growth in groups: ideas and perspectives

Por • 12 mar, 2013 • Category: Opinion

This is a survey of methods developed in the last few years to prove results on growth in non-commutative groups. These techniques have their roots in both additive combinatorics and group theory, as well as other fields. We discuss linear algebraic groups, with SL_2(Z/pZ) as the basic example, as well as permutation groups. The emphasis lies on the ideas behind the methods.



Independent Events in a Simple Random Experiment and the Meaning of Independence

Por • 10 may, 2012 • Category: Educacion

We count the number and patterns of pairs and tuples of independent events in a simple random experiment: first a fair coin is flipped and then a fair die is tossed. The first number, equal to 888,888, suggest that there are some open questions about the structure of independence even in a finite sample space. We discuss briefly these questions and possible approaches to answer them.