Search

Abstract In this paper, we generalize classical constructions of skew Hadamard difference families with two or four blocks in the additive groups of finite fields given by Szekeres (1969, 1971), Whiteman (1971) and Wallis–Whiteman (1972). In particular, we show that there exists a skew Hadamard difference family with 2 u − 1 blocks in the additive group of the finite field of order q e for any prime power q ≡ 2 u + 1 (mod 2 u + 1) with u ⩾ 2 and any positive integer e. In the aforementioned papers of Szekeres, Whiteman, and Wallis–Whiteman, the constructions of skew Hadamard difference families with 2 u − 1 (u = 2 or 3) blocks in (F q e , +) work only for restricted e ;namely e ≡ 1 , 2 , or 3 (mod 4) when u = 2 , and e ≡ 1 (mod 2) when u = 3 , respectively. Our more general construction, in particular, removes the restrictions on e. As a consequence, we obtain new infinite series of skew Hadamard difference families with two or four blocks, and hence skew Hadamard matrices. [ABSTRACT FROM AUTHOR]

Abstract In this paper, we study the following classical question of extremal set theory: what is the maximum size of a family of subsets of [ n ] such that no s sets from the family are pairwise disjoint? This problem was first posed by Erdős and resolved for n ≡ 0 , − 1 (mod s) by Kleitman in the 60s. Very little progress was made on the problem until recently. The only result was a very lengthy resolution of the case s = 3 , n ≡ 1 (mod 3) by Quinn, which was written in his PhD thesis and never published in a refereed journal. In this paper, we give another, much shorter proof of Quinn's result, as well as resolve the case s = 4 , n ≡ 2 (mod 4). This complements the results in our recent paper, where, in particular, we answered the question in the case n ≡ − 2 (mod s) for s ≥ 5. [ABSTRACT FROM AUTHOR]

This paper studies systems of polynomial equations that provide information about orientability of matroids. First, we study systems of linear equations over F 2 , originally alluded to by Bland and Jensen in their seminal paper on weak orientability. The Bland–Jensen linear equations for a matroid M have a solution if and only if M is weakly orientable. We use the Bland–Jensen system to determine weak orientability for all matroids on at most nine elements and all matroids between ten and twelve elements having rank three. Our experiments indicate that for small rank, about half the time, when a simple matroid is not orientable, it is already non-weakly orientable, and further this may happen more often as the rank increases. Thus, about half of the small simple non-orientable matroids of rank three are not representable over fields having order congruent to three modulo four. For binary matroids, the Bland–Jensen linear systems provide a practical way to check orientability. Second, we present two extensions of the Bland–Jensen equations to slightly larger systems of non-linear polynomial equations. Our systems of polynomial equations have a solution if and only if the associated matroid M is orientable. The systems come in two versions, one directly extending the Bland–Jensen system for F 2 , and a different system working over other fields. We study some basic algebraic properties of these systems. Finally, we present an infinite family of non-weakly-orientable matroids, with growing rank and co-rank. We conjecture that these matroids are minor-minimal non-weakly-orientable matroids. [ABSTRACT FROM AUTHOR]

The subjects of rook equivalence and Wilf equivalence have both attracted considerable attention over the last half-century. In this paper we introduce a new notion of Wilf equivalence for integer partitions, and, using this notion, we prove that rook equivalence implies Wilf equivalence. We also prove that if we refine the notions of rook and Wilf equivalence in a natural way, then these two notions coincide. In Bloom and Saracino (2017) we prove that Wilf equivalence implies rook equivalence. [ABSTRACT FROM AUTHOR]

