Combinatoria
Organizadores: Celina Miraglia Herrera de Figueiredo (celina@cos.ufrj.br), Flavia Bonomo (fbonomo@dc.uba.ar), Lucia Moura (lmoura@uottawa.ca)

Monday 13
15:00  15:45Complete colorings on circulant graphs and digraphs
Gabriela AraujoPardo (Universidad Nacional Autónoma de México, México)
A complete \(k\)vertexcoloring of a graph \(G\) is a vertexcoloring of \(G\) using \(k\) colors such that for every pair of colors there is at least two incident vertices in \(G\) colored with this pair of colors. The \emph{chromatic} \(\chi(G)\) and \emph{achromatic} \(\alpha(G)\) numbers of \(G\) are the smallest and the largest number of colors in a complete proper \(k\)vertexcoloring of \(G\), therefore \(\chi(G)\leq\alpha(G)\).
The dichromatic number and the diachromatic number, generalice the concepts of chromatic number and achromatic number. An acyclic \(k\)vertexcoloring of a digraph \(D\) is vertex coloring using \(k\) colors such that \(D\) has no monochromatic cycles and a \emph{complete} \(k\)vertexcoloring of a digraph \(D\) is a vertex coloring using \(k\) colors such that for every ordered pair \((i,j)\) of different colors, there is at least one arc \((u,v)\) such that \(u\) has color \(i\) and \(v\) has color \(j\). The dichromatic number \(dc(D)\) and diachromatic number \(dac(D)\) of \(D\) are the smallest and the largest number of colors in a complete proper \(k\)vertexcoloring of \(D\), therefore \(dc(D)\leq dac(D)\).
We determine the achromatic and diachromatic numbers of some specific circulant graphs and digraphs and give general bounds for these two parameters on these graphs and digraphs. Also, we determine the achromatic index for circulant graphs of order \(q^2+q+1\) using projective planes.
Joint work with: Juan José MontellanoBallesteros, Mika Olsen and Christian RubioMontiel.
15:45  16:30The status of the \((r, l)\) wellcovered graph sandwich problem
Sulamita Klein (Universidade Federal do Rio de Janeiro, Brasil)
An \((r, l)\)partition of a graph \(G\) is a partition of its vertex set into \(r\) independent sets and \(l\) cliques. A graph is \((r,l)\) if it admits an \((r, l)\)partition. A graph is wellcovered if every maximal independent set is also maximum. A graph is \((r,l)\)wellcovered if it is both \((r,l)\) and wellcovered. We have proved the full classification of the decision problem \((r,l)\)WellCovered Graph problem, where we are given a graph \(G\), and the question is whether \(G\) is an \((r, l)\)wellcovered graph. We have shown that this problem is polynomial only in the cases \((0, 1)\), \((0, 2)\), \((1, 0)\), \((1, 1)\), \((1, 2)\), and \((2, 0)\) and hard otherwise. The Sandwich Problem for the Property \(\pi\) has as an instance a pair of graphs \(G1 = (V, E_1)\) and \(G2 = (V, E_2)\) with \(E_1 \subset E_2\), plus the question whether there is a graph \(G=(V,E)\) with \(E_1 \subset E\subset E_2\), such that \(G\) has the property \(\pi\). When a recognition problem for a property \(\pi\) is hard, we can consider the sets \(E_1 = E_2\) to obtain that the sandwich problem for the property \(\pi\) reduces to the recognition and so also hard. Hence, the only cases where the \((r, l)\)wellcovered sandwich problem can be no longer hard are in the \(6\) polynomial cases. In this talk we prove that \((r, l)\)wellcovered sandwich problem is polynomial in the cases that \((r, l) = (0, 1), (1, 0), (1, 1)\) or \((0, 2)\), and NPcomplete if we consider the property of being \((1, 2)\)wellcovered.
This work was done with the collaboration of Sancrey Rodrigues Alves (FAETEC), Fernanda Couto (UFRRJ), Luerbio Faria (UERJ), Sylvain Gravier (CNRS), and Uéverton S. Souza (UFF).
16:45  17:30Perfect sequence covering arrays
Jonathan Jedwab (Simon Fraser University, Canada)
An \((n,k,\lambda)\) perfect sequence covering array is a subset of the \(n!\) permutations of the sequence \((1, 2, \dots, n)\) whose elements collectively contain each ordered \(k\)subsequence exactly \(\lambda\) times. The central question is: for given \(n\) and \(k\), what is the smallest value of \(\lambda\) (denoted \(g(n,k)\)) for which such a configuration exists? We interpret the sequences of a perfect sequence covering array as elements of the symmetric group \(S_n\), and constrain its structure to be a union of cosets of a prescribed subgroup of \(S_n\). By adapting a search algorithm due to Mathon and van Trung for finding spreads, we obtain highly structured examples of perfect sequence covering arrays. In particular, we determine that \(g(6,3) = g(7,3) = g(7,4) = 2\) and that \(g(8,3)\) is either 2 or 3.
This is joint work with Jingzhou Na.
17:30  18:15Active clustering
Maya Stein (Universidad de Chile, Chile)
Given a set (known to us), and a partition of this set, unknown to us, consider the following task. We have to determine the partition by making successive queries about pairs of elements, each time querying whether the pair belong to the same class or not. Later queries are allowed to depend on the outcome of earlier queries. There is a natural way to assign a graph to each step of the querying process, by starting with an edgeless graph where each vertex represents an element of the set, and after queries identifying vertices for a yesanswer and adding edges for noanswers. We prove the at first sight surprising result that the partitioning algorithms reaching the minimal average number of queries are exactly those that keep these graphs chordal. (The average is taken over all possible partitions of the base set.) The optimal algorithms even share the same distribution on the number of queries, which we characterize. We also analyse a related model where the number of partition classes is fixed, and each element of the base set chooses its partition class randomly.
This is joint work with Élie de Panafieu, Quentin Lutz and Alex Scott.

