Bipartite Powers of k-chordal Graphs

Let k be an integer and k >= 3. A graph G is k-chordal if G does not have an induced cycle of length greater than k. From the definition it is clear that 3-chordal graphs are precisely the class of chordal graphs. Duchet proved that, for every positive integer m, if G m is chordal then so is G(m+2). Brandst `` adt et al. in Andreas Brandsadt, Van Bang Le, and Thomas Szymczak. Duchet- type theorems for powers of HHD- free graphs. Discrete Mathematics, 177(1- 3): 9- 16, 1997.] showed that if G m is k - chordal, then so is G(m+2). Powering a bipartite graph does not preserve its bipartitedness. In order to preserve the bipartitedness of a bipartite graph while powering Chandran et al. introduced the notion of bipartite powering. This notion was introduced to aid their study of boxicity of chordal bipartite graphs. The m - th bipartite power G(m]) of a bipartite graph G is the bipartite graph obtained from G by adding edges (u; v) where d G (u; v) is odd and less than or equal to m. Note that G(m]) = G(m+1]) for each odd m. In this paper we show that, given a bipartite graph G, if G is k-chordal then so is G m], where k, m are positive integers with k >= 4

On Additive Combinatorics of Permutations of Z(n)

Let Z(n) denote the ring of integers modulo n. A permutation of Z(n) is a sequence of n distinct elements of Z(n). Addition and subtraction of two permutations is defined element-wise. In this paper we consider two extremal problems on permutations of Z(n), namely, the maximum size of a collection of permutations such that the sum of any two distinct permutations in the collection is again a permutation, and the maximum size of a collection of permutations such that no sum of two distinct permutations in the collection is a permutation. Let the sizes be denoted by s (n) and t (n) respectively. The case when n is even is trivial in both the cases, with s (n) = 1 and t (n) = n!. For n odd, we prove (n phi(n))/2(k) <= s(n) <= n!.2(-)(n-1)/2/((n-1)/2)! and 2 (n-1)/2 . (n-1/2)! <= t (n) <= 2(k) . (n-1)!/phi(n), where k is the number of distinct prime divisors of n and phi is the Euler's totient function.

REPRESENTING A CUBIC GRAPH AS THE INTERSECTION GRAPH OF AXIS-PARALLEL BOXES IN THREE DIMENSIONS

We show that every graph of maximum degree 3 can be represented as the intersection graph of axis parallel boxes in three dimensions, that is, every vertex can be mapped to an axis parallel box such that two boxes intersect if and only if their corresponding vertices are adjacent. In fact, we construct a representation in which any two intersecting boxes touch just at their boundaries.

Rainbow matchings in strongly edge-colored graphs

A rainbow matching of an edge-colored graph G is a matching in which no two edges have the same color. There have been several studies regarding the maximum size of a rainbow matching in a properly edge-colored graph G in terms of its minimum degree 3(G). Wang (2011) asked whether there exists a function f such that a properly edge-colored graph G with at least f (delta(G)) vertices is guaranteed to contain a rainbow matching of size delta(G). This was answered in the affirmative later: the best currently known function Lo and Tan (2014) is f(k) = 4k - 4, for k >= 4 and f (k) = 4k - 3, for k <= 3. Afterwards, the research was focused on finding lower bounds for the size of maximum rainbow matchings in properly edge-colored graphs with fewer than 4 delta(G) - 4 vertices. Strong edge-coloring of a graph G is a restriction of proper edge-coloring where every color class is required to be an induced matching, instead of just being a matching. In this paper, we give lower bounds for the size of a maximum rainbow matching in a strongly edge-colored graph Gin terms of delta(G). We show that for a strongly edge-colored graph G, if |V(G)| >= 2 |3 delta(G)/4|, then G has a rainbow matching of size |3 delta(G)/4|, and if |V(G)| < 2 |3 delta(G)/4|, then G has a rainbow matching of size |V(G)|/2] In addition, we prove that if G is a strongly edge-colored graph that is triangle-free, then it contains a rainbow matching of size at least delta(G). (C) 2015 Elsevier B.V. All rights reserved.

