Artículos con la etiqueta ‘combinatoria’

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.

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

Regular graphs and the spectra of two-variable logic with counting

Por • 14 abr, 2013 • Category: Crítica

The spectrum of a first-order logic sentence is the set of natural numbers that are cardinalities of its finite models. This notion has been shown to be closely linked with complexity theory. In fact, asking whether the spectra of first-order logic sentences is closed under complement is equivalent to asking whether NE=coNE. In this paper we show that when restricted to using only two variables, the spectra of first-order logic sentences are closed under complement. In particular, we show that they are semilinear. At the heart of our proof are semilinear characterisations for the existence of regular graphs, the class of graphs in which there are a priori bounds on the degrees of the vertices.

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.

The Monty Hall Problem in the Game Theory Class

Por • 12 jul, 2011 • Category: Opinion

The basic Monty Hall problem is explored to introduce into the fundamental concepts of the game theory and to give a complete Bayesian and a (noncooperative) game-theoretic analysis of the situation. Simple combinatorial arguments are used to exclude the holding action and to find minimax solutions.