A Dyck path of length 2 k with e flaws is a path in the integer lattice that starts at the origin and consists of k many ↗ -steps and k many ↘ -steps that change the current coordinate by ( 1 , 1 ) or ( 1 , − 1 ) , respectively, and that has exactly e many ↘ -steps below the line y = 0 . Denoting by D 2 k e the set of Dyck paths of length 2 k with e flaws, the well-known Chung–Feller theorem asserts that the sets D 2 k 0 , D 2 k 1 , … , D 2 k k all have the same cardinality 1 k + 1 2 k k = C k , the k th Catalan number. The standard combinatorial proof of this classical result establishes a bijection f ′ between D 2 k e and D 2 k e + 1 that swaps certain parts of the given Dyck path x , with the effect that x and f ′ ( x ) may differ in many positions. In this paper we strengthen the Chung–Feller theorem by presenting a simple bijection f between D 2 k e and D 2 k e + 1 which has the additional feature that x and f ( x ) differ in only two positions (the least possible number). We also present an algorithm that allows to compute a sequence of applications of f in constant time per generated Dyck path. As an application, we use our minimum-change bijection f to construct cycle-factors in the odd graph O 2 k + 1 and the middle levels graph M 2 k + 1 – two intensively studied families of vertex-transitive graphs – that consist of C k many cycles of the same length. [ABSTRACT FROM AUTHOR]

The paper designs five graph operations, and proves that every signed graph with chromatic number q , defined by Kang and Steffen (in press), can be obtained from copies of the all-positive complete graph ( K q , + ) by repeatedly applying these operations. This result gives a signed version of the Hajós theorem, emphasizing the role of all-positive complete graphs in the class of signed graphs, as in the class of unsigned graphs. Moreover, a similar result is established for the signed chromatic number defined by Máčajová, Raspaud and Škoviera. [ABSTRACT FROM AUTHOR]

The main result of this paper is to show that all binomial identities are orderable. This is a natural statement in the combinatorial theory of finite sets, which can also be applied in distributed computing to derive new strong bounds on the round complexity of the weak symmetry breaking task. Furthermore, we introduce the notion of a fundamental binomial identity and find an infinite family of values, other than the prime powers, for which no fundamental binomial identity can exist. [ABSTRACT FROM AUTHOR]

The first part of this paper deals with the combinatorics of equivariant partitions of finite sets with group actions. In the second part, we compute all equivariant Euler characteristics of the Σ n -poset of non-extreme partitions of an n -set. [ABSTRACT FROM AUTHOR]

The Raney numbers R p , r ( k ) are a two-parameter generalization of the Catalan numbers. In this paper, we give a combinatorial proof for a recurrence relation of the Raney numbers in terms of coral diagrams. Using this recurrence relation, we confirm a conjecture posed by Amdeberhan concerning the enumeration of ( s , s + 1 ) -core partitions λ with parts that are multiples of p . As a corollary, we give a new combinatorial interpretation for the Raney numbers R p + 1 , r + 1 ( k ) with 0 ≤ r < p in terms of ( k p + r , k p + r + 1 ) -core partitions λ with parts that are multiples of p . [ABSTRACT FROM AUTHOR]

In this paper, we study toric ideals associated with multichains of posets. It is shown that the comparability graph of a poset is chordal if and only if there exists a quadratic Gröbner basis of the toric ideal of the poset. Strong perfect elimination orderings of strongly chordal graphs play an important role. [ABSTRACT FROM AUTHOR]

An integer sequence is said to be 3-free if no three elements form an arithmetic progression. A Stanley sequence { a n } is a 3-free sequence constructed by the greedy algorithm. Namely, given initial terms a 0 < a 1 < ⋯ < a k , each subsequent term a n > a n − 1 is chosen to be the smallest such that the 3-free condition is not violated. Odlyzko and Stanley conjectured that Stanley sequences divide into two classes based on asymptotic growth: Type 1 sequences satisfy a n = Θ ( n log 2 3 ) and appear well-structured, while Type 2 sequences satisfy a n = Θ ( n 2 / log n ) and appear disorderly. In this paper, we define the notion of regularity , which is based on local structure and implies Type 1 asymptotic growth. We conjecture that the reverse implication holds. We construct many classes of regular Stanley sequences, which include all known Type 1 sequences as special cases. We show how two regular sequences may be combined into another regular sequence, and how parts of a Stanley sequence may be translated while preserving regularity. Finally, we demonstrate the surprising fact that certain Stanley sequences possess proper subsets that are also Stanley sequences. [ABSTRACT FROM AUTHOR]