SEPARATION DIMENSION OF BOUNDED DEGREE GRAPHS

The separation dimension of a graph G is the smallest natural number k for which the vertices of G can be embedded in R-k such that any pair of disjoint edges in G can be separated by a hyperplane normal to one of the axes. Equivalently, it is the smallest possible cardinality of a family F of total orders of the vertices of G such that for any two disjoint edges of G, there exists at least one total order in F in which all the vertices in one edge precede those in the other. In general, the maximum separation dimension of a graph on n vertices is Theta(log n). In this article, we focus on bounded degree graphs and show that the separation dimension of a graph with maximum degree d is at most 2(9) (log*d)d. We also demonstrate that the above bound is nearly tight by showing that, for every d, almost all d-regular graphs have separation dimension at least d/2]

Two player game variant of the Erdos-Szekeres problem

The classical Erdos-Szekeres theorem states that a convex k-gon exists in every sufficiently large point set. This problem has been well studied and finding tight asymptotic bounds is considered a challenging open problem. Several variants of the Erdos-Szekeres problem have been posed and studied in the last two decades. The well studied variants include the empty convex k-gon problem, convex k-gon with specified number of interior points and the chromatic variant. In this paper, we introduce the following two player game variant of the Erdos-Szekeres problem: Consider a two player game where each player playing in alternate turns, place points in the plane. The objective of the game is to avoid the formation of the convex k-gon among the placed points. The game ends when a convex k-gon is formed and the player who placed the last point loses the game. In our paper we show a winning strategy for the player who plays second in the convex 5-gon game and the empty convex 5-gon game by considering convex layer configurations at each step. We prove that the game always ends in the 9th step by showing that the game reaches a specific set of configurations.

DETERMINISTIC ALGORITHMS FOR MATCHING AND PACKING PROBLEMS BASED ON REPRESENTATIVE SETS

In this work, we study the well-known r-DIMENSIONAL k-MATCHING ((r, k)-DM), and r-SET k-PACKING ((r, k)-SP) problems. Given a universe U := U-1 ... U-r and an r-uniform family F subset of U-1 x ... x U-r, the (r, k)-DM problem asks if F admits a collection of k mutually disjoint sets. Given a universe U and an r-uniform family F subset of 2(U), the (r, k)-SP problem asks if F admits a collection of k mutually disjoint sets. We employ techniques based on dynamic programming and representative families. This leads to a deterministic algorithm with running time O(2.851((r-1)k) .vertical bar F vertical bar. n log(2)n . logW) for the weighted version of (r, k)-DM, where W is the maximum weight in the input, and a deterministic algorithm with running time O(2.851((r-0.5501)k).vertical bar F vertical bar.n log(2) n . logW) for the weighted version of (r, k)-SP. Thus, we significantly improve the previous best known deterministic running times for (r, k)-DM and (r, k)-SP and the previous best known running times for their weighted versions. We rely on structural properties of (r, k)-DM and (r, k)-SP to develop algorithms that are faster than those that can be obtained by a standard use of representative sets. Incorporating the principles of iterative expansion, we obtain a better algorithm for (3, k)-DM, running in time O(2.004(3k).vertical bar F vertical bar . n log(2)n). We believe that this algorithm demonstrates an interesting application of representative families in conjunction with more traditional techniques. Furthermore, we present kernels of size O(e(r)r(k-1)(r) logW) for the weighted versions of (r, k)-DM and (r, k)-SP, improving the previous best known kernels of size O(r!r(k-1)(r) logW) for these problems.

Upper bound on cubicity in terms of boxicity for graphs of low chromatic number

