Finding the symmetry group of an LP with equality constraints and its application to classifying orthogonal arrays

For a given linear program (LP) a permutation of its variables that sends feasible points to feasible points and preserves the objective function value of each of its feasible points is a symmetry of the LP. The set of all symmetries of an LP, denoted by $G^{\mathrm{LP}}$, is the symmetry group of the LP. Margot (2010) described a method for computing a subgroup of the symmetry group $G^{\mathrm{LP}}$ of an LP. This method computes $G^{\mathrm{LP}}$ when the LP has only non-redundant inequalities and its feasible set satisfies no equality constraints. However, when the feasible set of the LP satisfies equality constraints this method finds only a subgroup of $G^{\mathrm{LP}}$ and can miss symmetries. We develop a method for finding the symmetry group of a feasible LP whose feasible set satisfies equality constraints. We apply this method to find and exploit the previously unexploited symmetries of an orthogonal array defining integer linear program (ILP) within the branch-and-bound (B&B) with isomorphism pruning algorithm (Margot, 2007). Our method reduced the running time for finding all OD-equivalence classes of OA $(160,8,2,4)$ and OA $(176,8,2,4)$ by factors of $1∕(2.16)$ and $1∕(1.36)$ compared to the fastest known method (Bulutoglu and Ryan, 2018). These were the two bottleneck cases that could not have been solved until the B&B with isomorphism pruning algorithm was applied. Another key finding of this paper is that converting inequalities to equalities by introducing slack variables and exploiting the symmetry group of the resulting ILP’s LP relaxation within the B&B with isomorphism pruning algorithm can reduce the computation time by several orders of magnitude when enumerating a set of all non-isomorphic solutions of an ILP.     

SLE intersecting with random hulls

Lawler, Schramm, and Werner gave in 2003 an explicit formula of the probability that $\mathrm{SLE}(8/3)$ does not intersect a deterministic hull. For general $\mathrm{SLE}(\kappa )$ with $\kappa \ne 8/3$, no such explicit formula has been obtained so far. In this paper, we shall consider a random hull generated by an independent chordal conformal restriction measure and obtain an explicit formula for the probability that $\mathrm{SLE}(\kappa )$ does not intersect this random hull for any $\kappa \in (0,8)$. As a corollary, we will give a new proof of Werner's result on conformal restriction measures.     

Convergence of Picard’s iteration using projection algorithm for noncyclic contractions

Given $A$ and$B$ two nonempty subsets of a metric space, a mapping $T:A\cup B\to A\cup B$ is noncyclic provided that $T\left(A\right)?A$ and $T\left(B\right)?B$. A point $(p,q)\in A\times B$ is called a best proximity pair for the noncyclic mapping $T$ if $p=Tp,q=Tq$ and $d(p,q)=\mathrm{dist}(A,B)$. In this article, we survey the convergence of Picard’s iteration to a best proximity pair for noncyclic contractions using a projection algorithm in uniformly convex Banach spaces, where the initial point is in the proximal set of $A$. We also provide some sufficient conditions to ensure the existence of a common best proximity pairs for a pair of noncyclic mappings.     

Apollonius circles and irreducibility criteria for polynomials

We prove the irreducibility of integer polynomials $f\left(X\right)$ whose roots lie inside an Apollonius circle associated to two points on the real axis with integer abscissae $a$ and $b$, with ratio of the distances to these points depending on the canonical decomposition of $f\left(a\right)$ and $f\left(b\right)$. In particular, we obtain irreducibility criteria for the case where $f\left(a\right)$ and $f\left(b\right)$ have few prime factors, and $f$ is either an Eneström–Kakeya polynomial, or has a large leading coefficient. Analogous results are also provided for multivariate polynomials over arbitrary fields, in a non-Archimedean setting.     

An integer programming approach to b-coloring

In the b-coloring problem, we aim to assign colors from a set $C$ to the vertices of a graph $G$ in such a way that adjacent vertices do not receive the same color, and for every $c\in C$ we have a $c$-colored vertex $v$ in $G$ such that every color in $C\setminus \left\{c\right\}$ is assigned to at least one of $v$’s neighbors. It has been shown that b-coloring is NP-complete, so we propose in this article an approach for the problem under integer programming techniques. To this end, we give an integer programming formulation and study the associated polytope. We provide several families of valid inequalities, and analyze facetness conditions for them. Finally, we show computational evidence suggesting that the given inequalities may be useful in a branch-and-cut environment.     

The projective dimension of three cubics is at most 5