In 2015, Bau and Dankelmann showed that every bridgeless graph G of order n and minimum degree δ has an orientation of diameter at most 11 n δ + 1 + 9 . As they were convinced that this bound is not best possible, they posed the problem of improving it. In this paper, we prove that such a graph G has an orientation of diameter less than 7 n δ + 1 and give a polynomial-time algorithm to construct one. [ABSTRACT FROM AUTHOR]

Abstract The bunkbed conjecture was first posed by Kasteleyn. If G = (V , E) is a finite graph and H some subset of V , then the bunkbed of the pair (G , H) is the graph G × { 1 , 2 } plus | H | extra edges to connect for every v ∈ H the vertices (v , 1) and (v , 2). The conjecture asserts that (v , 1) is more likely to connect with (w , 1) than with (w , 2) in the independent bond percolation model for any v , w ∈ V. This is intuitive because (v , 1) is in some sense closer to (w , 1) than it is to (w , 2). The conjecture has however resisted several attempts of proof. This paper settles the conjecture in the case of a constant percolation parameter and G the complete graph. [ABSTRACT FROM AUTHOR]

The d -defective k -painting game on a graph G is played by two players: Lister and Painter. Initially, each vertex has k tokens and is uncoloured. In each round, Lister chooses a set M of uncoloured vertices and removes one token from each chosen vertex. Painter colours a subset X of M which induces a subgraph G [ X ] of maximum degree at most d . Lister wins the game if at the end of some round, a vertex v has no more tokens left, and is uncoloured. Otherwise, at some round, all vertices are coloured and Painter wins. We say G is d -defective k -paintable if Painter has a winning strategy in this game. This paper proves that for each surface S , there is a constant w such that graphs embedded in S with edge-width at least w are 2 -defective 4 -paintable. [ABSTRACT FROM AUTHOR]

An edge-colored graph H is called rainbow if e ( H ) = c ( H ) , where e ( H ) and c ( H ) are the number of edges of H and colors used in H , respectively. For two graphs G and H , the rainbow number r b ( G , H ) is the minimum number of colors k such that for every edge-coloring of G using k colors, G contains a rainbow H . In this paper we prove that for an edge-colored graph G on n vertices with n ≥ k ≥ 4 , if e ( G ) + c ( G ) ≥ ( n 2 ) + t n , k − 2 + 2 , then G contains a rainbow clique K k , where t n , k − 2 is the Turán number. This implies the known result r b ( K n , K k ) = t n , k − 2 + 2 , and moreover, r b ( G , K k ) ≤ e ( G ¯ ) + r b ( K n , K k ) for n ≥ k ≥ 4 . [ABSTRACT FROM AUTHOR]

A half-arc-transitive graph is a regular graph that is both vertex- and edge-transitive, but is not arc-transitive. If such a graph has finite valency, then its valency is even, and greater than 2 . In 1970, Bouwer proved that there exists a half-arc-transitive graph of every even valency greater than 2, by giving a construction for a family of graphs now known as B ( k , m , n ) , defined for every triple ( k , m , n ) of integers greater than 1 with 2 m ≡ 1 mod n . In each case, B ( k , m , n ) is a 2 k -valent vertex- and edge-transitive graph of order m n k − 1 , and Bouwer showed that B ( k , 6 , 9 ) is half-arc-transitive for all k > 1 . For almost 45 years the question of exactly which of Bouwer’s graphs are half-arc-transitive and which are arc-transitive has remained open, despite many attempts to answer it. In this paper, we use a cycle-counting argument to prove that almost all of the graphs constructed by Bouwer are half-arc-transitive. In fact, we prove that B ( k , m , n ) is arc-transitive only when n = 3 , or ( k , n ) = ( 2 , 5 ) , or ( k , m , n ) = ( 2 , 3 , 7 ) or ( 2 , 6 , 7 ) or ( 2 , 6 , 21 ) . In particular, B ( k , m , n ) is half-arc-transitive whenever m > 6 and n > 5 . This gives an easy way to prove that there are infinitely many half-arc-transitive graphs of each even valency 2 k > 2 . [ABSTRACT FROM AUTHOR]