The boxicity (respectively cubicity) of a graph G is the least integer k such that G can be represented as an intersection graph of axis-parallel k-dimensional boxes (respectively k-dimensional unit cubes) and is denoted by box(G) (respectively cub(G)). It was shown by Adiga and Chandran (2010) that for any graph G, cub(G) <= box(G) log(2) alpha(G], where alpha(G) is the maximum size of an independent set in G. In this note we show that cub(G) <= 2 log(2) X (G)] box(G) + X (G) log(2) alpha(G)], where x (G) is the chromatic number of G. This result can provide a much better upper bound than that of Adiga and Chandran for graph classes with bounded chromatic number. For example, for bipartite graphs we obtain cub(G) <= 2(box(G) + log(2) alpha(G)] Moreover, we show that for every positive integer k, there exist graphs with chromatic number k such that for every epsilon > 0, the value given by our upper bound is at most (1 + epsilon) times their cubicity. Thus, our upper bound is almost tight. (c) 2015 Elsevier B.V. All rights reserved.

Utilização de modelos de classificação para mineração de dados relacionados à aprendizagem de matemática e ao perfil de professores do ensino fundamental

No presente trabalho foram utilizados modelos de classificação para minerar dados relacionados à aprendizagem de Matemática e ao perfil de professores do ensino fundamental. Mais especificamente, foram abordados os fatores referentes aos educadores do Estado do Rio de Janeiro que influenciam positivamente e negativamente no desempenho dos alunos do 9 ano do ensino básico nas provas de Matemática. Os dados utilizados para extrair estas informações são disponibilizados pelo Instituto Nacional de Estudos e Pesquisas Educacionais Anísio Teixeira que avalia o sistema educacional brasileiro em diversos níveis e modalidades de ensino, incluindo a Educação Básica, cuja avaliação, que foi foco deste estudo, é realizada pela Prova Brasil. A partir desta base, foi aplicado o processo de Descoberta de Conhecimento em Bancos de Dados (KDD - Knowledge Discovery in Databases), composto das etapas de preparação, mineração e pós-processamento dos dados. Os padrões foram extraídos dos modelos de classificação gerados pelas técnicas árvore de decisão, indução de regras e classificadores Bayesianos, cujos algoritmos estão implementados no software Weka (Waikato Environment for Knowledge Analysis). Além disso, foram aplicados métodos de grupos e uma metodologia para tornar as classes uniformemente distribuídas, afim de melhorar a precisão dos modelos obtidos. Os resultados apresentaram importantes fatores que contribuem para o ensino-aprendizagem de Matemática, assim como evidenciaram aspectos que comprometem negativamente o desempenho dos discentes. Por fim, os resultados extraídos fornecem ao educador e elaborador de políticas públicas fatores para uma análise que os auxiliem em posteriores tomadas de decisão.

An investigation of the mathematical elements of the Dai culture south-west Yunnan province, China

Dai ethnic mathematical culture is an important part of Dai ethnic culture. Mathematical elements show in their daily life. Through a research project of the Yunnan Dehong Dai people in southwest China, We collected the first-hand information, tried to do a small investigative study, and collected mathematics teaching resources that is useful to primary and secondary schools students on mathematics learning  in this minority areas. Keyword: Dai ethnic; Mathematical culture; Primary and secondary schools; Teaching resources.

Ethnomathematical research and drama in education techniques: developing a dialogue in a geometry class of 10th grade students

Ethnomathematical research, together with digital technologies (WebQuest) and Drama-in- Education (DiE) techniques, can create a fruitful learning environment in a mathematics classroom—a hybrid/third space—enabling increased student participation and higher levels of cognitive engagement. This article examines how ethnomathematical ideas processed within the experiential environment established by the Drama-in-Education techniques challenged students‘ conceptions of the nature of mathematics, the ways in which students engaged with mathematics learning using mind and body, and the ̳dialogue‘ that was developed between the Discourse situated in a particular practice and the classroom Discourse of mathematics teaching. The analysis focuses on an interdisciplinary project based on an ethnomathematical study of a designing tradition carried out by the researchers themselves, involving a search for informal mathematics and the connections with context and culture; 10th grade students in a public school in Athens were introduced to the mathematics content via an original WebQuest based on this previous ethnomathematical study; Geometry content was further introduced and mediated using the Drama-in-Education (DiE) techniques. Students contributed in an unfolding dialogue between formal and informal knowledge, renegotiating both mathematical concepts and their perception of mathematics as a discipline.