An n × n partial Latin square P is called α-dense if each row and column has at most αn non-empty cells and each symbol occurs at most αn times in P. An n × n array A where each cell contains a subset of {1,…, n} is a (βn, βn, βn)-array if each symbol occurs at most βn times in each row and column and each cell contains a set of size at most βn. Combining the notions of completing partial Latin squares and avoiding arrays, we prove that there are constants α, β > 0 such that, for every positive integer n, if P is an α-dense n × n partial Latin square, A is an n × n (βn, βn, βn)-array, and no cell of P contains a symbol that appears in the corresponding cell of A, then there is a completion of P that avoids A; that is, there is a Latin square L that agrees with P on every non-empty cell of P, and, for each i, j satisfying 1 ≤ i, j ≤ n, the symbol in position (i, j) in L does not appear in the corresponding cell of A.

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.

Casselgren, Carl Johan

Öhman, Lars-Daniel

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.

Avoiding Arrays of Odd Order by Latin Squares2013In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 22, no 2, p. 184-212Article in journal (Refereed)

Abstract [en]

We prove that there is a constant c such that, for each positive integer k, every (2k + 1) x (2k + 1) array A on the symbols 1, ... , 2k + 1 with at most c(2k + 1) symbols in every cell, and each symbol repeated at most c(2k + 1) times in every row and column is avoidable; that is, there is a (2k + 1) x (2k + 1) Latin square S on the symbols 1, ... , 2k + 1 such that, for each i, j is an element of {1, ... , 2k + 1}, the symbol in position (i, j) of S does not appear in the corresponding cell in Lambda. This settles the last open case of a conjecture by Haggkvist. Using this result, we also show that there is a constant rho, such that, for any positive integer n, if each cell in an n x n array B is assigned a set of m <= rho n symbols, where each set is chosen independently and uniformly at random from {1, ... , n}, then the probability that B is avoidable tends to 1 as n -> infinity.

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.

Sperner's Problem for G-Independent Families2015In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 24, no 3, p. 528-550Article in journal (Refereed)

Abstract [en]

Given a graph G, let Q(G) denote the collection of all independent (edge-free) sets of vertices in G. We consider the problem of determining the size of a largest antichain in Q(G). When G is the edgeless graph, this problem is resolved by Sperner's theorem. In this paper, we focus on the case where G is the path of length n - 1, proving that the size of a maximal antichain is of the same order as the size of a largest layer of Q(G).

In this paper, we prove several new Turan density results for 3-graphs with independent neighbourhoods. We show: pi(K-4, C-5, F-3,F-2) = 12/49, pi(K-4, F-3,F-2) = 5/18 and pi(J(4), F-3,F-2) = pi(J(5), F-3,F-2) = 3/8, where J(t) is the 3-graph consisting of a single vertex x together with a disjoint set A of size t and all (vertical bar A vertical bar 2) 3-edges containing x. We also prove two Turan density results where we forbid certain induced subgraphs: pi(F-3,F-2, induced K-4(-)) = 3/8 and pi(K-5, 5-set spanning exactly 8 edges) = 3/4. The latter result is an analogue for K-5 of Razborov's result that pi(K-4, 4-set spanning exactly 1 edge) = 5/9. We give several new constructions, conjectures and bounds for Turan densities of 3-graphs which should be of interest to researchers in the area. Our main tool is 'Flagmatic', an implementation of Razborov's semi-definite method, which we are making publicly available. In a bid to make the power of Razborov's method more widely accessible, we have tried to make Flagmatic as user-friendly as possible, hoping to remove thereby the major hurdle that needs to be cleared before using the semi-definite method. Finally, we spend some time reflecting on the limitations of our approach, and in particular on which problems we may be unable to solve. Our discussion of the 'complexity barrier' for the semi-definite method may be of general interest.

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.

Johansson, Anders

Orthogonal latin rectangles2008In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 17, no 4, p. 519-536Article in journal (Refereed)

Abstract [en]

We use a greedy probabilistic method to prove that, for every epsilon > 0, every m x n Latin rectangle on n symbols has an orthogonal mate, where m = (1 - epsilon)n. That is, we show the existence of a second Latin rectangle such that no pair of the mn cells receives the same pair of symbols in the two rectangles.

The discrete cube {0, 1}d is a fundamental combinatorial structure. A subcube of {0, 1}d is a subset of 2k of its points formed by fixing k coordinates and allowing the remaining d - k to vary freely. This paper is concerned with patterns of intersections among subcubes of the discrete cube. Two sample questions along these lines are as follows: given a family of subcubes in which no r + 1 of them have non-empty intersection, how many pairwise intersections can we have? How many subcubes can we have if among them there are no k which have non-empty intersection and no l which are pairwise disjoint? These questions are naturally expressed using intersection graphs. The intersection graph of a family of sets has one vertex for each set in the family with two vertices being adjacent if the corresponding subsets intersect. Let I(n, d) be the set of all n vertex graphs which can be represented as the intersection graphs of subcubes in {0, 1}d. With this notation our first question above asks for the largest number of edges in a Kr+1-free graph in I(n, d). As such it is a Turán-type problem. We answer this question asymptotically for some ranges of r and d. More precisely we show that if (k + 1)2 [d/k+1] < n ≥k2[d/k] for some integer k ≥ 2 then the maximum edge density is (1 - 1/k - o(1)) provided that n is not too close to the lower limit of the range. The second question can be thought of as a Ramsey-type problem. The maximum such n can be defined in the same way as the usual Ramsey number but only considering graphs which are in I(n, d). We give bounds for this maximum n mainly concentrating on the case that l is fixed, and make some comparisons with the usual Ramsey number.

A perfect Kt-matching in a graph G is a spanning subgraph consisting of vertex-disjoint copies of Kt A classic theorem of Hajnal and Szemerédi states that if G is a graph of order n with minimum degree δ(G) ≥(t - 1)n/t and t|n, then G contains a perfect Kt-matching. Let G be a t-partite graph with vertex classes V1, . . . , Vt each of size n. We show that, for any γ > 0, if every vertex x ∈ Vi is joined to at least ((t - 1)/t + γ )n vertices of Vj for each j ≠ i, then G contains a perfect Kt-matching, provided n is large enough. Thus, we verify a conjecture of Fischer [6] asymptotically. Furthermore, we consider a generalization to hypergraphs in terms of the codegree.