Search

En aquest treball s'introdueixen les principals nocions de teoria de matroides, matroides transversals i extensions d'un sol element. El nostre primer objectiu és estudiar quines extensions d'una matroide transversal són també transversals. En particular, centrem el nostre estudi en la família de matroides uniformes. El conjunt d'extensions d'una matroide és un reticle sota l'anomenat weak order. Intentem respondre a la pregunta de si el conjunt d'extensions transversals d'una matroide uniforme és també un reticle o no. També dissenyem un algoritme per catalogar i contar matroides transversals fins a una certa mida del ground set. Per fer-ho, les construim a partir de la més petita, a base de iterativament extendre presentacions minimals, fent servir les eines que hem desenvolupat anteriorment. En vista que l'estratègia no troba realment totes les matroides transversals, també estudiem com són les matroides que no es poden construir amb aquesta estratègia i quines propietats satisfan. En este trabajo introducimos las nociones básicas de teoría de matroides, matroides transversales y extensiones de un solo elemento. Nuestro primer objetivo es estudiar las extensiones de matroides transversales que también son transversales. En particular, centramos nuestro estudio en la familia de las matroides uniformes. El conjunto de extensiones de una matroide es un retículo bajo el llamado weak order. Intentamos responder a la pregunta de si el conjunto de extensiones transversales de un matroide uniforme es también un retículo o no. También diseñamos un algoritmo que cataloga y cuenta matroides transversales hasta un tamaño fijo del ground set. Para ello, las construimos desde cero extendiendo iterativamente presentaciones minimales utilizando las herramientas que hemos visto anteriormente. Dado que la estrategia no cuenta realmente todas las matroides transversales, estudiamos también qué matroides no son alcanzables utilizando esta estrategia y qué propiedades satisfacen. In this work we introduce the basic notions of matroid theory, transversal matroids and single-element extensions. Our first objective is to study which extensions of a given transversal matroid are also transversal. In particular, we focus our study on the family of uniform matroids. The set of single-element extensions of a matroid is a lattice under the so-called weak order. We try to answer the question of whether the set of transversal extensions of a uniform matroid is also a lattice or not. We also design an algorithm that catalogs and counts transversal matroids up to a fixed size of the ground set. To do so, we build them from scratch by iteratively extending minimal presentations using the tools that we have previously seen. In view that the strategy does not actually count all transversal matroids, we also study which matroids are not reachable using this strategy and what properties do they satisfy.

Given a finite set of weighted points in $${\mathbb {R}}^d$$ R d (where there can be negative weights), the maximum box problem asks for an axis-aligned rectangle (i.e., box) such that the sum of the weights of the points that it contains is maximized. We consider that each point of the input has a probability of being present in the final random point set, and these events are mutually independent; then, the total weight of a maximum box is a random variable. We aim to compute both the probability that this variable is at least a given parameter, and its expectation. We show that even in $$d=1$$ d = 1 these computations are #P-hard, and give pseudo-polynomial time algorithms in the case where the weights are integers in a bounded interval. For $$d=2$$ d = 2 , we consider that each point is colored red or blue, where red points have weight $$+1$$ + 1 and blue points weight $$-\infty $$ - ∞ . The random variable is the maximum number of red points that can be covered with a box not containing any blue point. We prove that the above two computations are also #P-hard, and give a polynomial-time algorithm for computing the probability that there is a box containing exactly two red points, no blue point, and a given point of the plane.

A ( k , g ) -graph is a k -regular graph with girth g and a ( k , g ) -cage is a ( k , g ) -graph with the fewest possible number of vertices n ( k , g ) . Constructing ( k , g ) -cages and determining the order are both very hard problems. For this reason, an intensive line of research is devoted to constructing smaller ( k , g ) -graphs than previously known ones, providing in this way new upper bounds to n ( k , g ) each time such a graph is constructed. The paper focuses on girth g = 5 , where cages are known only for degrees k ≤ 7 . We construct ( k , 5 ) -graphs using and extending techniques of amalgamation into the incidence graphs of elliptic semiplanes of type L introduced and exposed by Funk (2009). The order of these graphs provides better upper bounds on n ( k , 5 ) than those known so far, for values of k such that either 13 ≤ k ≤ 33 or k ≥ 66 .

