1. Plane triangulations without large 2-treesAllan Bickle, Gunnar Brinkmann, 2026, izvirni znanstveni članek Opis: In 1995 Leizhen Cai asked whether each plane triangulation has a spanning 2-tree. This question was recently answered in the negative by Bickle. He gave a plane triangulation on 38 vertices for which each 2-tree contained in it misses at least one vertex. We give a smaller example on 29 vertices and show that for each c>0 there are plane triangulations P=(V,E), so that each 2-tree that is a subgraph of P contains fewer than c|V| vertices. We also give a lower bound for the size of a maximum 2-tree in plane triangulations by proving that each plane triangulation P=(V,E) contains a 2-tree on at least log_2 (|V|-1)+4 -log_2 3 vertices. Finally we give structural criteria based on the decomposition trees of Jackson and Yu that guarantee the existence of spanning 2-trees in plane triangulations. The results are proven by using the close relation of 2-trees to hamiltonian cycles and to induced trees in the dual for plane triangulations without separating triangles.
Ključne besede: 2-tree, triangulation, Hamiltonian cycle, Yutsis partition
Objavljeno v RUP: 21.12.2025; Ogledov: 220; Prenosov: 1
 Celotno besedilo (339,53 KB) |
2. Bollobás set pair inequalities for compositionsAnyuan Tian, Yaokun Wu, 2025, izvirni znanstveni članek Opis: A d-composition of a set S is an ordered d-tuple (S₁, …, S_d) where S₁, …, S_d are pairwise disjoint subsets of S. If we have a sequence of d-compositions of a finite set and observe certain intersection patterns among parts of different compositions, what are the corresponding arithmetic constraints on the parameters of this sequence? When d = 1, many results in extremal combinatorics address this question. Bollobás set pair inequality is such a classic result for d = 2. In this note, we provide several arithmetic constraints for general d and propose a conjecture as a linear space analogue for one of them. Our study highlights the connection between extremal combinatorics and Young’s lattice of a rectangle.
Ključne besede: Katona weight, Lubell weight, partition, shape homomorphism, Young's lattice of a rectangle
Objavljeno v RUP: 22.10.2025; Ogledov: 410; Prenosov: 12
Celotno besedilo (583,73 KB) |
3. On commutative association schemes and associated (directed) graphsGiusy Monzillo, Safet Penjić, 2025, izvirni znanstveni članek Opis: Let ${\mathcal M}$ denote the Bose--Mesner algebra of a commutative $d$-class association scheme ${\mathfrak X}$ (not necessarily symmetric), and $\Gamma$ denote a (strongly) connected (directed) graph with adjacency matrix $A$. Under the assumption that $A$ belongs to ${\mathcal M}$, we describe the combinatorial structure of $\Gamma$. Moreover, we provide an algebraic-combinatorial characterization of $\Gamma$ when $A$ generates ${\mathcal M}$. Among else, we show that, if ${\mathfrak X}$ is a commutative $3$-class association scheme that is not an amorphic symmetric scheme, then we can always find a (directed) graph $\Gamma$ such that the adjacency matrix $A$ of $\Gamma$ generates the Bose--Mesner algebra ${\mathcal M}$ of ${\mathfrak X}$.
Ključne besede: commutative association schemes, association schemes, Bose-Mesner algebra, equitable partition, graphs generating schemes, quotient-polynomial graphs, x-distance-faithful intersection diagram
Objavljeno v RUP: 26.09.2025; Ogledov: 392; Prenosov: 4
Celotno besedilo (483,56 KB)
Gradivo ima več datotek! Več... |
4. Regular antilatticesKarin Cvetko-Vah, Michael Kinyon, Jonathan Leech, Tomaž Pisanski, 2019, izvirni znanstveni članek Opis: Antilattices ▫$(S; \vee, \wedge)$▫ for which the Green's equivalences ▫$\mathcal{L}_{(\vee)}$▫, ▫$\mathcal{R}_{(\vee)}$▫, ▫$\mathcal{L}_{(\wedge)}$▫ and ▫$\mathcal{R}_{(\wedge)}$▫ are all congruences of the entire antilattice are studied and enumerated.
Ključne besede: noncommutative lattice, antilattice, Green's equivalences, lattice of subvarieties, enumeration, partition, composition
Objavljeno v RUP: 03.01.2022; Ogledov: 2365; Prenosov: 18
Celotno besedilo (308,07 KB) |
5. |
6. |
7. |
8. Perfect phylogenies via branchings in acyclic digraphs and a generalization of Dilworth's theoremAdemir Hujdurović, Martin Milanič, Edin Husić, Romeo Rizzi, Alexandru I. Tomescu, 2017, objavljeni povzetek znanstvenega prispevka na konferenci Ključne besede: perfect phylogeny, NP-hard problem, branching, acyclic digraph, chain partition, Dilworth's theorem, min-max theorem, approximation algorithm, heuristic
Objavljeno v RUP: 17.09.2018; Ogledov: 3956; Prenosov: 125
 Povezava na celotno besedilo |
9. Reconstructing perfect phylogenies via binary matrices, branchings in DAGs, and a generalization of Dilworth's theoremAdemir Hujdurović, Martin Milanič, Edin Husić, Romeo Rizzi, Alexandru I. Tomescu, 2018, objavljeni povzetek znanstvenega prispevka na konferenci Ključne besede: perfect phylogeny, NP-hard problem, branching, acyclic digraph, chain partition, Dilworth's theorem, min-max theorem, approximation algorithm, heuristic
Objavljeno v RUP: 17.09.2018; Ogledov: 3733; Prenosov: 106
Celotno besedilo (1,44 MB)
Gradivo ima več datotek! Več... |
10. Reconstructing perfect phylogenies via binary matrices, branchings in DAGs, and a generalization of Dilworth's theoremMartin Milanič, 2018, objavljeni povzetek znanstvenega prispevka na konferenci (vabljeno predavanje) Ključne besede: perfect phylogeny, NP-hard problem, graph coloring, branching, acyclic digraph, chain partition, Dilworth's theorem, min-max theorem, approximation algorithm, heuristic
Objavljeno v RUP: 17.09.2018; Ogledov: 3507; Prenosov: 22
Povezava na celotno besedilo |