Let N 0 be the set of all nonnegative integers and ℓ ≥ 2 be a fixed integer. For A ⊆ N 0 and n ∈ N 0 , let r ℓ ′ ( A , n ) denote the number of solutions of a 1 + ⋯ + a ℓ = n with a 1 , … , a ℓ ∈ A and a 1 ≤ ⋯ ≤ a ℓ . Let k be a fixed positive integer. In this paper, we prove that, for any given distinct positive integers u i ( 1 ≤ i ≤ k ) and positive rational numbers α i ( 1 ≤ i ≤ k ) with α 1 + ⋯ + α k = 1 , there are infinitely many sets A ⊆ N 0 such that r ℓ ′ ( A , n ) ≥ 1 for all n ≥ 0 and the set of n with r ℓ ′ ( A , n ) = u i has density α i for all 1 ≤ i ≤ k . [ABSTRACT FROM AUTHOR]

Skolem and Langford sequences and their many generalizations have applications in numerous areas. The ⊗ h -product is a generalization of the direct product of digraphs. In this paper we use the ⊗ h -product and super edge-magic digraphs to construct an exponential number of Langford sequences with certain order and defect. We also apply this procedure to extended Skolem sequences. [ABSTRACT FROM AUTHOR]

This paper studies the choosability of signed planar graphs. We prove that every signed planar graph is 5-choosable and that there is a signed planar graph which is not 4-choosable while the unsigned graph is 4-choosable. For each k ∈ { 3 , 4 , 5 , 6 } , every signed planar graph without circuits of length k is 4-choosable. Furthermore, every signed planar graph without circuits of length 3 and of length 4 is 3-choosable. We construct a signed planar graph with girth 4 which is not 3-choosable but the unsigned graph is 3-choosable. [ABSTRACT FROM AUTHOR]

In this paper we prove that there exists an absolute constant c > 0 such that for every natural number k , every non-bipartite 2-connected graph with average degree at least c k contains k cycles with consecutive odd lengths. This implies the existence of the absolute constant d > 0 that every non-bipartite 2-connected graph with minimum degree at least d k contains cycles of all lengths modulo k , thus providing an answer (in a strong form) to a question of Thomassen in Thomassen (1983). Both results are sharp up to the constant factors. [ABSTRACT FROM AUTHOR]

A solvable cover of a graph is a regular cover whose covering transformation group is solvable. In this paper, we show that a solvable cover of a graph can be decomposed into layers of abelian covers, and also, a lift of a given automorphism of the base graph of a solvable cover can be decomposed into layers of lifts of the automorphism in the layers of the abelian covers. This procedure is applied to classify metacyclic covers of the tetrahedron branched at face-centers. [ABSTRACT FROM AUTHOR]

Minimal non-orientable matroids have been investigated as a threshold between orientability and non-orientability. The Fano matroid and the MacLane matroid are well-known minimal non-orientable matroids of rank 3. A natural question is whether there exists a minimal non-orientable matroid of every rank r with m elements. In this paper, we give an answer to the question in rank 3 that for every m ≥ 7 , there exists a minimal non-orientable matroid of rank 3 with m elements. To prove this statement, we construct two new infinite families of minimal non-orientable matroids of rank 3. Furthermore we also investigate representability of the two infinite families. [ABSTRACT FROM AUTHOR]

Weak maps in matroids originate an order called weak order. In this paper, we characterize some chains of matroids which cannot be increased with respect to the weak order. We also give conditions for a pair of matroids to have few non-common bases. [ABSTRACT FROM AUTHOR]