This version of the contribution has been accepted for publication, after peer review but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: http://dx.doi.org/10.1007/978-3-030-83823-2_11. Use of this Accepted Version is subject to the publisher's Accepted Manuscript terms of use http://www.spingernature.com/gp/open-research/policies/accepted-manuscript-terms. We study the Laplacian spectrum of token graphs, also called symmetric powers of graphs. The k-token graph Fk(G) of a graph G is the graph whose vertices are the k-subsets of vertices from G, two of which being adjacent whenever their symmetric difference is a pair of adjacent vertices in G. In this work, we give a relationship between the Laplacian spectra of any two token graphs of a given graph. In particular, we show that, for any integers h and k such that 1=h=k=n2 , the Laplacian spectrum of Fh(G) is contained in the Laplacian spectrum of Fk(G) . Besides, we obtain a relationship between the spectra of the k-token graph of G and the k-token graph of its complement G¯¯¯¯ . This generalizes a well-known property for Laplacian eigenvalues of graphs to token graphs. The research of C. Dalf´o and M. A. Fiol has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. The research of C. Dalf´o has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. The research of C. Huemer was supported by PID2019-104129GBI00/ AEI/ 10.13039/501100011033 and Gen. Cat. DGR 2017SGR1336. F. J. Zaragoza Mart´ınez acknowledges the support of the National Council of Science and Technology (Conacyt) and its National System of Researchers (SNI). This work has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No 734922.

The main objective of this bachelor's thesis will be to present the concept of quasirandomness in various mathematical contexts while proving all the pertinent results. We will introduce the results of Fan Chung and Ronald Graham on quasirandom graphs and quasirandom sets, and the results of Timothy Gowers on quasirandom groups. To further display the connection between randomness and structuredness, we will also present some other influential results on the subject, i. e. Roth's Theorem on arithmetical progression on subsets of Zn, Erdős' Theorem on sum-free sets of integers, and the Alon-Boppana Bound for the spectral expansion of a graph.

A family A of k-subsets of { 1 , 2 , … , N } is a Sidon system if the sumsets A + A ′ , A , A ′ ∈ A are pairwise distinct. We show that the largest cardinality F k ( N ) of a Sidon system of k-subsets of [ N ] satisfies F k ( N ) ≤ ( N − 1 k − 1 ) + N − k and the asymptotic lower bound F k ( N ) = Ω k ( N k − 1 ) . More precise bounds on F k ( N ) are obtained for k ≤ 3 . We also obtain the threshold probability for a random system to be Sidon for k = 2 and 3.