Tuesday 14
15:00  15:45Approximating graph eigenvalues using tree decompositions
Carlos Hoppen (Universidade Federal do Rio Grande do Sul, Brasil)
Spectral graph theory aims to extract structural information about graphs from spectra of different types of matrices associated with them, such as the adjacency matrix, Laplacian matrices, and many others. A basic step in any such application consists of computing or approximating the spectrum or some prescribed subset of eigenvalues. One strategy for this is to compute diagonal matrices that are congruent to the original matrices, which can be done quite efficiently if we have a graph decompositions such as the tree decomposition with bounded width. To be precise, let \(M=(m_{ij})\) be a symmetric matrix of order \(n\) whose elements lie in an arbitrary field \(\mathbb{F}\), and let \(G\) be the graph with vertex set \(\{1,\ldots,n\}\) such that distinct vertices \(i\) and \(j\) are adjacent if and only if \(m_{ij} \neq 0\). We present an algorithm that finds a diagonal matrix that is congruent to \(M\) in time \(O(k^2 n)\), provided that we are given a suitable tree decomposition of \(G\) with width \(k\). In addition to the above applications, this allows one to compute the determinant and to find the rank of a symmetric matrix in time \(O(k^2 n)\).
This is joint work with M. FŸrer (Pennsylvannia State University) and Vilmar Trevisan (Universidade Federal do Rio Grande do Sul).
15:45  16:30Circularly compatible ones, \(D\)circularity, and proper circulararc bigraphs
Martín Safe, (Universidad Nacional del Sur, Argentina)
In 1969, Tucker characterized proper circulararc graphs as those graphs whose augmented adjacency matrices have the circularly compatible ones property. Moreover, he also found a polynomialtime algorithm for deciding whether any given augmented adjacency matrix has the circularly compatible ones property. These results led to the first polynomialtime recognition algorithm for proper circulararc graphs. However, as remarked there, this work did not solve the problems of finding a structure theorem and an efficient recognition algorithm for the circularly compatible ones property in arbitrary matrices (i.e., not restricted to augmented adjacency matrices only). We solve these problems. More precisely, we give a minimal forbidden submatrix characterization for the circularly compatible ones property in arbitrary matrices and a lineartime recognition algorithm for the same property. We derive these results from analogous ones for the related \(D\)circular property. Interestingly, these results lead to a minimal forbidden induced subgraph characterization and a lineartime recognition algorithm for proper circulararc bigraphs, solving a problem first posed by Basu et al. [J. Graph Theory, 73 (2013), pp. 361376]. Our findings generalize some known results about \(D\)interval hypergraphs and proper interval bigraphs.
16:45  17:30Fault tolerance in cryptography using coverfree families
Thais Bardini Idalino (Universidade Federal de Santa Catarina, Brasil)
Coverfree families (CFFs) have been investigated under different names and as a solution to many problems related to combinatorial group testing. A \(d\)coverfree family \(d\)CFF\((t, n)\) is a set system with n subsets of a \(t\)set, where the union of any d subsets does not contain any other. A \(d\)CFF\((t, n)\) allows for the identification of up to \(d\) defective elements in a set of \(n\) elements by performing only \(t\) tests (typically \(t \ll n\)).
We explore different aspects of coverfree families in order to achieve fault tolerance in cryptography. For instance, while CFFs are used as a solution to many problems in this area, we note that some of those problems require CFFs with increasing \(n\). In this context, we investigate new infinite families and their constructions in order to better approach fault tolerance in cryptography. This is joint work with Lucia Moura.
[1] IDALINO, T. B.; MOURA, L., Nested coverfree families for unbounded faulttolerant aggregate signatures. Theoretical Computer Science, 854 (2021), 116130.
[2] IDALINO, T. B.; MOURA, L., Embedding coverfree families and cryptographical applications. Advances in Mathematics of Communications, 13 (2019), 629643.17:30  18:15Counting Segment, Rays, Lines in Quasimetric spaces
Martín Matamala (Universidad de Chile, Chile)
In the Euclidean plane, it is a wellknown result that a set of n points defines exactly \(n(n1)/2\) distinct segments, at least \(2(n1)1\) different rays and, when the points are not collinear, at least \(n\) different lines. Segments, rays and lines can be define in any quasimetric space by using its quasimetric. In this talk we survey recent results concerning the generalization of the above mentioned properties of the Euclidean plane, specially those of lines, to finite quasimetric spaces, mainly those defined by connected graphs and strongly connected digraphs.