The linear complementarity problem (LCP) provides a unified approach to many problems such as linear programs, convex quadratic programs, and bimatrix games. The general LCP is known to be NP-hard, but there are some promising results that suggest the possibility that the LCP with a P-matrix (PLCP) may be polynomial-time solvable. However, no polynomial-time algorithm for the PLCP has been found yet and the computational complexity of the PLCP remains open. Simple principal pivoting (SPP) algorithms, also known as Bard-type algorithms, are candidates for polynomial-time algorithms for the PLCP. In 1978, Stickney and Watson interpreted SPP algorithms as a family of algorithms that seek the sink of unique-sink orientations of n -cubes. They performed the enumeration of the arising orientations of the 3-cube, hereafter called PLCP-orientations. In this paper, we present the enumeration of PLCP-orientations of the 4-cube. The enumeration is done via construction of oriented matroids generalizing P-matrices and realizability classification of oriented matroids. Some insights obtained in the computational experiments are presented as well. [ABSTRACT FROM AUTHOR]

An ( n k ) configuration is a set of n points and n lines such that each point lies on k lines while each line contains k points. The configuration is geometric, topological, or combinatorial depending on whether lines are considered to be straight lines, pseudolines, or just combinatorial lines. The existence and enumeration of ( n k ) configurations for a given k has been subject to active research. A current front of research concerns geometric ( n 4 ) configurations: it is now known that geometric ( n 4 ) configurations exist for all n ≥ 18 , apart from sporadic exceptional cases. In this paper, we settle by computational techniques the first open case of ( 1 9 4 ) configurations: we obtain all topological ( 1 9 4 ) configurations among which none are geometrically realizable. [ABSTRACT FROM AUTHOR]

A fullerene graph F is a planar cubic graph with exactly 12 pentagonal faces and other hexagonal faces. A set H of disjoint hexagons of F is called a resonant pattern (or sextet pattern ) if F has a perfect matching M such that every hexagon in H is M -alternating. F is said to be k - resonant if any i ( 0 ≤ i ≤ k ) disjoint hexagons of F form a resonant pattern. It was known that each fullerene graph is 1-resonant and there are only nine fullerene graphs that are 3-resonant. In this paper, we show that the fullerene graphs which do not contain the subgraph L or R as illustrated in Fig. 1 are 2-resonant except for the specific eleven graphs. This result implies that each IPR fullerene is 2-resonant. [ABSTRACT FROM AUTHOR]

In this paper, we classify the family of connected 2-geodesic-transitive graphs of valency 2 p where p is an odd prime. [ABSTRACT FROM AUTHOR]

A finite k -net of order n is an incidence structure consisting of k ≥ 3 pairwise disjoint classes of lines, each of size n , such that every point incident with two lines from distinct classes is incident with exactly one line from each of the k classes. Deleting a line class from a k -net, with k ≥ 4 , gives a derived ( k − 1 )-net of the same order. Finite k -nets embedded in a projective plane PG ( 2 , K ) coordinatized by a field K of characteristic 0 only exist for k = 3 , 4 , see Korchmáros et al. (2014). In this paper, we investigate 3-nets embedded in PG ( 2 , K ) whose line classes are in perspective position with an axis r , that is, every point on the line r incident with a line of the net is incident with exactly one line from each class. The problem of determining all such 3-nets remains open whereas we obtain a complete classification for those coordinatizable by a group. As a corollary, the (unique) 4-net of order 3 embedded in PG ( 2 , K ) turns out to be the only 4-net embedded in PG ( 2 , K ) with a derived 3-net which can be coordinatized by a group. Our results hold true in positive characteristic under the hypothesis that the order of the k -net considered is smaller than the characteristic of K . [ABSTRACT FROM AUTHOR]

