Sarosh Adenwalla

We study set-defined graph classes: hereditary classes of graphs in which vertices are assigned fixed length numerical tuples and adjacency depends only on equality patterns among tuple coordinates. These classes arise naturally in structural graph theory, communication complexity, logic, and adjacency labeling schemes. We investigate the structural complexity of set-defined classes by asking when they are $\chi$-bounded, i.e., when chromatic number is controlled by clique number throughout the class. Our main results give structural and algorithmic characterizations of $\chi$-boundedness in set-defined classes. First, we establish a decomposition theorem showing that every graph in a set-defined class can be partitioned into a number of parts bounded polynomially in its clique number, so that each part induces the union of a constant number of shift-colorable graphs, that is, graphs admitting a homomorphism to a shift graph. This identifies bounded unions of shift-colorable graphs as the fundamental obstruction to $\chi$-boundedness in set-defined classes. Second, for full set-defined graph classes, that is, classes containing all graphs realizable by a fixed Boolean rule on equality patterns, we prove a stronger dichotomy: every such class is either polynomially $\chi$-bounded or contains shift graphs of arbitrarily large chromatic number. Moreover, we provide an algorithm that, given a Boolean-function description of a full set-defined class, decides $\chi$-boundedness of the class. The key tool is combinatorial optimization, namely an explicit reduction to feasibility of tropical linear programs, while the correctness of the algorithm is proved using a duality result connecting this feasibility to winning strategies in mean payoff games. Conversely, we show that every integer system of tropical inequalities, and hence every mean payoff game, can be encoded in strongly polynomial time as a set-defined graph class whose non-$\chi$-boundedness is equivalent to their feasibility. Thus the $\chi$-boundedness dichotomy for set-defined graph classes provides a graph-theoretic counterpart of tropical feasibility and mean-payoff-game solvability, and suggests a route for transferring techniques among structural graph theory, tropical algebra, and game-theoretic algorithms.

Ron Graham introduced a function g(n) in the 1986 Issue 3 Problems column of Mathematical Magazine: g(n) is the least integer s such that the integers from n+1 through s contain a subset whose product with n is a square. Recent work of Kagey and Rajesh established several results about g(n) and conjectured a characterization of the integers n for which g(n)=2n. They also introduced m-th-power generalisations for m ≥ 2. In this paper, we prove their conjecture and obtain further results for these generalisations.

Boolean combinations allow combining given combinatorial objects to obtain new, potentially more complicated, objects. In this paper, we initiate a systematic study of this idea applied to graphs. In order to understand expressive power and limitations of boolean combinations in this context, we investigate how they affect different combinatorial and structural properties of graphs, in particular $\chi$-boundedness, as well as characterize the structure of boolean combinations of graphs from various classes.

Erdős and Graham asked whether there is an n whose divisors greater than 1 can be used as the moduli of a distinct covering system in which overlapping congruences have coprime moduli. We prove that no such n exists. We also give a necessary condition for n to have such a congruence set and prove that certain families of n do have this property.

A permutation of the integers avoiding monotone arithmetic progressions of length 6 was constructed in (Geneson, 2018). We improve on this by constructing a permutation of the integers avoiding monotone arithmetic progressions of length 5. We also construct permutations of the integers and the positive integers that improve on previous upper and lower density results. In (Davis et al. 1977) they constructed a doubly infinite permutation of the positive integers that avoids monotone arithmetic progressions of length 4. We construct a doubly infinite permutation of the integers avoiding monotone arithmetic progressions of length 5. A permutation of the positive integers that avoided monotone arithmetic progressions of length 4 with odd common difference was constructed in (LeSaulnier and Vijay, 2011). We generalise this result and show that for each k ≥ 1, there exists a permutation of the positive integers that avoids monotone arithmetic progressions of length 4 with common difference not divisible by 2ᵏ. In addition, we specify the structure of permutations of [1,n] that avoid length 3 monotone arithmetic progressions mod n as defined in (Davis et al. 1977) and provide an explicit construction for a multiplicative result on permutations that avoid length k monotone arithmetic progressions mod n.