It is well known that, in general, part of the spectrum of a graph can be obtained from the adjacency matrix of its quotient graph given by a regular partition. In this paper, a method that gives all the spectrum, and also the local spectra, of a graph from the quotient matrices of some of its regular partitions, is proposed. Moreover, from such partitions, the C -local multiplicities of any class of vertices C is also determined, and some applications of these parameters in the characterization of completely regular codes and their inner distributions are described. As examples, it is shown how to find the eigenvalues and (local) multiplicities of walk-regular, distance-regular, and distance-biregular graphs. Received by the editors on February 20, 2020. Accepted for publication on May 27, 2020. Handling Editor: Sebastian M.Cioaba. Corresponding Author: Cristina Dalf ́o.†Departament de Matem`atica, Universitat de Lleida, Igualada (Barcelona), Catalonia (cristina.dalfo@udl.cat). Partiallysupported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Governmentunder projects PGC2018-095471-B-I00 and MTM2017-83271-R. Also received funding from the European Union’s Horizon 2020research and innovation programme under the Marie Sk lodowska-Curie grant agreement no. 734922.‡Departament de Matem`atiques, Barcelona Graduate School of Mathematics, Universitat Polit`ecnica de Catalunya,Barcelona, Catalonia, (miguel.angel.fiol@upc.edu). Partially supported by AGAUR from the Catalan Government under project2017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00.

Matroids arise from the abstract notion of dependency. Matroids can be studied from different points of view. From linear algebra we know matrices, which can be seen as matroids, however matroids generalise the concept of dependency. In matroids there also is combinatorics, graph theory and geometry. This project wants to be an introduction to matroids throughout two its families: positroids and lattice path matroids. Starting with basic definitions and examples the project reaches deeper and more interesting relations between these two families.

La resolución de problemas y las tareas ricas nos brindan una magnífica oportunidad para la introducción y adquisición del lenguaje algebraico. En este trabajo presentamos una selección de actividades recogida en el blog Banco de recursos del FEM Matemàtiques, elaborado por las autoras de este artículo, que permiten a los alumnos trabajar el álgebra de una manera significativa a partir de la investigación de patrones. En los materiales recogidos se presentan propuestas para el trabajo de las actividades en el aula que incluyen producciones de alumnos.

This paper considers the multi-period service scheduling problem with an aperiodic service policy. In this problem, a set of customers who periodically require service over a finite time horizon is given. To satisfy the service demands, a set of operators is given, each with a fixed capacity in terms of the number of customers that can be served per period. With an aperiodic policy, customers may be served before the period were the service would be due. Two criteria are jointly considered in this problem: the total number of operators, and the total number of ahead-of-time periods. The task is to determine the service periods for each customer in such a way that the service requests of the customers are fulfilled and both criteria are minimized. A new integer programming formulation is proposed, which outperforms an existing formulation. Since the computational effort required to obtain solutions considerably increases with the size of the instances, we also present a reformulation suitable for column generation, which is then integrated within a branch-and-price algorithm. Computational experiments highlight the efficiency of this algorithm for the larger instances.

Inspired by prior results by Stanley and Leroux showing what information can be recovered from an isomorphism of incidence algebras, we investigate the very same idea applied to decomposition spaces. We review the work of Stanley and Leroux and provide sufficient background on the homotopy theory of groupoids to be able to define decomposition spaces, equivalences of them as linear functors and solve the isomorphism problem for both the groupoid-level coalgebra and for the numerical incidence algebra.

This paper focuses on the well-known problem due to Stanley of whether two non-isomorphic trees can have the same U -polynomial (or, equivalently, the same chromatic symmetric function). We consider the U k -polynomial, which is a restricted version of U -polynomial, and construct, for any given k , non-isomorphic trees with the same U k -polynomial. These trees are constructed by encoding solutions of the Prouhet–Tarry–Escott problem. As a consequence, we find a new class of trees that are distinguished by the U -polynomial up to isomorphism.

Background: Precision medicine is the Holy Grail of interventions that are tailored to a patient’s individual characteristics. However, conventional clinical trials are designed to find differences in averages, and interpreting these differences depends on untestable assumptions. Although only an ideal, a constant effect of treatment would facilitate individual management. A direct consequence of a constant effect is that the variance of the outcome measure would be the same in the treated and control arms. We reviewed the literature to explore the similarity of these variances as a foundation for examining whether and how often precision medicine is definitively required. Methods: We reviewed parallel clinical trials with numerical primary endpoints published in 2004, 2007, 2010 and 2013. We collected the baseline and final standard deviations of the main outcome measure. We assessed homoscedasticity by comparing the variance of the primary endpoint between arms through the outcome variance ratio (treated to control group). Results: The review provided 208 articles with enough information to conduct the analysis. One out of five studies (n = 40, 19.2%) had statistically different variances between groups, implying a non-constant-effect. The adjusted point estimate of the mean outcome variance ratio (treated to control group) is 0.89 (95% CI 0.81 to 0.97). Conclusions: The mean variance ratio is significantly lower than 1 and the lower variance was found more often in the intervention group than in the control group, suggesting it is more usual for treated patients to be stable. This observed reduction in variance might also imply that there could be a subgroup of less ill patients who derive no benefit from treatment. This would require further study as to whether the treatment effect outweighs the side effects as well as the economic costs. We have shown that there are ways to analyze the apparently unobservable constant effect.

© . This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/ In this paper we consider the concept of preintersection numbers of a graph. These numbers are determined by the spectrum of the adjacency matrix of the graph, and generalize the intersection numbers of a distance-regular graph. By using the preintersection numbers we give some new spectral and quasi-spectral characterizations of distance-regularity, in particular for graphs with large girth or large odd-girth. (C) 2016 Published by Elsevier Inc.

The final publication is available at Springer via http://dx.doi.org/10.1007/s10801-015-0654-6 Let Gamma be a distance-regular graph with diameter d and Kneser graph K = Gamma(d), the distance-d graph of Gamma. We say that Gamma is partially antipodal when K has fewer distinct eigenvalues than Gamma. In particular, this is the case of antipodal distance-regular graphs (K with only two distinct eigenvalues) and the so-called half-antipodal distance-regular graphs (K with only one negative eigenvalue). We provide a characterization of partially antipodal distance-regular graphs (among regular graphs with d + 1 distinct eigenvalues) in terms of the spectrum and the mean number of vertices at maximal distance d from every vertex. This can be seen as a more general version of the so-called spectral excess theorem, which allows us to characterize those distance-regular graphs which are half-antipodal, antipodal, bipartite, or with Kneser graph being strongly regular.

The goal of this work consists in a quantitative analysis and constitutive modelling of ageing processes associated to plaque formation in mice arteries. Reliable information on the characteristic evolution of pressure-stretch curves due to the ageing effects is extracted from previous inflation test experiments. Furthermore, characteristic age-dependent material parameters are identified on the basis of a continuum-mechanics-based parameter optimisation technique. The results indicate that the aorta-stiffness of the healthy control mice remains basically constant irrespective of the diet-time and age. In contrast, significant differences exist within the material response and in consequence within the material parameters between the ApoE(-/-) and the control mice as well as for the different locations over the aorta which is underlined by our experimental observations. With regard to the temporal evolution of the material parameters, we observe that the material parameters for the ApoE(-/-) mice aortas exhibit a saturation-type increase with respect to age.

The main objective of this thesis is to present and prove Plünnecke's Inequality, a theorem that gives bounds for sumsets in commutative groups. An introduction to the theory of set addition is presented. Three different proofs of Plünnecke's Inequality are presented, two of them relying strongly on graph theory, the third being more elementary. Some other tools and techniques are introduced to obtain generalizations of Plünnecke's Inequality. The most important are the Plünnecke-Ruzsa Inequality, that gives bounds to general sum-and-difference sets in commutative groups, and some generalizations to the non-commutative case, related to Tao's Theorem. Some other generalizations involve the sum of different sets. The results are used to prove an important structural result.

We introduce the concept of distance mean-regular graph, which can be seen as a generalization of both vertex-transitive and distance-regular graphs. Let $$\Gamma $$Γ be a graph with vertex set V, diameter D, adjacency matrix $$\varvec{A}$$A, and adjacency algebra $$\mathcal{A}$$A. Then, $$\Gamma $$Γ is distance mean-regular when, for a given $$u\in V$$uźV, the averages of the intersection numbers $$p_{ij}^h(u,v)=|\Gamma _i(u)\cap \Gamma _j(v)|$$pijh(u,v)=|Γi(u)źΓj(v)| (number of vertices at distance i from u and distance j from v) computed over all vertices v at a given distance $$h\in \{0,1,\ldots ,D\}$$hź{0,1,ź,D} from u, do not depend on u. In this work we study some properties and characterizations of these graphs. For instance, it is shown that a distance mean-regular graph is always distance degree-regular, and we give a condition for the converse to be also true. Some algebraic and spectral properties of distance mean-regular graphs are also investigated. We show that, for distance mean regular-graphs, the role of the distance matrices of distance-regular graphs is played for the so-called distance mean-regular matrices. These matrices are computed from a sequence of orthogonal polynomials evaluated at the adjacency matrix of $$\Gamma $$Γ and, hence, they generate a subalgebra of $$\mathcal{A}$$A. Some other algebras associated to distance mean-regular graphs are also characterized.

The Klein theorem asserts the existence of at least one solution of the Carlson problem when a related Littlewood–Richardson sequence exists. Then, we present an explicit construction of some matricial solutions.

Comunicació presentada a: CRYPTO 2013 The 33rd Annual Cryptology Conference, celebrada del 18 al 22 d'agost de 2013 a Santa Bàrbara, Califòrnia, Estats Units d'Amèrica. We put forward a new algebraic framework to generalize and analyze Di_e-Hellman like Decisional Assumptions which allows us to argue about security and applications by considering only algebraic properties. Our D`;k-MDDH assumption states that it is hard to decide whether a vector in G` is linearly dependent of the columns of some matrix in G`_k sampled according to distribution D`;k. It covers known assumptions such as DDH, 2-Lin (linear assumption), and k-Lin (the k-linear assumption). Using our algebraic viewpoint, we can relate the generic hardness of our assumptions in m-linear groups to the irreducibility of certain polynomials which describe the output of D`;k. We use the hardness results to _nd new distributions for which the D`;k-MDDH-Assumption holds generically in m-linear groups. In particular, our new assumption 2-SCasc is generically hard in bilinear groups and, compared to 2-Lin, has shorter description size, which is a relevant parameter for e_ciency in many applications. These results support using our new assumption as a natural replacement for the 2-Lin Assumption which was already used in a large number of applications. To illustrate the conceptual advantages of our algebraic framework, we construct several fundamental primitives based on any MDDH-Assumption. In particular, we can give many instantiations of a primitive in a compact way, including public-key encryption, hash-proof systems, pseudo-random functions, and Groth-Sahai NIZK and NIWI proofs. As an independent contribution we give more e_cient NIZK proofs for membership in a subgroup of G`, for validity of ciphertexts and for equality of plaintexts. The results imply very signi_cant e_ciency improvements for a large number of schemes, most notably Naor-Yung type of constructions. _ Funded by a Sofja Kovalevskaja Award of the Alexander von Humboldt Foundation and the German Federal Ministry for Education and Research. Partially supported by the Spanish Government through projects MTM2009-07694 and Consolider Ingenio 2010 CDS2007-00004 ARES.

