|
|
Extremal combinatorics of matrices, sequences and sets of permutations
Cibulka, Josef ; Valtr, Pavel (advisor) ; Füredi, Zoltán (referee) ; Jelínek, Vít (referee)
Title: Extremal combinatorics of matrices, sequences and sets of permutations Author: Josef Cibulka Department: Department of Applied Mathematics Supervisor: Doc. RNDr. Pavel Valtr, Dr., Department of Applied Mathematics Abstract: This thesis studies questions from the areas of the extremal theory of {0, 1}-matrices, sequences and sets of permutations, which found many ap- plications in combinatorial and computational geometry. The VC-dimension of a set P of n-element permutations is the largest integer k such that the set of restrictions of the permutations in P on some k-tuple of positions is the set of all k! permutation patterns. We show lower and upper bounds quasiexponential in n on the maximum size of a set of n-element permutations with VC-dimension bounded by a constant. This is used in a paper of Jan Kynčl to considerably improve the upper bound on the number of weak isomorphism classes of com- plete topological graphs on n vertices. For some, mostly permutation, matrices M, we give new bounds on the number of 1-entries an n × n M-avoiding matrix can have. For example, for every even k, we give a construction of a matrix with k2 n/2 1-entries that avoids one specific k-permutation matrix. We also give almost tight bounds on the maximum number of 1-entries in matrices avoiding a fixed layered...
|
|
|
The effect of nest quality for breeding success in Great Reed Warbler
Jelínek, Václav ; Procházka, Petr (advisor) ; Fuchs, Roman (referee)
Nests are key structures for the reproduction of majority of avian species and as such they should be subject to natural selection. Six hypotheses have been suggested to explain variance in avian nest size. In my master thesis I evaluate their validity in the Great Reed Warbler (Acrocephalus arundinaceus). First two hypotheses describe responses of nest size to predation and brood parasitism. These two selection pressures may lead to the reduction of nest size, but no evidence of their impact on nest dimensions was obtained. However, I found a significant but negative relationship between the probability of nest predation and soft nest height. No such relationship was found between the probability of brood parasitism and nest size characteristics. The incidence of brood parasitism was affected only by nest visibility from the nearest cuckoo perch site and distance from open water. More visible nests suffered heavier parasitism while those located deeper in reed beds were better protected from cuckoo parasitism. Another four hypotheses describe selection pressures which favour large nests or some of their functional parts. The thermoregulatory hypothesis, the sexual display hypothesis and the nest support hypothesis did not explain nest size variation. I found support for the clutch size hypothesis,...
|
|
| |
|
|
Intersection representations of graphs
Töpfer, Martin ; Jelínek, Vít (advisor) ; Pangrác, Ondřej (referee)
This thesis is devoted to the outer and grounded string representations of graphs and their subclasses. A string representation of a graph is a set of strings (bounded continuous curves in a plane), where each string corresponds to one vertex of the graph. Two strings intersect each other if and only if the two corresponding vertices are adjacent in the original graph. An outer string graph is a graph with a string representation where strings are realized inside a disk and one endpoint of each string lies on the boundary of the disk. Similarly, in case of grounded string graphs the strings lie in a common half- plane with one endpoint of each string on the boundary of the half-plane. We give a summary of subclasses of grounded string graphs and proves several results about their mutual inclusions and separations. To prove those, we use an order-forcing lemma which can be used to force a particular order of the endpoints of the string on the boundary circle or boundary line. The second part of the thesis contains proof that recognition of outer string graphs is NP-hard. 1
|
|
|
Impact of intraspecific brood parasitism on reproductive success of barn swallow females
Hodanová, Jana ; Jelínek, Václav (advisor) ; Klvaňa, Petr (referee)
Intraspecific nest parasitism is one of the alternative reproductive strategies of birds, in which a parasitic female lays her eggs in the nest of another female of the same species, thereby increasing her reproductive success while avoiding any demands on parental care. In this paper, I used data from long-term monitoring of a population of the barn swallow, Hirundo rustica, in the Třeboň region. Using genetic analysis, I determined all parasitic and non-parasitic females that occurred in this socially monogamous species in the studied populations with regard to the difference between classical parasitism and quasi-parasitism. In my thesis, I also described the egg-laying timing of parasitic females in context of host egg-laying, compared qualitative characteristics of individual parasitic and non-parasitic females, and investigated the effect of parasitism on female reproductive success. The results suggest that female parasitism is a relatively common phenomenon in swallow populations and that the occurrence of parasitism cannot be predicted by the quality of females. However, I found a positive relationship between parasitism and female reproductive success. Finally, several ways of timing of parasitism have been observed. Key words Barn swallow, conspecific brood parasitism, hypotheses,...
|
|
|
Partial representation extension for subclasses of interval graphs
Onduš, Daniel ; Kratochvíl, Jan (advisor) ; Jelínek, Vít (referee)
The problem of extending partial representations for an interval graph asks, whether it is possible to extend a given representation of some vertices to a valid representation of the entire graph. In this thesis we extend the recent result of Klavík et al. who proved REPEXT can be decided for proper and unit interval graphs in polynomial time. We describe properties of PI± and U± graphs and their representations and present algorithms deciding REPEXT for these classes in polynomial time. In the process, we characterize relations between the K1,3's in a graph and show that we can decide the open vertex of every K1,3. We also define notions of representation of the same order type and locally similar representations as well as intervals forced and locally forced to be closed (open) that are essential for extending partial representations when multiple types of intervals can occur in the same representation. We characterize intervals forced and locally forced to be closed (open) in a U± graph using integer gaps in the pre-representation and we construct lower bounds for the rightmost endpoint of a component in polynomial time.
|
|
| |
|
|
Matrices without forbidden interval minors
Surma, David ; Jelínek, Vít (advisor) ; Klazar, Martin (referee)
In the thesis, we study the structure of binary matrices which do not contain a pat- tern P as an interval minor. We also deal with matrices that are critical for P, i.e., matrices without P which after changing any 0-entry to 1-entry contain the forbidden pattern P. First, we describe matrices critical for any one-line pattern. Then we deal with all patterns with two rows and three columns which contain at most four 1-entries. Finally, we characterize the matrices critical for the alternating pattern of size 2 × 4. 1
|
|
|
Algorithmic aspects of intersection representations
Chmel, Petr ; Jelínek, Vít (advisor) ; Kratochvíl, Jan (referee)
As some problems are (NP-)hard to solve in the general case, a possible approach is to try to solve the problem on a restricted class of graphs. In the thesis, we focus on graphs induced by axis-aligned L-shapes, so-called L-graphs, and a similar class of axis- aligned L-shapes and L-shapes, referred to as {L, L}-graphs, with two vertices sharing an edge if and only if their respective curves intersect. We show that recognizing both L- graphs and {L, L}-graphs is NP-complete. The second part of the thesis focuses on other typical decision problems on L-graphs and their relatives: finding the clique number, the independence number or a 3-coloring.
|
|
|
Computational and structural apects of interval graphs and their variants
Novotná, Jana ; Kratochvíl, Jan (advisor) ; Jelínek, Vít (referee)
Interval graphs, intersection graphs of segments on a real line (intervals), play a key role in the study of algorithms and special structural properties. Unit interval graphs, their proper subclass, where each interval has a unit length, has also been extensively studied. We study mixed unit interval graphs-a generalization of unit interval graphs where each interval has still a unit length, but intervals of more than one type (open, closed, semi-closed) are allowed. This small modification captures a much richer class of graphs. In particular, mixed unit interval graphs are not claw-free, compared to unit interval graphs. Heggernes, Meister, and Papadopoulos defined a representation of unit interval graphs called the bubble model which turned out to be useful in algorithm design. We extend this model to the class of mixed unit interval graphs. The original bubble model was used by Boyaci, Ekim, and Shalom for proving the polynomiality of the MaxCut problem on unit interval graphs. However, we found a significant mistake in the proof which seems to be hardly repairable. Moreover, we demonstrate advantages of such model by providing a subexponential-time algorithm solving the MaxCut problem on mixed unit interval graphs using our extended version of the bubble model. In addition, it gives us a polynomial-time...
|
guest ::
RSS feed.