We study the flow spectrum S ( G ) and the integer flow spectrum S ¯ ( G ) of signed ( 2 t + 1 ) -regular graphs. We show that if r ∈ S ( G ) , then r = 2 + 1 t or r ≥ 2 + 2 2 t − 1 . Furthermore, 2 + 1 t ∈ S ( G ) if and only if G has a t -factor. If G has a 1-factor, then 3 ∈ S ¯ ( G ) , and for every t ≥ 2 , there is a signed ( 2 t + 1 ) -regular graph ( H , σ ) with 3 ∈ S ¯ ( H ) and H does not have a 1-factor. If G ( ≠ K 2 3 ) is a cubic graph which has a 1-factor, then { 3 , 4 } ⊆ S ( G ) ∩ S ¯ ( G ) . Furthermore, the following four statements are equivalent: (1) G has a 1-factor. (2) 3 ∈ S ( G ) . (3) 3 ∈ S ¯ ( G ) . (4) 4 ∈ S ¯ ( G ) . There are cubic graphs whose integer flow spectrum does not contain 5 or 6, and we construct an infinite family of bridgeless cubic graphs with integer flow spectrum { 3 , 4 , 6 } . We show that there are signed graphs where the difference between the integer flow number and the flow number is greater than or equal to 1, disproving a conjecture of Raspaud and Zhu. The paper concludes with a proof of Bouchet’s 6-flow conjecture for Kotzig-graphs. [ABSTRACT FROM AUTHOR]

In this paper, we study the acquaintance time A C ( G ) defined for a connected graph G . We focus on G ( n , r , p ) , a random subgraph of a random geometric graph in which n vertices are chosen uniformly at random and independently from [ 0 , 1 ] 2 , and two vertices are adjacent with probability p if the Euclidean distance between them is at most r . We present asymptotic results for the acquaintance time of G ( n , r , p ) for a wide range of p = p ( n ) and r = r ( n ) . In particular, we show that with high probability A C ( G ) = Θ ( r − 2 ) for G ∈ G ( n , r , 1 ) , the usual random geometric graph, provided that π n r 2 − ln n → ∞ (that is, above the connectivity threshold). For the percolated random geometric graph G ∈ G ( n , r , p ) , we show that with high probability A C ( G ) = Θ ( r − 2 p − 1 ln n ) , provided that p n r 2 ≥ n 1 / 2 + ε and p < 1 − ε for some ε > 0 . [ABSTRACT FROM AUTHOR]

The current paper deals with the enumeration and classification of the set SOR r , n of self-orthogonal r × r partial Latin rectangles based on n symbols. These combinatorial objects are identified with the independent sets of a Hamming graph and with the zeros of a radical zero-dimensional ideal of polynomials, whose reduced Gröbner basis and Hilbert series can be computed to determine explicitly the set SOR r , n . In particular, the cardinality of this set is shown for r ≤ 4 and n ≤ 9 and several formulas on the cardinality of SOR r , n are exposed, for r ≤ 3 . The distribution of r × s partial Latin rectangles based on n symbols according to their size is also obtained, for all r , s , n ≤ 4 . [ABSTRACT FROM AUTHOR]

The concept of generalized Cayley graphs was introduced by Marušič et al. (1992), where it was asked if there exists a vertex-transitive generalized Cayley graph which is not a Cayley graph. In this paper the question is answered in the affirmative with a construction of two infinite families of such graphs. It is also proven that every generalized Cayley graph admits a semiregular automorphism. [ABSTRACT FROM AUTHOR]

A regular graph is said to be semisymmetric if it is edge-transitive but not vertex-transitive. In this paper, we give a complete list of connected semisymmetric cubic graph of square-free order, which consists of one single graph of order 210 and four infinite families of such graphs. [ABSTRACT FROM AUTHOR]

Let K = { k 1 , k 2 , … , k r } and L = { l 1 , l 2 , … , l s } be disjoint subsets of { 0 , 1 , ⋯ p − 1 } , where p is a prime and F = { F 1 , F 2 , … , F m } be a family of subsets of [ n ] such that | F i | (mod p ) ∈ K for all F i ∈ F and | F i ∩ F j | (mod p ) ∈ L for i ≠ j . In 1991 Alon, Babai and Suzuki conjectured that if n ≥ s + max 1 ≤ i ≤ r k i , then | F | ≤ n s + n s − 1 + ⋯ + n s − r + 1 . In this paper we prove this conjecture. [ABSTRACT FROM AUTHOR]

In an earlier paper Dudek (2015), the present author proposed a simple way to construct families of almost-Ramanujan graphs. The purpose of this note is to point out a crucial error in the construction and discuss what results can be salvaged. [ABSTRACT FROM AUTHOR]