A graph $\G$ with diameter $D$ and $d+1$ distinct eigenvalues is said to be {\it $(\ell,m)$-walk-regular}, for some integers $\ell\in[0,d]$ and $m\in[0,D]$, $\ell\ge m$, if the number of walks of length $i\in [0,\ell]$ between any pair of vertices at distance $j\in [0,m]$ depends only on the values of $i$ and $j$. In this paper we study some algebraic and combinatorial characterizations of $(\ell,m)$-walk-regularity based on the so-called predistance polynomials and the preintersection numbers.

An outindependent subgraph of a graph G, with respect to an independent vertex subset C¿¿V, is the subgraph GC induced by the vertices in V\¿C. We study the case when G is strongly regular, where the results of de Caen [1998, The spectra of complementary subgraphs in a strongly regular graph. European Journal of Combinatorics, 19 (5), 559–565.], allow us to derive the whole spectrum of GC . Moreover, when C attains the Hoffman–Lovász bound for the independence number, GC is a regular graph (in fact, distance-regular if G is a Moore graph). This article is mainly devoted to study the non-regular case. As a main result, we characterize the structure of GC when C is the neighborhood of either one vertex or one edge.

The Klein theorem asserts the existence of a solution of the Carlson problem when a related Littelewood-Richardson sequence exists. Here we present an explicit construction of these matricial solutions.

