A5027559065- Advanced Graph Theory Research
- Limits and Structures in Graph Theory
- Graph Labeling and Dimension Problems
- graph theory and CDMA systems
- Graph theory and applications
- Complexity and Algorithms in Graphs
- Computational Geometry and Mesh Generation
- Advanced Topology and Set Theory
- semigroups and automata theory
- Interconnection Networks and Systems
- Bayesian Methods and Mixture Models
- Coding theory and cryptography
- Constraint Satisfaction and Optimization
- Topological and Geometric Data Analysis
- Formal Methods in Verification
- Analytic Number Theory Research
- Advanced Mathematical Identities
- Advanced Combinatorial Mathematics
- Markov Chains and Monte Carlo Methods
- Finite Group Theory Research
- Mathematical Dynamics and Fractals
- Scheduling and Optimization Algorithms
- Optimization and Search Problems
- Heusler alloys: electronic and magnetic properties
- Logic, Reasoning, and Knowledge
Masaryk University
2016-2025
University of Warwick
2014-2023
Charles University
2007-2020
Center for Discrete Mathematics and Theoretical Computer Science
2012-2013
University of West Bohemia
2011-2012
Czech Academy of Sciences, Institute of Theoretical and Applied Mechanics
2007-2012
Instituto de Física Teórica
2004-2010
Georgia Institute of Technology
2006
Simon Fraser University
2006
Technische Universität Berlin
2005
We present a linear-time algorithm for deciding first-order (FO) properties in classes of graphs with bounded expansion, notion recently introduced by Nešetřil and Ossona de Mendez. This generalizes several results from the literature, because many natural have expansion: tree-width, all proper minor-closed graphs, degree, no subgraph isomorphic to subdivision fixed graph, that can be drawn surface such way each edge crosses at most constant number other edges. deduce there is an almost FO...
A list channel assignment problem is a triple (G,L,w), where G graph, L function which assigns to each vertex of integers (colors), and w edge positive integer (its weight). coloring c the vertices proper if c(v)\in L(v)$ for v $|c(u)-c(v)|\ge w(uv)$ uv. weighted degree $\deg_w(v)$ sum weights edges incident with v. If connected, $|L(v)|>\deg_w(v)$ at least one v, $|L(v)|\ge\deg_w(v)$ all then always exists. balanced $|L(v)|=\deg_w(v)$ We characterize problems (G,L,w) admit coloring. An...
We present a linear-time algorithm for deciding first-order logic (FOL) properties in classes of graphs with bounded expansion. Many natural have expansion: tree-width, all proper minor-closed graphs, degree, no sub graph isomorphic to subdivision fixed graph, and that can be drawn surface such way each edge crosses at most constant number other edges. also develop an almost FOL locally expansion, those include tree-width or excluding minor. More generally, we design dynamic data structure...
For permutations $${\pi}$$ and $${\tau}$$ of lengths $${|\pi|\le|\tau|}$$ , let $${t(\pi,\tau)}$$ be the probability that restriction to a random $${|\pi|}$$ -point set is (order) isomorphic . We show every sequence $${\{\tau_j\}}$$ such $${|\tau_j|\to\infty}$$ $${t(\pi,\tau_j)\to 1/4!}$$ for 4-point permutation quasirandom (that is, 1/|\pi|!}$$ ). This answers question posed by Graham.
A graph H is called common if the total number of copies in every and its complement asymptotically minimizes for random graphs. former conjecture Burr Rosta, extending a Erdos asserted that common. Thomason disproved both conjectures by showing complete order four not It now known fact graphs are very rare. Answering question Sidorenko Jagger, Stovicek from 1996 we show 5-wheel This provides first example three-colorable.
Abstract A classical result of Erdős, Lovász and Spencer from the late 1970s asserts that dimension feasible region densities graphs with at most k vertices in large is equal to number non-trivial connected vertices. Indecomposable permutations play role realm permutations, Glebov et al. showed pattern indecomposable are independent, i.e., permutation patterns size least . However, this lower bound not tight already for $k=3$ We prove Lyndon The proof exploits an interplay between algebra...