Let R be a polynomial ring over a field and I an ideal generated by three forms of degree three. Motivated by Stillman's question, Engheta proved that the projective dimension $\mathrm{pd}(R/I)$ of $R/I$ is at most 36, although the example with largest projective dimension he constructed has $\mathrm{pd}(R/I)=5$. Based on computational evidence, it had been conjectured that $\mathrm{pd}(R/I)\le 5$. In the present paper we prove this conjectured sharp bound.     

Classification of reconfiguration graphs of shortest path graphs with no induced 4-cycles

For any graph $G$ with $a,b\in V\left(G\right)$, a shortest path reconfiguration graph can be formed with respect to $a$ and $b$; we denote such a graph as $S(G,a,b)$. The vertex set of $S(G,a,b)$ is the set of all shortest paths from $a$ to $b$ in $G$ while two vertices $U,W$ in $V\left(S(G,a,b)\right)$ are adjacent if and only if the vertex sets of the paths that represent $U$ and $W$ differ in exactly one vertex. In a recent paper (Asplund et al., 2018), it was shown that shortest path graphs with girth five or greater are exactly disjoint unions of even cycles and paths. In this paper, we extend this result by classifying all shortest path graphs with no induced 4-cycles.     

On the (3,1)-choosability of planar graphs without adjacent cycles of length 5,6,7

A $(k,d)$-list assignment $L$ of a graph $G$ is a mapping that assigns to each vertex $v$ a list $L\left(v\right)$ of at least $k$ colors satisfying $|L\left(x\right)\cap L\left(y\right)|\le d$ for each edge $xy$. A graph $G$ is $(k,d)$-choosable if there exists an $L$-coloring of $G$ for every $(k,d)$-list assignment $L$. This concept is also known as choosability with separation. In this paper, we prove that any planar graph $G$ is $(3,1)$-choosable if any $i$-cycle is not adjacent to a $j$-cycle, where $5\le i\le 6$ and $5\le j\le 7$.     

Proportional choosability: A new list analogue of equitable coloring

In 2003, Kostochka, Pelsmajer, and West introduced a list analogue of equitable coloring called equitable choosability. In this paper, we motivate and define a new list analogue of equitable coloring called proportional choosability. A $k$-assignment $L$ for a graph $G$ specifies a list $L\left(v\right)$ of $k$ available colors for each vertex $v$ of $G$. An $L$-coloring assigns a color to each vertex $v$ from its list $L\left(v\right)$. For each color $c$, let $\eta \left(c\right)$ be the number of vertices $v$ whose list $L\left(v\right)$ contains $c$. A proportional$L$-coloring of $G$ is a proper $L$-coloring in which each color $c\in {?}_{v\in V\left(G\right)}L\left(v\right)$ is used $?\eta \left(c\right)∕k?$ or $?\eta \left(c\right)∕k?$ times. A graph $G$ is proportionally$k$-choosable if a proportional $L$-coloring of $G$ exists whenever $L$ is a $k$-assignment for $G$. We show that if a graph $G$ is proportionally $k$-choosable, then every subgraph of $G$ is also proportionally $k$-choosable and also $G$ is proportionally $(k+1)$-choosable, unlike equitable choosability for which analogous claims would be false. We also show that any graph $G$ is proportionally $k$-choosable whenever $k\ge \Delta \left(G\right)+?\left|V\left(G\right)\right|∕2?$, and we use matching theory to completely characterize the proportional choosability of stars and the disjoint union of cliques.     

Colouring of generalized signed triangle-free planar graphs

We view an undirected graph $G$ as a symmetric digraph, where each edge $xy$ is replaced by two opposite arcs $e=(x,y)$ and $e^{?1}=(y,x)$. Assume $S$ is an inverse closed subset of permutations of positive integers. We say $G$ is $S$-$k$-colourable if for any mapping $\sigma :E\left(G\right)\to S$ with $\sigma (x,y)={\left(\sigma (y,x)\right)}^{?1}$, there is a mapping $f:V\left(G\right)\to \left[k\right]=\{1,2,\dots ,k\}$ such that ${\sigma }_e\left(f\left(x\right)\right)\ne f\left(y\right)$ for each arc $e=(x,y)$. The concept of $S$-$k$-colourable is a common generalization of several other colouring concepts. This paper is focused on finding the sets $S$ such that every triangle-free planar graph is $S$-3-colourable. Such a set $S$ is called TFP-good. Grötzsch’s theorem is equivalent to say that $S=\left\{id\right\}$ is TFP-good. We prove that for any inverse closed subset $S$ of $S_3$ which is not isomorphic to $\{id,\left(12\right)\}$, $S$ is TFP-good if and only if either $S=\left\{id\right\}$ or there exists $a\in \left[3\right]$ such that for each $\pi \in S$, $\pi \left(a\right)\ne a$. It remains an open question to determine whether or not $S=\{id,\left(12\right)\}$ is TFP-good.