National Repository of Grey Literature 19 records found  1 - 10next  jump to record: Search took 0.01 seconds. 
Off-diagonal ordered Ramsey numbers
Poljak, Marian ; Balko, Martin (advisor) ; Hubička, Jan (referee)
We study ordered Ramsey numbers, an analogue of the classical Ramsey numbers for graphs with linearly ordered vertex sets. Inspired by a problem posed by Conlon, Fox, Lee and Sudakov, we focus on ordered Ramsey numbers of ordered matchings M< versus triangles. We generalize their lower bound on r<(M< , K< 3 ) for ordered matchings with any fixed interval chromatic number. We also analyze an upper bound on r<(M< , K< 3 ) for almost all ordered matchings M< with interval chromatic number 2 obtained by Rohatgi and improve it from O(n24/13 ) to O(n7/4 ). 1
Convex polygons in density-restricted point sets
Zálešák, Ondřej ; Valtr, Pavel (advisor) ; Balko, Martin (referee)
For A, a finite set of points in Rd , let ∆(A) denote the spread of A and be equal to the ratio of the maximum and the minimum distance of two points from A. Valtr (1992) proved that for sets of points in the plane with spread equal to Θ(n 1 2 ), the cardinality of the largest subset in convex position is Θ(n 1 3 ) in the worst case. The same article also contains an expanded upper bound on the guaranteed cardinality of subsets in convex position for sets with spread asymptotically higher than n 1 2 , and a brief construction for the proof. This thesis looks at this construction in detail. Furthermore it builds on the recent results for sets in higher dimensions, specifically discusses, whether it is possible to expand the upper bound in three-dimensional space for higher spreads with a similar technique as in the planar case. 1 Seznam použité literatury Valtr, P. (1992). Convex independent sets and 7-holes in restricted planar point sets. Discrete & Computational Geometry, 7(2), 135-152. 2
Generalized Moran process
Svoboda, Jakub ; Šámal, Robert (advisor) ; Balko, Martin (referee)
The Moran process is a model for simulating evolutionary dynamics. In that model, one mutant with higher fitness is introduced to a structured population. Evolution is simulated in rounds. In one round, individual is selected proportio- nally to its fitness and spreads to the place of a random neighbour. In this thesis, we motivate the Moran process, present basic results, and define our variant. We work in a vertex dependent model; every individual has fitness according to its type and occupied vertex. In the vertex dependent model we prove two theorems about the number of steps the process has to make to get to the stable state. We show that on the complete graph, the process takes only polynomially many steps and we find a graph where the process take exponentially many steps, but in the normal settings the number of steps is the same as on the complete graph. 1
Dots and Bpxes implementation
Balko, Martin ; Pangrác, Ondřej (advisor) ; Šámal, Robert (referee)
Title: Dots and Boxes implementation Author: Martin Balko Department: Department of Applied Mathematics Supervisor: RNDr. Ondřej Pangrác, Ph.D. Supervisor's email address: pangrac@kam.mff.cuni.cz Abstract: The presented thesis deals with the analysis of a popular logical game Dots and Boxes and its generalized versions. It focuses on the different methods and algorithms of opponent's artificial intelligence. The result of the work is implementation of the generalized version of this game in which a board editing, game with more than two players on the several levels of difficultness and the different face valuations are possible. Keywords: Dots and Boxes, Nimstring, Advanced Chain Counting
Implementation of the Sprouts game
Čížek, Tomáš ; Balko, Martin (advisor) ; Pangrác, Ondřej (referee)
Sprouts is a two-player pencil-and-paper game invented by John Conway and Michael Paterson in 1967. In the game, the players take turns in joining dots by curves according to simple rules, until one player cannot make a move. The Game of Sprouts is very popular and simple-looking, so it may come as a surprise that there are essentially no AI Sprouts players available. This lack of computer opponents is caused by the fact that the game hides a surprisingly high combinatorial complexity and implementing it involves fascinating programming challenges. We overcome all the implementation barriers and create the first user-friendly Sprouts application with a strong artificial intelligence after more than 50 years of the existence of the game. In particular, we combine results from the theory of nimbers with new methods based on Delaunay triangulations and crossing-preserving force-directed algorithms to develop an AI Sprouts player which plays a perfect game on up to 11 spots. 1
Generating simple drawings of graphs
Čermák, Filip ; Balko, Martin (advisor) ; Valtr, Pavel (referee)
In this thesis, we study the crossing numbers of complete graphs. After introducing a long history of the old problem of determining the crossing number of Kn, we survey the recent progress on the Harary-Hill conjecture by compiling proofs of this conjecture for special classes of drawings of Kn. We also create a program for generating a database of all simple drawings of Kn with n ≤ 8. We implement another program that visualizes these drawings and allows the user to create its own simple drawings of general graphs. The visualizer also captures the structure of crossings of the displayed drawings. We use our programs to verify a conjecture by Balko, Fulek, and Kynčl for small cases and we find a mistake in a paper by Mutzel and Oettershagen. 1
Ramsey-type results for ordered hypergraphs
Balko, Martin ; Valtr, Pavel (advisor)
Ramsey-type results for ordered hypergraphs Martin Balko Abstract We introduce ordered Ramsey numbers, which are an analogue of Ramsey numbers for graphs with a linear ordering on their vertices. We study the growth rate of ordered Ramsey numbers of ordered graphs with respect to the number of vertices. We find ordered match- ings whose ordered Ramsey numbers grow superpolynomially. We show that ordered Ramsey numbers of ordered graphs with bounded degeneracy and interval chromatic number are at most polynomial. We prove that ordered Ramsey numbers are at most polynomial for ordered graphs with bounded bandwidth. We find 3-regular graphs that have superlinear ordered Ramsey numbers, regardless of the ordering. The last two results solve problems of Conlon, Fox, Lee, and Sudakov. We derive the exact formula for ordered Ramsey numbers of mono- tone cycles and use it to obtain the exact formula for geometric Ramsey numbers of cycles that were introduced by K'arolyi et al. We refute a conjecture of Peters and Szekeres about a strengthening of the fa- mous Erd˝os-Szekeres conjecture to ordered hypergraphs. We obtain the exact formula for the minimum number of crossings in simple x-monotone drawings of complete graphs and provide a combinatorial characterization of these drawings in terms of colorings of ordered...
Bounds of number of empty tetrahedra and other simplices
Reichel, Tomáš ; Valtr, Pavel (advisor) ; Balko, Martin (referee)
Let M be a finite set of random uniformly distributed points lying in a unit cube. Every four points from M make a tetrahedron and the tetrahedron can either contain some of the other points from M, or it can be empty. This diploma thesis brings an upper bound of the expected value of the number of empty tetrahedra with respect to size of M. We also show how precise is the upper bound in comparison to an approximation computed by a straightforward algorithm. In the last section we move from the three- dimensional case to a general dimension d. In the general d-dimensional case we have empty d-simplices in a d-hypercube instead of empty tetrahedra in a cube. Then we compare the upper bound for d-dimensional case to the results from another paper on this topic. 1
Computing and estimating ordered Ramsey numbers
Poljak, Marian ; Balko, Martin (advisor) ; Hubička, Jan (referee)
We study ordered Ramsey numbers, which are an analogue of the classical Ramsey numbers for ordered graphs. We improve some already obtained results for a special class of ordered matchings and disprove a conjecture of Rohatgi. We expand the classical notion of Ramsey goodness to the ordered case and we attempt to characterize all Ram- sey good connected ordered graphs. We outline how Ramsey numbers can be obtained computationally and describe our SAT solver based utility developed to achieve this goal, which might be of use to other researchers studying this topic. 1

National Repository of Grey Literature : 19 records found   1 - 10next  jump to record:
See also: similar author names
2 Balko, Marek
6 Balko, Michal
Interested in being notified about new results for this query?
Subscribe to the RSS feed.