Friday 17
15:00  15:45Fault Localization via Combinatorial Testing
Charles J. Colbourn (Arizona State University, Estados Unidos)
In this talk, we explore combinatorial arrays that are useful in identifying faulty interactions in complex engineered systems. A separating hash family \({\sf SHF}_\lambda(N; k,v,\{w_1,\dots,w_s\})\) is an \(N \times k\) array on \(v\) symbols, with the property that no matter how disjoint sets \(C_1, \dots, C_s\) of columns with \(C_i = w_i\) are chosen, there are at least \(\lambda\) rows in which, for every \(1 \leq i < j \leq s\), no entry in a column of \(C_i\) equals that in a column of \(C_j\). (That is, there are \(\lambda\) rows in which sets \(\{C_1,\dots,C_s\}\) are separated) Separating hash families have numerous applications in combinatorial cryptography and in the construction of various combinatorial arrays; typically, one only considers whether two symbols are the same or different. We instead employ symbols that have algebraic significance.
We consider an \({\sf SHF}_\lambda(N; k,q^s,\{w_1,\dots,w_s\})\) whose symbols are column vectors from \({\mathbb F}_q^s\). The entry in row \(r\) and column \(c\) of the \({\sf SHF}\) is denoted by \({\bf v}_{r,c}\). Suppose that \(C_1, \dots, C_s\) is a set of disjoint sets of columns. Row \(r\) is covering for \(\{C_1, \dots, C_s\}\) if, whenever we choose \(s\) columns \(\{ \gamma_i \in C_i : 1 \leq i \leq s\}\), the \(s \times s\) matrix \([ {\bf v}_{r,\gamma_1} \cdots {\bf v}_{r,\gamma_s} ]\) is nonsingular over \({\mathbb F}_q\). Then the \({\sf SHF}_\lambda(N; k,q^s,\{w_1,\dots,w_s\})\) is covering if, for every way to choose \(\{C_1, \dots, C_s\}\), there are at least \(\lambda\) covering rows.
We establish that covering separating hash families of type \(1^t d^1\) give an effective construction for detecting arrays, which are useful in screening complex systems to find interactions among \(t\) or fewer factors without being masked by \(d\) or fewer other interactions. This connection easily accommodates outlier and missing responses in the screening. We explore asymptotic existence results and explicit constructions using finite geometries for covering separating hash families. We develop randomized and derandomized construction algorithms and discuss consequences for detecting arrays. This is joint work with Violet R. Syrotiuk (ASU).
15:45  16:30Uniformly OptimallyReliable Graphs
Franco Robledo (Universidad de la Republica, Uruguay)
The reliability polynomial of a simple graph G represents the probability that G will remain connected given a fixed probability \(1p\) of each edge failing. A graph \(G\) is uniformly most reliable if its reliability polynomial is greater than or equal to the reliability polynomial of all other graphs with the same number of nodes and edges for all \(p \in [0, 1]\).
Which is the mostreliable graph with n nodes and m edges?
This problem has several variants, according to the notion of optimality (in a local or uniform sense), failure type (either nodes or edges), or reliability model (allterminal connectedness, sourceterminal or general multiterminal setting).
This presentation shows a summary of the multiple proposals to attack the problem, together with recent trends and important conjectures proposed decades ago which require further research.
Particularly, we will present recently proved conjectures regarding UMGR (Uniformly MostReliable Graphs) as well as new evaluation techniques for this property.
Keywords: uniformly mostreliable graph, uniformly leastreliable graph, allterminal reliability, sourceterminal reliability, failuretype, graph theory.
16:45  17:30On the \(\Delta\)interval and \(\Delta\)convexity numbers of graphs and graph products
Mitre Dourado (Universidade Federal do Rio de Janeiro, Brasil)
Given a graph \(G\) and a set \(S \subseteq V(G)\), the \(\Delta\)interval of \(S\), \([S]_{\Delta}\), is the set formed by the vertices of \(S\) and every \(w \in V(G)\) forming a triangle with two vertices of \(S\). If \([S]_\Delta = S\), then \(S\) is \(\Delta\)convex of \(G\); if \([S]_{\Delta} = V(G)\), then \(S\) is a \(\Delta\)interval set of \(G\). The \(\Delta\)interval number of \(G\) is the minimum cardinality of a \(\Delta\)interval set and the \(\Delta\)convexity number of \(G\) is the maximum cardinality of a proper \(\Delta\)convex subset of \(V(G)\). In this work, we show that the problem of computing the \(\Delta\)convexity number is {\sf W}[1]hard and {\sf NP}hard to approximate within a factor \(O(n^{1\varepsilon})\) for any constant \(\varepsilon > 0\) even for graphs with diameter \(2\) and that the problem of computing the \(\Delta\)interval number is {\sf NP}complete for general graphs. For the positive side, we present characterizations that lead to polynomialtime algorithms for computing the \(\Delta\)convexity number of chordal graphs and for computing the \(\Delta\)interval number of block graphs. We also present results on the \(\Delta\)hull, \(\Delta\)interval and \(\Delta\)convexity numbers concerning the three standard graph products, namely, the Cartesian, strong and lexicographic products, in function of these and wellstudied parameters of the operands.
Joint work with: Bijo S. Anand, Prasanth G. NarasimhaShenoi, and Sabeer S. Ramla.
17:30  18:15Unavoidable patterns
Adriana Hansberg (Universidad Nacional Autónoma de México, México)
Ramsey's theorem states that, for any integer \(t\), if \(n\) is a sufficiently large integer, then every \(2\)edgecoloring of a complete graph \(K_n\) contains a monochromatic \(K_t\). On the other hand, Turán's theorem says that, if a graph has sufficiently many edges, then it contains a \(K_t\) as a subgraph. In relation to these two types of problems, we study which \(2\)colored patterns are forced to appear in differently saturated \(2\)edgecolorings of the complete graph \(K_n\) provided \(n\) is large enough. This is a joint work with Yair Caro and Amanda Montejano.