Given a vertex $u\inV$ of a graph $\Gamma=(V,E)$, the (local) proper polynomials constitute a sequence of orthogonal polynomials, constructed from the so-called $u$-local spectrum of $\Gamma$. These polynomials can be thought of as a generalization, for all graphs, of the distance polynomials for te distance-regular graphs. The (local) adjacency polynomials, which are basically sums of proper polynomials, were recently used to study a new concept of distance-regularity for non-regular graphs, and also to give bounds on some distance-related parameters such as the diameter. Here we develop the subject of these polynomials and gave a survey of some known results involving them. For instance, distance-regular graphs are characterized from their spectra and the number of vertices at ``extremal distance'' from each of their vertices. Afterwards, some new applications of both, the proper and adjacency polynomials, are derived, such as bounds for the radius of $\Gamma$ and the weight $k$-excess of a vertex. Given the integers $k,\mu\ge 0$, let $\Gamma_k^{\mu}(u)$ denote the set of vertices which are at distance at least $k$ from a vertex $u\in V$, and there exist exactly $\mu$ (shortest) $k$-paths from $u$ to each each of such vertices. As a main result, an upper bound for the cardinality of $\Gamma_k^{\mu}(u)$ is derived, showing that $|\Gamma_k^{\mu}(u)|$ decreases at least as $O(\mu^{-2})$, and the cases in which the bound is attained are characterized. When these results are particularized to regular graphs with four distinct eigenvalues, we reobtain a result of Van Dam about $3$-class association schemes, and prove some conjectures of Haemers and Van Dam about the number of vertices at distane three from every vertex of a regular graph with four distinct eigenvalues---setting $k=2$ and $\mu=0$---and, more generally, the number of non-adjacent vertices to every vertex $u\in V$, which have $\mu$ common neighbours with it.

This is an Accepted Manuscript of an article published by Taylor & Francis Group in Journal of Sustainable Tourism on 28 Feb 2018, available online at: https://www.tandfonline.com/doi/full/10.1080/09669582.2018.1433183." Many destinations are implementing various water management alternatives to diminish the environmental impacts of tourism and increase sustainability. These efforts toward sustainability can be understood as part of corporate social responsibility (CSR) strategies implemented by tourism destinations. This paper is focused on the tourism destination of the Costa Brava (Catalonia, Spain) and proposes a method for selecting a list of influential factors in water management for sustainable tourism destinations by considering stakeholder preferences for technical, economic, social, political, and environmental factors. A new qualitative Delphi technique is used to identify a set of qualitative and quantitative factors by surveying eight stakeholders (six water management experts and two hotel managers). In addition, the study presents the weight for each of the influential factors that decision-makers – water planners, policy-makers, tourism destination managers and hotel managers – can use in assessing water management alternatives. Although research to date has addressed many aspects of responsible tourism, there is little literature on the importance of water management in responsible strategies for tourism destinations. This paper contributes to a more efficient selection of CSR strategies in tourism destinations by proposing a new methodology for identifying key factors for assessing sustainable solutions for water problems.

Background There is a scarce number of studies on the cost of agitation and containment interventions and their results are still inconclusive. We aimed to calculate the economic consequences of agitation events in an in-patient psychiatric facility providing care for an urban catchment area. Methods A mixed approach combining secondary analysis of clinical databases, surveys and expert knowledge was used to model the 2013 direct costs of agitation and containment events for adult inpatients with mental disorders in an area of 640,572 adult inhabitants in South Barcelona (Spain). To calculate costs, a seven-step methodology with novel definition of agitation was used along with a staff survey, a database of containment events, and data on aggressive incidents. A micro-costing analysis of specific containment interventions was used to estimate both prevalence and direct costs from the healthcare provider perspective, by means of a mixed approach with a probabilistic model evaluated on real data. Due to the complex interaction of the multivariate covariances, a sensitivity analysis was conducted to have empirical bounds of variability. Results During 2013, 918 patients were admitted to the Acute Inpatient Unit. Of these, 52.8% were men, with a mean age of 44.6 years (SD = 15.5), 74.4% were compulsory admissions, 40.1% were diagnosed with schizophrenia or non-affective psychosis, with a mean length of stay of 24.6 days (SD = 16.9). The annual estimate of total agitation events was 508. The cost of containment interventions ranges from 282€ at the lowest level of agitation to 822€ when verbal containment plus seclusion and restraint have to be used. The annual total cost of agitation was 280,535€, representing 6.87% of the total costs of acute hospitalisation in the local area. Conclusions Agitation events are frequent and costly. Strategies to reduce their number and severity should be implemented to reduce costs to the Health System and alleviate patient suffering. Electronic supplementary material The online version of this article (doi:10.1186/s12888-017-1373-4) contains supplementary material, which is available to authorized users.

We derive some Moore-like bounds for multipartite digraphs, which extend those of bipartite digraphs, under the assumption that every vertex of a given partite set is adjacent to the same number $\delta$ of vertices in each of the other independent sets. We determine when a Moore multipartite digraph is weakly distance-regular. Within this framework, some necessary conditions for the existence of a Moore $r$-partite digraph with interpartite outdegree $\delta>1$ and diameter $k=2m$ are obtained. In the case $\delta=1$, which corresponds to almost Moore digraphs, a necessary condition in terms of the permutation cycle structure is derived. Additionally, we present some constructions of dense multipartite digraphs of diameter two that are vertex-transitive.

A matching M in an edge–colored (hyper)graph is rainbow if each pair of edges in M have distinct colors. We extend the result of Erdős and Spencer on the existence of rainbow perfect matchings in the complete bipartite graph K n , n to complete bipartite multigraphs, dense regular bipartite graphs and complete r-partite r-uniform hypergraphs. The proof of the results use the Lopsided version of the Local Lovasz Lemma.

Let $\Gamma$ be a regular (connected) graph with $n$ vertices and $d+1$ distinct eigenvalues. As a main result, it is shown that $\Gamma$ is an $r$-antipodal distance-regular graph if and only if the distance graph $\Gamma_d$ is constituted by disjoint coies of the complete graph $K_r$, with $r$ satisfying an expression in terms of $n$ and the distinct eigenvalues.

Given a simple connected graph $\Gamma$ and a subset of its vertices $C$, the pseudo-distance-regularity around $C$ generalizes, for not necessarily regular graphs, the notion of completely regular code. Up to now, most of the characterizations of pseudo-distance-regularity has been derived from a combinatorial definition. In this paper we propose an algebraic (Terwilliger-like) approach to this notion, showing its equivalence with the combinatorial one. This allows us to give new proofs of known results, and also to obtain new characterizations which do not depend on the so-called $C$-spectrum of $\Gamma$, but only on the positive eigenvector of its adjacency matrix. In the way, we also obtain some results relating the local spectra of a vertex set and its antipodal. As a consequence of our study, we obtain a new characterization of a completely regular code $C$, in terms of the number of walks in $\Gamma$ with an endvertex in $C$.